LeetCode: Implement Queue using Stacks

In this problem, the programmer is tasked with implementing their own version of a Queue. Remember that a Queue is a first in first out data structure, meaning the first element to be added will be removed. Normally a queue has methods add(), remove(), and peek(), but this problem reuses stack naming conventions for add() and remove(). Therefor add() is the equivalent of push() and remove is the equivalent of pop().

Solution Intuition

The first concept to notice while solving this problem is that a stack and queue have opposite ordering when removing elements. A pop() in a stack will always return the very last element that was added to the stack. A queue on other hand gives an offer() method, which will return the very first element added to the queue. Using this knowledge we can create a MyQueue class that contains two stacks.

The first stack will be the one that maintains a collection of elements, in the same order that they were pushed. Next we create a second stack that will be the equivalent of our queue. When applying any queue operations, all that needs to be done is invert the elements in stack one and push them onto stack two. This will have the effect of reversing the original stack. By reversing the elements, the data structure becomes a type of FIFO (first in first out) because we will now be popping the first item on the stack rather than the last.

Implementation in Java

package org.example;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.push(1);
        System.out.println(myQueue.empty());
        myQueue.push(2);
        myQueue.push(3);
        myQueue.display();
        System.out.println(myQueue.peek());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.peek());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.peek());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.empty());
    }
}

class MyQueue {
    Stack<Integer> stk1;
    Stack<Integer> stk2;
    public MyQueue() {
        stk1 = new Stack<>();
        stk2 = new Stack<>();
    }

    public void push(int x) {
        stk1.push(x);
    }
    public int pop() {
        if(stk2.empty()) {
            while(!stk1.empty()) {
                stk2.push(stk1.pop());
            }
        }
        return stk2.pop();
    }

    public int peek() {
        if(stk2.empty()) {
            while(!stk1.empty()) {
                stk2.push(stk1.pop());
            }
        }
        return stk2.peek();
    }

    public boolean empty() {
        return stk1.empty() && stk2.empty();
    }

    public void display() {
        if(stk2.empty()) {
            while(!stk1.empty()) {
                stk2.push(stk1.pop());
            }
        }
        int x = stk2.size() - 1;
        while (x >= 0) {
            System.out.println(stk2.elementAt(x));
            x--;
        }
    }
}

Method Explanations

• push(int x): Push operations will be exactly the same as those of a stack. The original list we want to maintain will be added to stack one.
• pop(): A pop operation will need to extract the first element of stack one instead of the last. First we check if stack two has an elements. If not, progressively pop each element off stack one onto stack two. This reverses the order of the original stack, in turn simulating a queue. Then we can just pop() the last element added to stack two.
• peek(): The logic for this method will be almost identical to the pop() method. (In fact we should just extract it out into its own method, to prevent code duplication. I’ll leave that portion up to any diligent programmers.) The only difference is we will end by peeking the last element of stack two.
• empty(): To check if our queue implementation is empty, we just need to determine if both stacks are empty and no more elements exist. This is accomplished through a simple and condition.
• display(): While not part of the actual leetcode question, display() is used for learning purposes. It add all elements to stack two and then iterates over them in reverse, displaying them to the console.

Summary

Congratulations, you have now created your own implementation of a queue using a unique technique of reversing two stacks.

Here is a link to an example project: