A common question from interviewers, in this tutorial we will take a look at how to implement a queue data structure by using the stack data structure. There are a couple of things that we need to understand about these data structures in order to come to a plausible solution. So, let us take a look at the stack data structure. Visualize a stack of books, we place one book on top of another and our stack grows in height. We call this a push. If we want to take a book from the stack we always take it from the top, this is called a pop. Below, we can see how that operates with a simple example. Starting off, the number 5 is pushed into the stack, followed by 4, 3 and 2. If we want a number from the stack, we can only take it from the top. So we would pop the number 2. If we continued to withdraw integers from our stack, our order would be 2, 3, 4, 5. In computer science, we have a brief description of what this data structures function is, which is LIFO, last in - first out. The last item that is placed in the stack is the first item drawn from the stack.

Stack Example

Queue Example

Now we come to the queue. A queue is meant to be thought of as a line. Imagine you are in line at a store, waiting to purchase an item. The customer that arrived first is the first customer to be taken care of. This structure follows a FIFO function, first in - first out. Inserting the data into the queue would be the same as the stack, however, when taking from the queue, our ordering would be 5, 4, 3, 2. So, how would we get a stack to have the same behavior?

Approach

The solution would involve using another stack. We will be using the java util package Stack that is included in Java. Stack 1 would be the stack used to push our elements into. Stack 2 would be our queue ordering. Our pop functionality would check if Stack 2 is empty. If Stack 2 is empty we would then iterate through stack 1 and push all the elements of stack 1 into stack 2. We would then pop what's in stack 2. The peek functionality would operate in almost the same fashion as pop. We will check if stack 2 is not empty. If that condition is satisfied, we can peek from stack 2. If stack 2 is empty, then we need to push all of stack 1 to stack 2. Below, we can see the same exercise but for two stacks.

Populate Stack 1

Populate Stack 2

Now, if we take from the top of the stack it would be in the same order as the queue! Below is the Java code that is being used.

                                
class StackToQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public StackToQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int element) {
        stack1.push(element);
    }

    public int pop() {
        if(stack2.isEmpty())
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        return stack2.pop();
    }

    public int peek() {
        if(!stack2.isEmpty())
            return stack2.peek();
        else
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}
                                
                                Code copied