deques in c++ code example

Example: deques in c++

// A CPP program to demonstrate linked list  
// based implementation of queue  
#include <bits/stdc++.h> 
using namespace std; 
  
// A linked list (LL) node to store a queue entry  
class QNode  
{  
    public: 
    int key;  
    QNode *next;  
};  
  
// The queue, front stores the front node 
// of LL and rear stores ths last node of LL  
class Queue  
{  
    public: 
    QNode *front, *rear;  
};  
  
// A utility function to create  
// a new linked list node.  
QNode* newNode(int k)  
{  
    QNode *temp = new QNode(); 
    temp->key = k;  
    temp->next = NULL;  
    return temp;  
}  
  
// A utility function to create an empty queue  
Queue *createQueue()  
{  
    Queue *q = new Queue(); 
    q->front = q->rear = NULL;  
    return q;  
}  
  
// The function to add a key k to q  
void enQueue(Queue *q, int k)  
{  
    // Create a new LL node  
    QNode *temp = newNode(k);  
  
    // If queue is empty, then  
    // new node is front and rear both  
    if (q->rear == NULL)  
    {  
    q->front = q->rear = temp;  
    return;  
    }  
  
    // Add the new node at  
    // the end of queue and change rear  
    q->rear->next = temp;  
    q->rear = temp;  
}  
  
// Function to remove 
// a key from given queue q  
QNode *deQueue(Queue *q)  
{  
    // If queue is empty, return NULL.  
    if (q->front == NULL)  
    return NULL;  
  
    // Store previous front and  
    // move front one node ahead  
    QNode *temp = q->front;  
    q->front = q->front->next;  
  
    // If front becomes NULL, then  
    // change rear also as NULL  
    if (q->front == NULL)  
    q->rear = NULL;  
    return temp;  
}  
  
// Driver code  
int main()  
{  
    Queue *q = createQueue();  
    enQueue(q, 10);  
    enQueue(q, 20);  
    deQueue(q);  
    deQueue(q);  
    enQueue(q, 30);  
    enQueue(q, 40);  
    enQueue(q, 50);  
    QNode *n = deQueue(q);  
    if (n != NULL)  
    cout << "Dequeued item is " << n->key;  
    return 0;  
}

Tags:

Misc Example