smatskevich

QueueOnList

Mar 11th, 2017
195
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <assert.h>
  2. #include <iostream>
  3.  
  4. class CQueueOnList {
  5. public:
  6.     CQueueOnList();
  7.     ~CQueueOnList();
  8.  
  9.     // Добавление элемента в очередь.
  10.     void Enqueue( int value );
  11.     // Извлечение из очереди. Если очередь пуста, возвращает -1.
  12.     int Dequeue();
  13.  
  14. private:
  15.     // Элемент односвязного списка.
  16.     struct CListNode {
  17.         int Data;
  18.         CListNode* Next;
  19.  
  20.         CListNode( int data ) : Data( data ), Next( 0 ) {}
  21.     };
  22.     CListNode* head; // Голова очереди. Указывает на первый элемент списка. 0, если очередь пуста.
  23.     CListNode* tail; // Хвост очереди. Указывает на последний элемент списка.
  24. };
  25.  
  26. CQueueOnList::CQueueOnList() :
  27.     head( 0 ),
  28.     tail( 0 )
  29. {
  30. }
  31.  
  32. CQueueOnList::~CQueueOnList()
  33. {
  34.     while( head != 0 ) {
  35.         CListNode* next = head->Next;
  36.         delete head;
  37.         head = next;
  38.     }
  39. }
  40.  
  41. void CQueueOnList::Enqueue( int value )
  42. {
  43.     if( tail == 0 ) {
  44.         assert( head == 0 );
  45.         tail = new CListNode( value );
  46.         head = tail;
  47.     } else {
  48.         assert( head != 0 );
  49.         tail->Next = new CListNode( value );
  50.         tail = tail->Next;
  51.     }
  52. }
  53.  
  54. int CQueueOnList::Dequeue()
  55. {
  56.     if( head == 0 ) {
  57.         assert( tail == 0 );
  58.         // Очередь пуста.
  59.         return -1;
  60.     }
  61.     assert( tail != 0 );
  62.  
  63.     const int value = head->Data;
  64.     CListNode* toDelete = head;
  65.     // Подвинем head вперед. Он мог стать равным 0, если элемент был последним.
  66.     head = head->Next;
  67.     delete toDelete;
  68.     if( head == 0 ) {
  69.         tail = 0;
  70.     }
  71.     return value;
  72. }
  73.  
  74. int main()
  75. {
  76.     std::cout << ( sizeof( int ) == sizeof( int* ) ? "equal" : "not equal" );
  77.     int requestsCount = 0;
  78.     std::cin >> requestsCount;
  79.  
  80.     CQueueOnList queue;
  81.  
  82.     for( int i = 0; i < requestsCount; ++i ) {
  83.         int requestType = 0;
  84.         int requestValue = 0;
  85.         std::cin >> requestType >> requestValue;
  86.         switch( requestType ) {
  87.             case 2:
  88.                 if( queue.Dequeue() != requestValue ) {
  89.                     std::cout << "NO";
  90.                     return 0;
  91.                 }
  92.                 break;
  93.             case 3:
  94.                 queue.Enqueue( requestValue );
  95.                 break;
  96.             default:
  97.                 assert( false );
  98.         }
  99.     }
  100.     std::cout << "YES";
  101.     return 0;
  102. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×