我们知道，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()）
1 class Stack2queue { 2 public: 3 void push(int node) { 4 stack1.push(node); 5 } 6 7 void pop() { 8 if (stack2.empty()) { 9 if (stack1.empty()) 10 throw runtime_error("No elements"); 11 else { 12 while (!stack1.empty()) { 13 stack2.push(stack1.top()); 14 stack1.pop(); 15 } 16 stack2.pop(); 17 } 18 19 }else 20 stack2.pop(); 21 } 22 int front() { 23 if (stack2.empty()) { 24 if (stack1.empty()) 25 throw runtime_error("No elements"); 26 else { 27 while (!stack1.empty()) { 28 stack2.push(stack1.top()); 29 stack1.pop(); 30 } 31 return stack2.top(); 32 } 33 34 }else 35 return stack2.top(); 36 } 37 38 bool myEmpty() { 39 if (stack1.empty() && stack2.empty()) 40 return true; 41 else 42 return false; 43 } 44 private: 45 stack<int> stack1; 46 stack<int> stack2; 47 };
示意代码中未实现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，示意代码
1 class Queue2stack { 2 public: 3 void push(int); 4 void pop(); 5 int top(); 6 bool myempty(); 7 private: 8 queue<int> queue1; 9 queue<int> queue2; 10 }; 11 void Queue2stack::push(int element) { 12 queue1.push(element); 13 } 14 15 void Queue2stack::pop() { 16 if(!queue1.empty()) { 17 while(queue1.size() > 1) { 18 queue2.push(queue1.front()); 19 queue1.pop(); 20 } 21 queue1.pop(); 22 23 } 24 else { 25 if(!queue2.empty()) { 26 while (!queue2.empty()) { 27 queue1.push(queue2.front()); 28 queue2.pop(); 29 } 30 while(queue1.size() > 1) { 31 queue2.push(queue1.front()); 32 queue1.pop(); 33 } 34 queue1.pop(); 35 } 36 37 } 38 } 39 40 int Queue2stack::top() { 41 if(!queue1.empty()) { 42 while(queue1.size() > 1) { 43 queue2.push(queue1.front()); 44 queue1.pop(); 45 } 46 return queue1.back(); 47 48 } 49 else { 50 if(!queue2.empty()) { 51 while (!queue2.empty()) { 52 queue1.push(queue2.front()); 53 queue2.pop(); 54 } 55 while(queue1.size() > 1) { 56 queue2.push(queue1.front()); 57 queue1.pop(); 58 } 59 return queue1.back(); 60 } 61 } 62 throw runtime_error("No elements!"); 63 64 } 65 66 bool Queue2stack::myempty() { 67 if(queue1.empty() && queue2.empty()) 68 return true; 69 else 70 return false; 71 }
五、综合测试
上述讨论，介绍了stack和queue的相互实现。下面这个例子来检测我们的算法是否正确。
1 #include <iostream> 2 #include <stack> 3 #include <queue> 4 using namespace std; 5 6 class Stack2queue { 7 public: 8 void push(int node) { 9 stack1.push(node); 10 } 11 12 void pop() { 13 if (stack2.empty()) { 14 if (stack1.empty()) 15 throw runtime_error("No elements"); 16 else { 17 while (!stack1.empty()) { 18 stack2.push(stack1.top()); 19 stack1.pop(); 20 } 21 stack2.pop(); 22 } 23 24 }else 25 stack2.pop(); 26 } 27 int front() { 28 if (stack2.empty()) { 29 if (stack1.empty()) 30 throw runtime_error("No elements"); 31 else { 32 while (!stack1.empty()) { 33 stack2.push(stack1.top()); 34 stack1.pop(); 35 } 36 return stack2.top(); 37 } 38 39 }else 40 return stack2.top(); 41 } 42 43 bool myEmpty() { 44 if (stack1.empty() && stack2.empty()) 45 return true; 46 else 47 return false; 48 } 49 private: 50 stack<int> stack1; 51 stack<int> stack2; 52 }; 53 54 class Queue2stack { 55 public: 56 void push(int); 57 void pop(); 58 int top(); 59 bool myempty(); 60 private: 61 queue<int> queue1; 62 queue<int> queue2; 63 }; 64 void Queue2stack::push(int element) { 65 queue1.push(element); 66 } 67 68 void Queue2stack::pop() { 69 if(!queue1.empty()) { 70 while(queue1.size() > 1) { 71 queue2.push(queue1.front()); 72 queue1.pop(); 73 } 74 queue1.pop(); 75 76 } 77 else { 78 if(!queue2.empty()) { 79 while (!queue2.empty()) { 80 queue1.push(queue2.front()); 81 queue2.pop(); 82 } 83 while(queue1.size() > 1) { 84 queue2.push(queue1.front()); 85 queue1.pop(); 86 } 87 queue1.pop(); 88 } 89 90 } 91 } 92 93 int Queue2stack::top() { 94 if(!queue1.empty()) { 95 while(queue1.size() > 1) { 96 queue2.push(queue1.front()); 97 queue1.pop(); 98 } 99 return queue1.back(); 100 101 } 102 else { 103 if(!queue2.empty()) { 104 while (!queue2.empty()) { 105 queue1.push(queue2.front()); 106 queue2.pop(); 107 } 108 while(queue1.size() > 1) { 109 queue2.push(queue1.front()); 110 queue1.pop(); 111 } 112 return queue1.back(); 113 } 114 } 115 throw runtime_error("No elements!"); 116 117 } 118 119 bool Queue2stack::myempty() { 120 if(queue1.empty() && queue2.empty()) 121 return true; 122 else 123 return false; 124 } 125 int main() 126 { 127 // stack to queue 128 Stack2queue s2q; 129 for (int i = 1; i < 10; ++i) { 130 s2q.push(i); 131 } 132 while (!s2q.myEmpty()) { 133 cout << s2q.front() << ' '; 134 s2q.pop(); 135 } 136 137 //queue to stack 138 cout << endl; 139 Queue2stack q2s; 140 for (int i = 1; i < 10; ++i) { 141 q2s.push(i); 142 } 143 while(!q2s.myempty()) { 144 cout << q2s.top() << ' '; 145 q2s.pop(); 146 } 147 //system("pause"); 148 return 0; 149 }
实验结果：
我们看到，我们很好的用stack模拟了queue，达到了先进先出的效果；同样，我们也很好的用queue模拟了stack，先进后出的效果。
不过，值得考虑的是，笔者在用stack实现queue时，没有实现back()操作。各位博友有啥好想法呢？