Powered By GitBook
225.Implement Stack Using Queues

225.Implement Stack Using Queues

难度:Easy
使用队列实现栈的下列操作:
1
push(x) -- 元素 x 入栈
2
pop() -- 移除栈顶元素
3
top() -- 获取栈顶元素
4
empty() -- 返回栈是否为空
5
注意:
6
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
7
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
8
你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。
Copied!
由于队列是FIFO,栈是LIFO,所以需要两个队列来实现栈的功能:
1
class MyStack {
2
private:
3
queue<int> a;
4
queue<int> b;
5
public:
6
/** Initialize your data structure here. */
7
MyStack() {
8
9
}
10
11
/** Push element x onto stack. */
12
void push(int x) {
13
if(a.empty())
14
{
15
b.push(x);
16
}
17
else
18
{
19
a.push(x);
20
}
21
}
22
23
/** Removes the element on top of the stack and returns that element. */
24
int pop() {
25
int tmp;
26
if(a.empty())
27
{
28
tmp=b.back();
29
int s=b.size();
30
while(s-- >1)
31
{
32
a.push(b.front());
33
b.pop();
34
}
35
b.pop();
36
}
37
else
38
{
39
tmp=a.back();
40
int s=a.size();
41
while(s-->1)
42
{
43
b.push(a.front());
44
a.pop();
45
}
46
a.pop();
47
}
48
//cout<<a.size()<< "+"<<b.size()<<endl;
49
50
return tmp;
51
}
52
53
/** Get the top element. */
54
int top() {
55
if(a.empty())
56
return b.back();
57
58
else
59
return a.back();
60
}
61
62
/** Returns whether the stack is empty. */
63
bool empty() {
64
return a.empty() && b.empty() ;
65
}
66
};
67
68
/**
69
* Your MyStack object will be instantiated and called as such:
70
* MyStack* obj = new MyStack();
71
* obj->push(x);
72
* int param_2 = obj->pop();
73
* int param_3 = obj->top();
74
* bool param_4 = obj->empty();
75
*/
Copied!
运行结果:
成功 执行用时 : 8 ms, 在Implement Stack using Queues的C++提交中击败了96.69% 的用户 内存消耗 : 8.9 MB, 在Implement Stack using Queues的C++提交中击败了34.06% 的用户
Last modified 2yr ago
Copy link