Implement Queue Using Stacks

“Implement Queue using Stacks” is a classic interview problem based on stack and queue data structures. 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 customisation in the standard operations of stack data structure, push and pop. 

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

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

Create Two Stacks, say ‘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 Stacks is as follows:

/* Program to Implement Queue Using 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. Find Minimum number of bracket reversals required to make an expression balanced.
11. Program to find longest palindromic Substring.
12. Program to check Anagram Strings.
13. Program to check whether two Strings are Rotation of each other or not.
14. Program to check Palindromic Anagram.
15. Program to print all the Palindromic Substring of the String.
16. Program to check Panagram String.
17. Program to find first non-repeating character of the String.
18. Check Anagram Strings.
19. Check Whether Given String is Palindromic Anagram or Not.
20. Check Whether Given String is Panagram or Not.