C++ Program to Implement Queue Using Two Stacks

Article Creation Date : 19-Jun-2021 10:54:50 PM

/* C++ Program to Implement Queue Using Two Stacks

This is a C++ Program to implement queue using stacks. In this program, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.  */

/* Program to implement a queue using two stacks */

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
 
using namespace std;
 
struct sNode
{
        int data;
        struct sNode *next;
};
 
void push(struct sNode** top_ref, int new_data);
 
int pop(struct sNode** top_ref);

struct queue
{
        struct sNode *stack1;
        struct sNode *stack2;
};
 
void enQueue(struct queue *q, int x)
{
    push(&q->stack1, x);
}
 
int deQueue(struct queue *q)
{
    int x;
 
    if (q->stack1 == NULL && q->stack2 == NULL)
    {
        cout << "Queue is empty";
        return 0;
    }
 
    if (q->stack2 == NULL)
    {
        while (q->stack1 != NULL)
        {
            x = pop(&q->stack1);
            push(&q->stack2, x);
        }
    }
 
    x = pop(&q->stack2);
    return x;
}
 
void push(struct sNode** top_ref, int new_data)
{
    struct sNode* new_node = (struct sNode*) malloc(sizeof(struct sNode));
 
    if (new_node == NULL)
    {
        cout << "Stack overflow \n";
        return ;
    }
 
    new_node->data = new_data;
    new_node->next = (*top_ref);
    (*top_ref) = new_node;
}
 
int pop(struct sNode** top_ref)
{
    int res;
    struct sNode *top;
 
    /*If stack is empty then error */
    if (*top_ref == NULL)
    {
        cout << "Stack overflow \n";
        return 0;
    }
    else
    {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}
 
int main()
{
    struct queue *q = (struct queue*) malloc(sizeof(struct queue));
    q->stack1 = NULL;
    q->stack2 = NULL;
    enQueue(q, 4);
    enQueue(q, 8);
    enQueue(q, 3);
 
    cout << deQueue(q) << " ";
    cout << deQueue(q) << " ";
    cout << deQueue(q) << " ";
    cout << endl;
}



/*
Output :
4 8 3

*/