smatskevich

QueueOnList2018

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

×