1
2// A CPP program to demonstrate linked list
3// based implementation of queue
4#include <bits/stdc++.h>
5using namespace std;
6
7// A linked list (LL) node to store a queue entry
8class QNode
9{
10 public:
11 int key;
12 QNode *next;
13};
14
15// The queue, front stores the front node
16// of LL and rear stores ths last node of LL
17class Queue
18{
19 public:
20 QNode *front, *rear;
21};
22
23// A utility function to create
24// a new linked list node.
25QNode* newNode(int k)
26{
27 QNode *temp = new QNode();
28 temp->key = k;
29 temp->next = NULL;
30 return temp;
31}
32
33// A utility function to create an empty queue
34Queue *createQueue()
35{
36 Queue *q = new Queue();
37 q->front = q->rear = NULL;
38 return q;
39}
40
41// The function to add a key k to q
42void enQueue(Queue *q, int k)
43{
44 // Create a new LL node
45 QNode *temp = newNode(k);
46
47 // If queue is empty, then
48 // new node is front and rear both
49 if (q->rear == NULL)
50 {
51 q->front = q->rear = temp;
52 return;
53 }
54
55 // Add the new node at
56 // the end of queue and change rear
57 q->rear->next = temp;
58 q->rear = temp;
59}
60
61// Function to remove
62// a key from given queue q
63QNode *deQueue(Queue *q)
64{
65 // If queue is empty, return NULL.
66 if (q->front == NULL)
67 return NULL;
68
69 // Store previous front and
70 // move front one node ahead
71 QNode *temp = q->front;
72 q->front = q->front->next;
73
74 // If front becomes NULL, then
75 // change rear also as NULL
76 if (q->front == NULL)
77 q->rear = NULL;
78 return temp;
79}
80
81// Driver code
82int main()
83{
84 Queue *q = createQueue();
85 enQueue(q, 10);
86 enQueue(q, 20);
87 deQueue(q);
88 deQueue(q);
89 enQueue(q, 30);
90 enQueue(q, 40);
91 enQueue(q, 50);
92 QNode *n = deQueue(q);
93 if (n != NULL)
94 cout << "Dequeued item is " << n->key;
95 return 0;
96}
97