Queue Using Two Stacks Algorithm

The Queue Using Two Stacks Algorithm is a technique to implement a queue data structure using two stacks. A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where the element that is inserted first will be removed first. A stack, on the other hand, follows the Last-In-First-Out (LIFO) principle, where the element that is inserted last will be removed first. The main idea behind this algorithm is to use one stack for enqueuing elements and another stack for dequeuing elements, effectively converting the LIFO behavior of stacks into the FIFO behavior of a queue. To implement this algorithm, we need two stacks, Stack1 and Stack2. When an element is enqueued, it is pushed onto Stack1. When an element is dequeued, if Stack2 is empty, all elements are popped from Stack1 and pushed onto Stack2, essentially reversing their order, and then the top element of Stack2 is popped. If Stack2 is not empty, the top element of Stack2 is simply popped. This ensures that the oldest element in the queue is always at the top of Stack2, maintaining the FIFO order of the queue. This algorithm works efficiently for both enqueuing and dequeuing operations, making it a useful technique to implement queues in situations where only stack operations are available.
package Others;

import java.util.Stack;

/**
 * This implements Queue using two Stacks.
 *
 * Big O Runtime:
 *      insert(): O(1)
 *      remove(): O(1) amortized
 *      isEmpty(): O(1)
 *
 * A queue data structure functions the same as a real world queue.
 * The elements that are added first are the first to be removed.
 * New elements are added to the back/rear of the queue.
 *
 * @author sahilb2 (https://www.github.com/sahilb2)
 *
 */
class QueueWithStack {

    // Stack to keep track of elements inserted into the queue
    private Stack inStack;
    // Stack to keep track of elements to be removed next in queue
    private Stack outStack;

    /**
	 * Constructor
	 */
    public QueueWithStack() {
        this.inStack = new Stack();
        this.outStack = new Stack();
    }

    /**
     * Inserts an element at the rear of the queue
     *
     * @param x element to be added
     */
    public void insert(Object x) {
        // Insert element into inStack
        this.inStack.push(x);
    }

    /**
     * Remove an element from the front of the queue
     *
     * @return the new front of the queue
     */
    public Object remove() {
        if(this.outStack.isEmpty()) {
            // Move all elements from inStack to outStack (preserving the order)
            while(!this.inStack.isEmpty()) {
                this.outStack.push( this.inStack.pop() );
            }
        }
        return this.outStack.pop();
    }

    /**
     * Peek at the element from the front of the queue
     *
     * @return the front element of the queue
     */
    public Object peekFront() {
        if(this.outStack.isEmpty()) {
            // Move all elements from inStack to outStack (preserving the order)
            while(!this.inStack.isEmpty()) {
                this.outStack.push( this.inStack.pop() );
            }
        }
        return this.outStack.peek();
    }

    /**
     * Peek at the element from the back of the queue
     *
     * @return the back element of the queue
     */
    public Object peekBack() {
        return this.inStack.peek();
    }

    /**
     * Returns true if the queue is empty
     *
     * @return true if the queue is empty
     */
    public boolean isEmpty() {
        return (this.inStack.isEmpty() && this.outStack.isEmpty());
    }

}

/**
 * This class is the example for the Queue class
 *
 * @author sahilb2 (https://www.github.com/sahilb2)
 *
 */
public class QueueUsingTwoStacks {

    /**
     * Main method
     *
     * @param args Command line arguments
     */
    public static void main(String args[]){
        QueueWithStack myQueue = new QueueWithStack();
        myQueue.insert(1);
        System.out.println(myQueue.peekBack()); //Will print 1
        // instack: [(top) 1]
        // outStack: []
        myQueue.insert(2);
        System.out.println(myQueue.peekBack()); //Will print 2
        // instack: [(top) 2, 1]
        // outStack: []
        myQueue.insert(3);
        System.out.println(myQueue.peekBack()); //Will print 3
        // instack: [(top) 3, 2, 1]
        // outStack: []
        myQueue.insert(4);
        System.out.println(myQueue.peekBack()); //Will print 4
        // instack: [(top) 4, 3, 2, 1]
        // outStack: []

        System.out.println(myQueue.isEmpty()); //Will print false

        System.out.println(myQueue.remove()); //Will print 1
        System.out.println(myQueue.peekBack()); //Will print NULL
        // instack: []
        // outStack: [(top) 2, 3, 4]

        myQueue.insert(5);
        System.out.println(myQueue.peekFront()); //Will print 2
        // instack: [(top) 5]
        // outStack: [(top) 2, 3, 4]

        myQueue.remove();
        System.out.println(myQueue.peekFront()); //Will print 3
        // instack: [(top) 5]
        // outStack: [(top) 3, 4]
        myQueue.remove();
        System.out.println(myQueue.peekFront()); //Will print 4
        // instack: [(top) 5]
        // outStack: [(top) 4]
        myQueue.remove();
        // instack: [(top) 5]
        // outStack: []
        System.out.println(myQueue.peekFront()); //Will print 5
        // instack: []
        // outStack: [(top) 5]
        myQueue.remove();
        // instack: []
        // outStack: []

        System.out.println(myQueue.isEmpty()); //Will print true

    }
}

LANGUAGE:

DARK MODE: