smatskevich

QueueOnChunks

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

×