Implement Queue Using Stacks

Implement Queue using Stacks” is a classic interview problem based on stack and queue data structure. Here, we have given two stacks and our task is to implement queue using these two stack. 

Stack contains basically two operations, including:  push and pop. To implement queue using given two stacks, we need to perform some customization in the standard operations of stacks, push and pop. 

There might be other methods possible to implement queue using two stacks. But, Here, we are customizing pop operation of stack data structure to implement queue data structure. 

The steps required to implement queue using these stacks are as follows:

  1. Create two stacks, say stack ‘st1’ and ‘st2’.

Push Operation:

  1. Simply, Push element into stack ‘st1’.

       Pop Operation:

  1. Pop all elements of stack ‘st1’ and push those elements into stack ‘st2’.
  2. Now, pop the first element of stack ‘st2’.
  3. Again, pop all elements of stack ‘st2’ and push those elements into stack ‘st1’.

C++ Program to Implement Queue Using Two Stacks


#include<bits/stdc++.h>  
using namespace std;    
void enqueue(stack<int>&st1, int ele)
{
    st1.push(ele);
}
int dequeue(stack<int>&st1)
{
    stack<int> st2;
    /* Pop all elements from stack 'st1'
    and push those into stack 'st2' */
    while(!st1.empty())
    {
        st2.push(st1.top());
        st1.pop();    
    } 
    // Pop the element from 'st2'
    int temp = st2.top();
    st2.pop();
    /*Now, Pop all elements from stack 'st2'
    and push those into stack 'st1' */
    while(!st2.empty())
    {
        st1.push(st2.top());
        st2.pop();    
    } 
    return temp;
}
int main()
{
    stack<int> st1;
    // Push Some Elements into queue
    enqueue(st1,1);
    enqueue(st1,2);
    enqueue(st1,3);
    
    // pop element from the queue
    
    cout<<"The dequeued element from queue is "<<dequeue(st1);
    
}


OUTPUT:
The dequeued element from queue is 1

Related Posts:

  1. Merge Overlapping Intervals using Stacks
  2. Implement Stack Using Linked List
  3. Largest Rectangular Area in Histogram
  4. Length of Longest Valid Substring
  5. Reverse a String using Stack
  6. Implement two stacks in a single array
  7. Print Bracket Number
  8. Next Greater Frequency Element
  9. Sort a Stack using Temporary Stack
  10. Infix to Postfix Conversion
  11. Infix to Prefix Conversion
  12. Prefix to Infix Conversion
  13. Prefix to Postfix Conversion
  14. Postfix to Infix Conversion
  15. Postfix to Prefix Conversion
  16. Check whether given Parentheses String are Balanced Parentheses or Not.
  17. Next Greater Element
  18. Find Minimum number of bracket reversals required to make an expression balanced.
  19. Program to sort an Array of 0s and 1s.
  20.  Program to find missing number in an array.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *