0%

[Leetcode]225. Implement Stack using Queues(C++)

题目描述

题目链接:225. 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 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.

例子

例子 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

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.

Note

  • 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

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.

解题思路

思路比较简单,由于栈是先入后出,因此每 push 一个元素我们要确保它在我们使用的 queue 的前面,因此只需要用一个临时 queuex 压入,然后依次压入我们维护的 queue 的元素,最后将临时 queue 与我们维护的 queue 交换即可;其他操作可以直接使用 queue 的相应操作,代码如下:

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
28
29
30
31
32
33
34
#include <queue>

class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {}

/** Push element x onto stack. */
void push(int x) {
std::queue<int> temp;
temp.push(x);
while (!ordered_.empty()) {
temp.push(ordered_.front());
ordered_.pop();
}
ordered_.swap(temp);
}

/** Removes the element on top of the stack and returns that element. */
int pop() {
int val = ordered_.front();
ordered_.pop();
return val;
}

/** Get the top element. */
int top() { return ordered_.front(); }

/** Returns whether the stack is empty. */
bool empty() { return ordered_.empty(); }

private:
std::queue<int> ordered_;
};
  • 时间复杂度:
    • push: O(n)
    • pop: O(1)
    • peek: O(1)
    • empty: O(1)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 225.ImplementStackUsingQueues.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions