225. Implement Stack using Queues

Description

Implement a stack using queues. The stack should support the standard stack operations: push, pop, top, and empty. The stack must be implemented such that each operation runs in O(1) amortized time, although some individual operations may take longer.

The push operation adds an element to the top of the stack. The pop operation removes and returns the top element. The top operation returns the top element without removing it. The empty operation checks whether the stack is empty.

Intuition

The intuition behind this problem is to mimic the Last-In-First-Out (LIFO) behavior of a stack using the First-In-First-Out (FIFO) behavior of a queue. By rotating the elements in the queue after each push operation, we can simulate the behavior of a stack.

Approach

1. Data Structure: Use a single queue to implement the stack. After each push operation, rotate the elements of the queue such that the last pushed element is always at the front of the queue. This way, pop and top operations can be performed directly on the front of the queue.
2. Push Operation: When pushing an element x, add it to the queue. Then, rotate the queue so that x moves to the front. This ensures that x will be the first element to be popped or accessed by the top operation.
3. Pop Operation: Simply remove the front element of the queue, which corresponds to the top of the stack.
4. Top Operation: Return the front element of the queue without removing it.
5. Empty Operation: Check if the queue is empty.

Complexity

Time Complexity:

• Push: O(n), where n is the number of elements in the queue. This is because, after inserting an element, all other elements need to be rotated.
• Pop: O(1), since we just remove the front element of the queue.
• Top: O(1), since we just access the front element of the queue.
• Empty: O(1), since checking if a queue is empty is an O(1) operation.

Space Complexity:

O(n), where n is the number of elements in the stack. This is the space used by the queue to store the elements.

Code

C++

class MyStack {
private:
    queue q;
    
public:
    MyStack() {
    }

    void push(int x) {
        q.push(x);
        for (int i = 0; i < q.size() - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int topElement = q.front();
        q.pop();
        return topElement;
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

// Usage:
// MyStack* obj = new MyStack();
// obj->push(x);
// int param_2 = obj->pop();
// int param_3 = obj->top();
// bool param_4 = obj->empty();

Python

class MyStack:

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

# Usage:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

Java

class MyStack {
    private Queue q;

    public MyStack() {
        q = new LinkedList<>();
    }

    public void push(int x) {
        q.offer(x);
        for (int i = 0; i < q.size() - 1; i++) {
            q.offer(q.poll());
        }
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}

// Usage:
// MyStack obj = new MyStack();
// obj.push(x);
// int param_2 = obj.pop();
// int param_3 = obj.top();
// boolean param_4 = obj.empty();

JavaScript

var MyStack = function() {
    this.q = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.q.push(x);
    for ( let i=0;i < this.q.length - 1;i++ ) {
this.q.push(this.q.shift());
    }
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    return this.q.shift();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.q[0];
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return this.q.length == 0
};

/** 
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */