Advertisement
smatskevich

Queue on list

Oct 8th, 2015
355
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. struct CNode {
  4.     int Data;
  5.     CNode* Next;
  6.  
  7.     explicit CNode( int data ) : Data( data ), Next( 0 ) {}
  8. };
  9.  
  10. class CQueue {
  11. public:
  12.     CQueue();
  13.     ~CQueue();
  14.  
  15.     // Вставка элемент.
  16.     void Enqueue( int element );
  17.     // Извлечение элемента. Если очередь пуста, то возвращает -1.
  18.     int Dequeue();
  19.  
  20. private:
  21.     CNode* head; // Указатель на голову очереди - первый элемент односвязного списка.
  22.     CNode* tail; // Указатель на хвост очереди - последний элемент односвязного списка.
  23. };
  24.  
  25. CQueue::CQueue() :
  26.     head( 0 ),
  27.     tail( 0 )
  28. {
  29. }
  30.  
  31. CQueue::~CQueue()
  32. {
  33.     for( CNode* current = head; current != 0; ) {
  34.         CNode* next = current->Next;
  35.         delete current;
  36.         current = next;
  37.     }
  38. }
  39.  
  40. void CQueue::Enqueue( int element )
  41. {
  42.     CNode* newNode = new CNode( element );
  43.     if( tail != 0 ) {
  44.         tail->Next = newNode;
  45.     } else {
  46.         head = newNode;
  47.     }
  48.     tail = newNode;
  49. }
  50.  
  51. int CQueue::Dequeue()
  52. {
  53.     if( head == 0 ) {
  54.         return -1;
  55.     }
  56.     // Запоминаем результат и указатель на следующий.
  57.     int result = head->Data;
  58.     CNode* next = head->Next;
  59.  
  60.     // Удаляем элемент и двигаем head.
  61.     delete head;
  62.     head = next;
  63.  
  64.     // Если список оказался пуст, обновим tail.
  65.     if( head == 0 ) {
  66.         tail = 0;
  67.     }
  68.  
  69.     return result;
  70. }
  71.  
  72. int main()
  73. {
  74.     int commandsCount = 0;
  75.     std::cin >> commandsCount;
  76.  
  77.     CQueue queue;
  78.     for( int i = 0; i < commandsCount; ++i ) {
  79.         int command = 0;
  80.         std::cin >> command;
  81.         int value = 0;
  82.         std::cin >> value;
  83.         switch( command ) {
  84.             case 2:
  85.             {
  86.                 int extractedElement = queue.Dequeue();
  87.                 if( value != extractedElement ) {
  88.                     std::cout << "NO";
  89.                     return 0;
  90.                 }
  91.                 break;
  92.             }
  93.             case 3:
  94.                 queue.Enqueue( value );
  95.                 break;
  96.         }
  97.     }
  98.     std::cout << "YES";
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement