smatskevich

Queue

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

×