Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java
communitycreator

How to use stacks to implement a queue in Java

Harsh Jain

In this shot, we will implement stacks with push and pop operations. Our task is to implement a queue using that stack.

Solution approach

We can use two stacks to implement a queue. Let the implemented queue be q and let the stacks be stack1 and stack2, respectively.

We will make the deQueue operation costly. In the enQueue operation, the new element is always entered at the top of the stack. In the deQueue operation, if stack2 is empty, then all the elements are removed from stack1 to stack2, and the top of stack2 is returned.

Code

Let’s see the code now.

import java.util.Stack;

class Solution{
    
    static class Queue {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
    }

    static void push(Stack<Integer> stack, int value)
    {
        stack.push(value);
    }

    static int pop(Stack<Integer> stack)
    {
        if (stack.isEmpty()) {
            System.out.println("Stack Underflow");
            System.exit(0);
        }

        return stack.pop();
    }

    static void enQueue(Queue q, int x)
    {
        push(q.stack1, x);
    }

    static int deQueue(Queue q)
    {
        int x;

        if (q.stack1.isEmpty() && q.stack2.isEmpty()) {
            System.out.println("Q is empty");
            System.exit(0);
        }

        if (q.stack2.isEmpty()) {
            while (!q.stack1.isEmpty()) {
                push(q.stack2,  pop(q.stack1));
            }
        }
         return pop(q.stack2);
    }

    public static void main(String args[])
    {
        Queue q = new Queue();
        q.stack1 = new Stack<>();
        q.stack2 = new Stack<>();
        enQueue(q, 1);
        enQueue(q, 2);
        enQueue(q, 3);

        System.out.print(deQueue(q) + " ");
        System.out.print(deQueue(q) + " ");
        System.out.println(deQueue(q) + " ");
    }
}
Implement Queue using Stacks in Java

Explanation

  • In the first line of code, we import the java.util.Stack class.

  • From lines 5 to 8, we make a static class Queue that has two stacks.

  • From lines 10 to 13, we make a function to push an item into the stack.

  • From lines 15 to 23, we call a function to pop an item from the stack.

  • From lines 25 to 28, we make a function to enqueue an item into the queue.

  • From lines 30 to 45, we make a function to dequeue an item from the queue.

  • From lines 47 to 59, we have our driver code main() function in which we create a queue, then enqueue elements into it, and finally dequeue elements from it and test all the functions that we create above.

In this way, we can implement a queue using stacks in Java.

RELATED TAGS

java
communitycreator
RELATED COURSES

View all Courses

Keep Exploring