fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. #define BUF 4
  6.  
  7. class queue {
  8. 	private:
  9. 	struct Node {
  10. 		int *arr;
  11. 		int front,rare;
  12. 		Node* next;
  13. 		queue* parent_queue;
  14. 		Node(queue* pq) : front(0),rare(0),next(NULL),parent_queue(pq) {
  15. 			arr = new int[BUF];
  16. 			++parent_queue->nNodes;
  17. 		}
  18. 		~Node() {
  19. 			delete[] arr;
  20. 			--parent_queue->nNodes;
  21. 		}
  22. 		void add(int v) {
  23. 			if(rare >= BUF) return;
  24. 			arr[rare++] = v;
  25. 		}
  26. 		int size() {
  27. 			return rare-front;
  28. 		}
  29. 	};
  30. 	int nNodes;
  31. 	Node* head,*tail;
  32.  
  33. 	public:
  34. 	queue() : head(0),tail(0),nNodes(0) {}
  35.  
  36. 	bool isEmpty() {
  37. 		return (nNodes == 0);
  38. 	}
  39.  
  40. 	void enqueue(int v) {
  41. 		if(!head) {
  42. 			head = tail = new Node(this);
  43. 			head->add(v);
  44. 		} else {
  45. 			if(tail->rare == BUF) {
  46. 				tail->next = new Node(this);
  47. 				tail = tail->next;
  48. 			}
  49. 			tail->add(v);
  50. 		}
  51. 	}
  52.  
  53. 	void dequeue() {
  54. 		if(isEmpty() || head->front == -1) return;
  55. 		++head->front;
  56. 		if(head->front == head->rare) {
  57. 			Node* temp = head;
  58. 			head = head->next;
  59. 			delete temp;
  60. 		}
  61. 	}
  62.  
  63. 	bool isEmpty() const {
  64. 		return (nNodes == 0);
  65. 	}
  66.  
  67. 	int getFront() const {
  68. 		if(isEmpty() || head->front == -1) return -1;
  69. 		return head->arr[head->front];
  70. 	}	
  71.  
  72. 	int size() const {
  73. 		if(nNodes == 0) {
  74. 			return 0;
  75. 		} else if(nNodes >= 2) {
  76. 			return (nNodes-2)*BUF + head->size() + tail->size();
  77. 		} else {
  78. 			return head->size();
  79. 		}
  80. 	}
  81. };
  82.  
  83. int main() {
  84. 	queue q;
  85. 	q.enqueue(18);q.enqueue(4);q.enqueue(9);q.enqueue(1);q.enqueue(3);q.enqueue(5);q.enqueue(10);
  86. 	while(!q.isEmpty()) {
  87. 		cout << "size = "<<q.size()<<" front = "<<q.getFront() << endl;
  88. 		q.dequeue();
  89. 	}
  90. 	return 0;
  91. }
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
size = 7 front = 18
size = 6 front = 4
size = 5 front = 9
size = 4 front = 1
size = 3 front = 3
size = 2 front = 5
size = 1 front = 10
https://ideone.com/GL3nyw
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!