C++ Program to Implement Queue using Two Stacks

«
»
This is a C++ Program to implement queue using stacks. n this method, 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 satck1 to stack2.
3) Pop the element from stack2 and return it.

Here is source code of the C++ Program to Implement Queue Using Two Stacks. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* Program to implement a queue using two stacks */
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. /* structure of a stack node */
  9. struct sNode
  10. {
  11.         int data;
  12.         struct sNode *next;
  13. };
  14.  
  15. /* Function to push an item to stack*/
  16. void push(struct sNode** top_ref, int new_data);
  17.  
  18. /* Function to pop an item from stack*/
  19. int pop(struct sNode** top_ref);
  20.  
  21. /* structure of queue having two stacks */
  22. struct queue
  23. {
  24.         struct sNode *stack1;
  25.         struct sNode *stack2;
  26. };
  27.  
  28. /* Function to enqueue an item to queue */
  29. void enQueue(struct queue *q, int x)
  30. {
  31.     push(&q->stack1, x);
  32. }
  33.  
  34. /* Function to dequeue an item from queue */
  35. int deQueue(struct queue *q)
  36. {
  37.     int x;
  38.  
  39.     /* If both stacks are empty then error */
  40.     if (q->stack1 == NULL && q->stack2 == NULL)
  41.     {
  42.         cout << "Queue is empty";
  43.         exit(0);
  44.     }
  45.  
  46.     /* Move elements from satck1 to stack 2 only if
  47.      stack2 is empty */
  48.     if (q->stack2 == NULL)
  49.     {
  50.         while (q->stack1 != NULL)
  51.         {
  52.             x = pop(&q->stack1);
  53.             push(&q->stack2, x);
  54.         }
  55.     }
  56.  
  57.     x = pop(&q->stack2);
  58.     return x;
  59. }
  60.  
  61. /* Function to push an item to stack*/
  62. void push(struct sNode** top_ref, int new_data)
  63. {
  64.     /* allocate node */
  65.     struct sNode* new_node = (struct sNode*) malloc(sizeof(struct sNode));
  66.  
  67.     if (new_node == NULL)
  68.     {
  69.         cout << "Stack overflow \n";
  70.         exit(0);
  71.     }
  72.  
  73.     /* put in the data  */
  74.     new_node->data = new_data;
  75.  
  76.     /* link the old list off the new node */
  77.     new_node->next = (*top_ref);
  78.  
  79.     /* move the head to point to the new node */
  80.     (*top_ref) = new_node;
  81. }
  82.  
  83. /* Function to pop an item from stack*/
  84. int pop(struct sNode** top_ref)
  85. {
  86.     int res;
  87.     struct sNode *top;
  88.  
  89.     /*If stack is empty then error */
  90.     if (*top_ref == NULL)
  91.     {
  92.         cout << "Stack overflow \n";
  93.         exit(0);
  94.     }
  95.     else
  96.     {
  97.         top = *top_ref;
  98.         res = top->data;
  99.         *top_ref = top->next;
  100.         free(top);
  101.         return res;
  102.     }
  103. }
  104.  
  105. /* Driver function to test anove functions */
  106. int main()
  107. {
  108.     /* Create a queue with items 1 2 3*/
  109.     struct queue *q = (struct queue*) malloc(sizeof(struct queue));
  110.     q->stack1 = NULL;
  111.     q->stack2 = NULL;
  112.     cout << "Enqueuing...";
  113.     cout << endl;
  114.     enQueue(q, 1);
  115.     cout << "Enqueuing...";
  116.     cout << endl;
  117.     enQueue(q, 2);
  118.     cout << "Enqueuing...";
  119.     cout << endl;
  120.     enQueue(q, 3);
  121.  
  122.     /* Dequeue items */
  123.     cout << "Dequeuing...";
  124.     cout << deQueue(q) << " ";
  125.     cout << endl;
  126.     cout << "Dequeuing...";
  127.     cout << deQueue(q) << " ";
  128.     cout << endl;
  129.     cout << "Dequeuing...";
  130.     cout << deQueue(q) << " ";
  131.     cout << endl;
  132. }

Output:

advertisement
$ g++ QueueUsingStacks.cpp
$ a.out
 
Enqueuing...
Enqueuing...
Enqueuing...
Dequeuing...1 
Dequeuing...2 
Dequeuing...3 
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.