225. Implement Stack using Queues
使用兩個隊列實現一個後進先出(LIFO)的堆疊。實現的堆疊應該支持所有正常堆疊的功能(推入、取頂、彈出和判空)。
實現 MyStack 類:
void push(int x)
:將元素 x 推入堆疊的頂部。int pop()
:移除堆疊頂部的元素並返回該元素。int top()
:返回堆疊頂部的元素。boolean empty()
:如果堆疊為空,返回 true;否則返回 false。
注意:
你只能使用隊列的標準操作,這意味著只能使用「後端推入」、「前端查看/彈出」、「查詢大小」和「判空」操作。
根據你使用的語言,隊列可能不原生支持。你可以使用列表或雙端隊列(deque)來模擬隊列,只要你只使用隊列的標準操作即可。
範例:
輸入["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出[null, null, null, 2, 2, false]
Python
from collections import deque
class MyStack:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x: int) -> None:
self.q2.append(x)
while self.q1:
self.q2.append(self.q1.popleft())
self.q1, self.q2 = self.q2, self.q1
def pop(self) -> int:
return self.q1.popleft()
def top(self) -> int:
return self.q1[0]
def empty(self) -> bool:
return len(self.q1) == 0
16.49MB, 36ms
C++
#include <queue>
class MyStack {
private:
std::queue<int> q1, q2;
public:
MyStack() {}
void push(int x) {
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
std::swap(q1, q2);
}
int pop() {
int top = q1.front();
q1.pop();
return top;
}
int top() {
return q1.front();
}
bool empty() {
return q1.empty();
}
};
8.52MB, 0ms
Javascript
class MyStack {
constructor() {
this.q1 = [];
this.q2 = [];
}
push(x) {
this.q2.push(x);
while (this.q1.length > 0) {
this.q2.push(this.q1.shift());
}
[this.q1, this.q2] = [this.q2, this.q1];
}
pop() {
return this.q1.shift();
}
top() {
return this.q1[0];
}
empty() {
return this.q1.length === 0;
}
}
49.05MB, 49ms