deques in c 2b 2b

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