我们知道，stack和queue是C++中常见的container。下面，我们来探究下如何以stack来实现queue，以及如何用queue来实现stack。
首先，先了解下stack与queue的基本属性。
一、stack
1，参数要求
stack模板类需要两个参数：一个元素类型，一个容器类型。容器类型缺省为deque。
2，基本操作
入栈：s.push(element);element加入栈顶。
出栈：s.pop()，栈顶元素被删除，无返回值。
访问栈顶：s.top()。取得栈顶元素。
判断栈空：s.empty()。栈空，返回true；非空，返回false。
长度判断：s.size()。返回栈张元素个数
二、queue
1，参数要求
queue模板类需要两个参数：一个元素类型，一个容器类型。容器类型缺省为deque。
2，基本操作
入队：q.push(element)。element加入到队列的末端。
出对：q.pop()。弹出（删除）队列的第一个元素（q.front()）。无返回值。
访问队首：q.front(), 即最早被压入队列的元素。
访问队尾：q.back(),即最后被压入队列的元素。
判断队空：q.empty()。队空，返回true。
长度判断：q.size()。返回队列中元素个数。
三、两个stack实现queue
在基本了解了stack和queue这两个container后，我们来看看如何用stack实现queue。
如上所诉，queue包含了push(), pop(),front(),back(),empty()这些基本操作，现在的问题 就是如何用stack实现这些操作。
1,分析（已知stack A 和stack B）
入队：将元素进栈A
出队：判断B是否为空，如果为空，则将栈A中所有元素pop, 并push进 栈B，栈B出栈。
访问队首：栈B的栈顶。
访问队尾：如果栈A非空，队尾即栈A的栈顶（A.top()）;如果栈A为空，队尾为栈B的栈底（怎么取得栈B的栈底？利用第三个stack？？）
队空：两个栈空，则队空。
长度：A.size(), B.size()
2,示意代码（未实现back()）
class Stack2queue {
public:
void push(int node) {
stack1.push(node);
}
void pop() {
if (stack2.empty()) {
if (stack1.empty())
throw runtime_error("No elements");
else {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
stack2.pop();
}
}else
stack2.pop();
}
int front() {
if (stack2.empty()) {
if (stack1.empty())
throw runtime_error("No elements");
else {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
return stack2.top();
}
}else
return stack2.top();
}
bool myEmpty() {
if (stack1.empty() && stack2.empty())
return true;
else
return false;
}
private:
stack<int> stack1;
stack<int> stack2;
};
示意代码中未实现back()操作，笔者的想法是：若栈A为空，将stack B的元素pop出来，再push进 stack C。C的栈顶元素即是队尾。但是这样就新增了一个stack。不知道给广大博友是否有更好的方法？
四、两个queue实现stack
1，分析（queue A 和 queue B）
入栈：将元素push进队列A
出栈：判断队列A是否为空。空，则把队列B的元素出队列，进队列A，A再出队列进队列B，直到A中元素剩1，然后A.pop();非空，队列A中元素出队列进队列B，直到A中元素剩1，然后A.pop().
访问栈顶：与出栈类似，只不过由A.pop()B变为了A.front()或A.back(), 因为此时A只剩下一个元素。
判断栈空：queue1.empty() && queue2.empty()
长度：queue1.size() + queue2.size()
2，示意代码
class Queue2stack {
public:
void push(int);
void pop();
int top();
bool myempty();
private:
queue<int> queue1;
queue<int> queue2;
};
void Queue2stack::push(int element) {
queue1.push(element);
}
void Queue2stack::pop() {
if(!queue1.empty()) {
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
queue1.pop();
}
else {
if(!queue2.empty()) {
while (!queue2.empty()) {
queue1.push(queue2.front());
queue2.pop();
}
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
queue1.pop();
}
}
}
int Queue2stack::top() {
if(!queue1.empty()) {
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
return queue1.back();
}
else {
if(!queue2.empty()) {
while (!queue2.empty()) {
queue1.push(queue2.front());
queue2.pop();
}
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
return queue1.back();
}
}
throw runtime_error("No elements!");
}
bool Queue2stack::myempty() {
if(queue1.empty() && queue2.empty())
return true;
else
return false;
}
五、综合测试
上述讨论，介绍了stack和queue的相互实现。下面这个例子来检测我们的算法是否正确。
#include <iostream>
#include <stack>
#include <queue>
using namespace std; class Stack2queue {
public:
void push(int node) {
stack1.push(node);
} void pop() {
if (stack2.empty()) {
if (stack1.empty())
throw runtime_error("No elements");
else {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
stack2.pop();
} }else
stack2.pop();
}
int front() {
if (stack2.empty()) {
if (stack1.empty())
throw runtime_error("No elements");
else {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
return stack2.top();
} }else
return stack2.top();
} bool myEmpty() {
if (stack1.empty() && stack2.empty())
return true;
else
return false;
}
private:
stack<int> stack1;
stack<int> stack2;
}; class Queue2stack {
public:
void push(int);
void pop();
int top();
bool myempty();
private:
queue<int> queue1;
queue<int> queue2;
};
void Queue2stack::push(int element) {
queue1.push(element);
} void Queue2stack::pop() {
if(!queue1.empty()) {
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
queue1.pop(); }
else {
if(!queue2.empty()) {
while (!queue2.empty()) {
queue1.push(queue2.front());
queue2.pop();
}
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
queue1.pop();
} }
} int Queue2stack::top() {
if(!queue1.empty()) {
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
return queue1.back(); }
else {
if(!queue2.empty()) {
while (!queue2.empty()) {
queue1.push(queue2.front());
queue2.pop();
}
while(queue1.size() > ) {
queue2.push(queue1.front());
queue1.pop();
}
return queue1.back();
}
}
throw runtime_error("No elements!"); } bool Queue2stack::myempty() {
if(queue1.empty() && queue2.empty())
return true;
else
return false;
}
int main()
{
// stack to queue
Stack2queue s2q;
for (int i = ; i < ; ++i) {
s2q.push(i);
}
while (!s2q.myEmpty()) {
cout << s2q.front() << ' ';
s2q.pop();
} //queue to stack
cout << endl;
Queue2stack q2s;
for (int i = ; i < ; ++i) {
q2s.push(i);
}
while(!q2s.myempty()) {
cout << q2s.top() << ' ';
q2s.pop();
}
//system("pause");
return ;
}
实验结果：
我们看到，我们很好的用stack模拟了queue，达到了先进先出的效果；同样，我们也很好的用queue模拟了stack，先进后出的效果。
不过，值得考虑的是，笔者在用stack实现queue时，没有实现back()操作。各位博友有啥好想法呢？