Implement the following operations of a stack using queues.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- empty() -- Return whether the stack is empty.
不用多想,可以使用两个queue来实现,代码如下
耗时在pop上
class Stack {
public:
// Push element x onto stack.
void push(int x) {
que1.push(x);
} // Removes the element on top of the stack.
void pop() {
while (que1.size() > )
{
que2.push(que1.front());
que1.pop();
}
que1.pop();
while (!que2.empty())
{
que1.push(que2.front());
que2.pop();
}
} // Get the top element.
int top() {
return que1.back();
} // Return whether the stack is empty.
bool empty() {
return que1.empty();
}
private:
queue<int> que1;
queue<int> que2;
};
查看其它人的代码,发现居然可以使用一个queue来实现,实现思路非常巧妙,每一次push操作都将queue之前的元素都移到后面,使其保持栈的排序
如:
push 1
1
push 2
2 1
push 3
3 2 1
class Stack {
public:
queue<int> que;
// Push element x onto stack.
void push(int x) {
que.push(x);
for (int i = ; i<que.size() - ; ++i) {
que.push(que.front());
que.pop();
}
} // Removes the element on top of the stack.
void pop() {
que.pop();
} // Get the top element.
int top() {
return que.front();
} // Return whether the stack is empty.
bool empty() {
return que.empty();
}
};