https://leetcode.cn/problems/implement-stack-using-queues/

题面

使用队列实现栈的下列操作：

  • push(x) – 元素 x 入栈
  • pop() – 移除栈顶元素
  • top() – 获取栈顶元素
  • empty() – 返回栈是否为空

注意:

  • 你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
  • 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

代码（使用一个单向队列实现）

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public:
	queue<int> que;
	MyStack() {}
	
	void push(int x) {
        que.push(x);
    }
	
	int pop() {
        int size = que.size();
        size--;
        while (size--) { // 将队列头部的元素（除了最后一个元素）重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序
        que.pop();
        return result;
    }

	int top() {
        return que.back();
    }

	bool empty() {
        return que.empty();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Queue<Integer> queue;

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

// 每offer一个数进来都重新排列，把这个数放到队列的队首
public void push(int x) {
    queue.offer(x);
    int size = queue.size();
    // 移动除了这个数的其他数
    while (size-- > 1)
        queue.offer(queue.poll());
}

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

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

public boolena empty() {
    return queue.isEmpty();
}