Stack - Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Input: ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]
Output: [null, null, null, 2, 2, false]
Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Solution 1 - Implementation of stack using one queue

In this approach, we are going to implement a Stack datastructure using a single Queue, as we know stack works in LIFO (last in first out) order, but the queue works in FIFO (first in first out) order. So, we will implement a stack operations as follows:

push(int x): we will add the element x to the queue.
pop(): we will go through stack elements from 1.....n-1 and remove these elements from top, and add it back to the stack. Say if the stack looks like this 1, 2, 3, .., .., then after after popping n-1 elements and add it back, it looks like this 3, 2, 1, .., .., now we can simply pop the first element from the queue, it returns 1, note that pop() operation will also remove and return the element.
top(): this operation is similar to pop(), except at the end, we will make a peek() operation on queue, it returns the first element from the queue, but will not remove it.
empty(): we will simply call queue.isEmpty(), this returns true is the queue is empty, false otherwise.

import java.util.Deque; import java.util.LinkedList; public class StackUsingQueue { final Deque<Integer> queue; public StackUsingQueue() { queue = new LinkedList<>(); } public void push(int x) { queue.push(x); } public int pop() { for(int i=0; i<queue.size()-1; i++) { queue.push(queue.pop()); } return queue.pop(); } public int top() { for(int i=0; i<queue.size()-1; i++) { queue.push(queue.pop()); } return queue.peek(); } public boolean empty() { return queue.isEmpty(); } public static void main(String[] args) { StackUsingQueue stackUsingQueue = new StackUsingQueue(); stackUsingQueue.push(3); stackUsingQueue.push(2); stackUsingQueue.push(1); System.out.println("top : " + stackUsingQueue.top()); System.out.println(stackUsingQueue.pop()); System.out.println(stackUsingQueue.pop()); System.out.println(stackUsingQueue.pop()); System.out.println(stackUsingQueue.empty()); } }

Complexity Analysis:

Time complexity: In this implementation push(int x) and empty() runs in constant time, and pop() and top() runs in O(n) time, because we are iterating through stack to move the elements from the beginning to the end of queue.
Space complexity: O(n).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: