Posts Queue using two Stacks (geeksforgeeks - SDE Sheet)
Post
Cancel

Queue using two Stacks (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Implement a Queue using 2 stacks s1 and s2

A Query Q is of 2 Types

(i) 1 x (a query of this type means pushing ‘x’ into the queue)
(ii) 2 (a query of this type means to pop element from queue and print the poped element)

geeksforgeeks

SOLUTION

  • push

    • First, all elements from s1 are transferred to s2.
    • Then, the new element x is pushed to the now-empty s1.
    • Finally, all the elements in s2 are transferred back to s1 in reverse order.
  • pop

    • get element from s1. return -1 if empty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class StackQueue
{
    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();

    //Function to push an element in queue by using 2 stacks.
    void Push(int x)
    {

        while(!s1.isEmpty())
            s2.push(s1.pop());

        s1.push(x);

        while(!s2.isEmpty())
            s1.push(s2.pop());


    }


    //Function to pop an element from queue by using 2 stacks.
    int Pop()
    {
        return s1.isEmpty() ? -1 : s1.pop();
    }
}
This post is licensed under CC BY 4.0 by the author.