Posts Stack using two queues (geeksforgeeks - SDE Sheet)
Post
Cancel

Stack using two queues (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Implement a Stack using two queues q1 and q2.

geeksforgeeks

SOLUTION

  • push:

    add current element to q2
    transfer all elements from q1 to q2
    switch q1, q2 references, so q1 becomes q2 and vice versa

  • pop:

    get element from q1. 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Queues
{
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();

    //Function to push an element into stack using two queues.
    void push(int a)
    {

        // add element in q2
        q2.add(a);

        // move all elements from q1 to q2
        // so, the current element will become the first element to be remove, which is what we want as per stack logic
        while(!q1.isEmpty()){
            q2.add(q1.poll());
        }

        // swap q1 & q2
        // this helps in avoiding logic to check which queue will act as source or destination
        Queue<Integer> tq = q1;
        q1 = q2;
        q2 = tq;

    }

    //Function to pop an element from stack using two queues.
    int pop()
    {

        // while pushing, we have made sure that the final queue q1 has all the elements
        // if its empty, return -1
        if(q1.isEmpty())
            return -1;

        // otherwise get the element from queue which will be logically the top of stack
        return q1.poll();

    }

}
This post is licensed under CC BY 4.0 by the author.