225. Implement Stack using Queues

LeetCode 225. Implement Stack using Queues

Description

Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (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 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.

Example 1:

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 such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer. You can use more than two queues.

Tags

Stack, Design

Solution

Here we only use a single queue to implement the stack.

• Push: push x into the queue, then pop and push all other elements;

• Pop: same as the queue's pop;

• Top: return the value of the front element of the queue;

• Empty: return the equality of the length of queue and 0.

Complexity

• Time complexity: $O(n)$ for Push; $O(1)$ for others;

• Space complexity: $O(n)$

Code

type MyStack struct {
	q []int
}

// Constructor initialize your data structure here. */
func Constructor() MyStack {
	return MyStack{make([]int, 0, 100)}
}

// Push element x onto stack. */
func (this *MyStack) Push(x int) {
	n := len(this.q)
	this.q = append(this.q, x)
	for i := 0; i < n; i++ {
		this.q = append(this.q, this.q[0])
		this.q = this.q[1:]
	}
}

// Pop removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
	val := this.q[0]
	this.q = this.q[1:]
	return val
}

// Top get the top element. */
func (this *MyStack) Top() int {
	return this.q[0]
}

// Empty returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
	return len(this.q) == 0
}

Reference

1. 用队列实现栈