一、Implement Stack using Queues
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.
Notes:
- You must use only standard operations of a queue -- which means only
push to back,peek/pop from front,size, andis emptyoperations are valid. - Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
- You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
分析：用（两个）队列实现栈
设置两个队列分别为1和2
（1）入栈：如果队列2当前有元素，而队列1为空（反之亦然），那么将需要入栈的元素放入队列1中，然后将队列2中的元素依次出队并入队到队列1中。（即要保证有一个队列是空的）
（2）出栈：将有元素（不为空）的队列出队即可-------如：
先将元素a插入队列1中 ，现在要将元素b入栈，则将b插入到队列2中然后将队列1中的a出队到队列2中，则队列2中的元素变为 b，a
这样队列1为空，现在要压入c， 则将c插入队列1中 ，依次将队列2中的b ，a出队并加入到队列1中 ，则队列1中的元素变为 c，b，a，而队列2为空
（保证一队列为空）
代码如下：
【两个队列】
class Stack {
public:
// Push element x onto stack.
queue<int> queue1;
queue<int> queue2;
void push(int x) {
if (queue1.empty())
{
queue1.push(x);
while(!queue2.empty()){
int tmp = queue2.front();
queue2.pop();
queue1.push(tmp);
}
}else{
queue2.push(x);
while(!queue1.empty()){
int tmp = queue1.front();
queue1.pop();
queue2.push(tmp);
}
}
}
// Removes the element on top of the stack.
void pop() {
if (!queue1.empty())
queue1.pop();
if (!queue2.empty())
queue2.pop();
}
// Get the top element.
int top() {
if (!queue1.empty())
return queue1.front();
if (!queue2.empty())
return queue2.front();
}
// Return whether the stack is empty.
bool empty() {
return queue1.empty() && queue2.empty();
}
};
其他解法：
【两个队列】用两个队列myStack，temp实现一个栈。push时把新元素添加到myStack的队尾。pop时把myStack中除最后一个元素外逐个添加到myStack中，然后pop掉myStack中的最后一个元素，然后注意记得myStack和temp，以保证我们添加元素时始终向temp中添加。
class Stack {
public:
// Push element x onto stack.
void push(int x) {
myStack.push(x);
}
// Removes the element on top of the stack.
void pop() {
std::queue<int> temp;
int len = myStack.size();
for(int i = 0; i < len - 1; i++) {
temp.push(myStack.front());
myStack.pop();
}
myStack = temp;
}
// Get the top element.
int top() {
if(myStack.size() != 0) return myStack.back();
}
// Return whether the stack is empty.
bool empty() {
if(myStack.size() == 0) return true;
else return false;
}
private:
std::queue<int> myStack;
};
或：
【两个队列】
class Stack {
queue<int> rev_q;
public:
// Push element x onto stack.
void push(int x) {
queue<int> temp_q;
temp_q.push(x);
while (!rev_q.empty()) {
temp_q.push(rev_q.front());
rev_q.pop();
}
rev_q = temp_q;
}
// Removes the element on top of the stack.
void pop() {
rev_q.pop();
}
// Get the top element.
int top() {
return rev_q.front();
}
// Return whether the stack is empty.
bool empty() {
return rev_q.empty();
}
};
【一个队列】---push时直接添加到队尾就好。pop和top时，把队列除最后一个元素外，逐个循环添加到队列的尾部。
class Stack {
public:
// Push element x onto stack.
void push(int x) {
unsigned int size = s.size();
this->s.push(x);
while (size--){
s.push(s.front());
s.pop();
}
}
// Removes the element on top of the stack.
void pop() {
s.pop();
}
// Get the top element.
int top() {
return s.front();
}
// Return whether the stack is empty.
bool empty() {
return s.empty();
}
private:
queue<int> s;
};
附注：队列queue的成员函数
- empty()判断队列空，当队列空时，返回true。
- size()访问队列中的元素个数。
- push()会将一个元素置入queue中。
- front()会返回queue内的第一个元素(也就是第一个被置入的元素)。
- back()会返回queue中最后一个元素(也就是最后被插入的元素)。
- pop()会从queue中移除一个元素。[1]
- 注意：pop()虽然会移除下一个元素，但是并不返回它，front()和back()返回下一个元素但并不移除该元素。
二、Implement Queue using Stacks
Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
Notes:
- You must use only standard operations of a stack -- which means only
push to top,peek/pop from top,size, andis emptyoperations are valid. - Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
分析：
class Queue {
public:
stack<int> stack1;
stack<int> stack2;
// Push element x to the back of queue.
void push(int x) {
stack1.push(x);
}
// Removes the element from in front of queue.
void pop(void) {
if(!stack2.empty()) stack2.pop();
else{
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
stack2.pop();
}
}
// Get the front element.
int peek(void) {
if(!stack2.empty()) return stack2.top();
else{
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
return stack2.top();
}
}
// Return whether the queue is empty.
bool empty(void) {
return stack1.empty() && stack2.empty();
}
};
注：stack2.push(stack1.top())中若写成 stack2.push(stack1.pop())则会出错：invalid use of void expression
或：
class Queue {
public:
stack<int> s1;
stack<int> s2;
// Push element x to the back of queue.
void push(int x) {
s1.push(x);
}
// Removes the element from in front of queue.
void pop(void) {
if(s1.empty())
return;
while(!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
s2.pop();
while(!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
// Get the front element.
int peek(void) {
if(s1.empty())
return -1;
while(!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
int t = s2.top();
while(!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
return t;
}
// Return whether the queue is empty.
bool empty(void) {
return s1.empty();
}
};
可参考其他解法：
我们做过一道相反的题目Implement Stack using Queues 用队列来实现栈。这道题颠倒了个顺序，起始并没有太大的区别，栈和队列的核心不同点就是栈是先进后出，而队列是先进先出，那么怎么用栈的先进后出的特性来表示出队列的先进先出呢？方法是：只要在插入元素的时候每次都从前面插入即可，即如果一个队列是1,2,3,4，那么就在栈中保存为4,3,2,1，那么返回栈顶元素1，即为队列的首元素。我们可以设置一个辅助栈tmp，把s的元素也逆着顺序存入tmp中，此时若加入新元素x，再把tmp中的元素倒回来。
代码如下：
class Queue {
public:
// Push element x to the back of queue.
void push(int x) {
stack<int> tmp;
while (!s.empty()) {
tmp.push(s.top());
s.pop();
}
s.push(x);
while (!tmp.empty()) {
s.push(tmp.top());
tmp.pop();
}
}
// Removes the element from in front of queue.
void pop(void) {
s.pop();
}
// Get the front element.
int peek(void) {
return s.top();
}
// Return whether the queue is empty.
bool empty(void) {
return s.empty();
}
private:
stack<int> s;
};