栈和队列的相互模拟
最后更新于：2022-04-01 16:17:52
队列是先进先出的数据结构，栈时先进后出的数据结构，可以使用栈和队列模拟彼此。
# 两个队列模拟栈
使用C++泛型编程，队列使用STL的queue容器适配器。
主要思想：
两个队列模拟栈时，某时刻要么两个队列均为空，要么有一个队列为空。
（1）向栈中push时：如果两个队列均为空，将元素插入某个队列（这里假定插入队列1）；
如果某个队列不为空，将元素push到该队列中即可。
（2）从栈中pop时： 如果两个队列均为空，则函数返回即可；
如果某个队列不为空，将该队列的前n-1个元素出队，并依次插入另一个队列，再将最后一个元素pop（最后一个元素就是要）。
~~~
//test.h
#ifndef TEST_TEST_H
#define TEST_TEST_H
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
template <class T>
class Qstack {
private:
queue<T> queue1;
queue<T> queue2;
public:
void display(); //输出所有元素
void push(const T& value); //向栈中插入
void pop(); //从栈中弹出
};
template<typename T>
void Qstack<T>::display() {
if (queue1.size() > 0) {
queue<T> q1(queue1);
while (q1.size() > 0) {
cout << q1.front() << " ";
q1.pop();
}
}
if (queue2.size() > 0) {
queue<T> q2(queue2);
while (q2.size() > 0) {
cout << q2.front() << " ";
q2.pop();
}
}
cout << endl << endl;
}
//注意这里在类模板外定义其成员函数的写法
template<class T>
void Qstack<T>::push(const T& value) {
if (queue2.empty())
queue1.push(value);
else if (queue1.empty())
queue2.push(value);
else {}
}
//这里的pop操作返回void，当栈为空时什么也不做。
//这和STL中栈适配器pop操作行为一致
template<typename T>
void Qstack<T>::pop() {
if (queue1.size() > 0) {
while (queue1.size() > 1) {
queue2.push(queue1.front());
queue1.pop();
}
queue1.pop();
}
else if (queue2.size() > 0) {
while (queue2.size() > 1) {
queue1.push(queue2.front());
queue2.pop();
}
queue2.pop();
}
else {}
return;
}
#endif
~~~
测试：
~~~
#include "qstack.h"
using namespace std;
int main() {
Qstack<string> s;
s.push("1");
s.push("2");
s.push("3");
s.display();
s.pop();
s.display();
s.push("4");
s.push("5");
s.display();
s.pop();
s.display();
s.pop();
s.display();
}
~~~
# 两个栈模拟队列
使用C++泛型编程，栈使用STL的stack容器适配器。
主要思想：
与“两个队列模拟栈”不同：这个问题中，在某个状态下两个栈可能都不为空。
（1）向队列插入：一律插入stack1中。
（2）从队列取数：如果stack2不为空，直接从stack2中弹出一个元素；
如果stack2为空，那么将stack1中所有元素弹出并插入stack2，然后从stack2中pop一个。
~~~
template <typename T>
class CQueue
{
public:
void display();
// 在队列末尾添加一个结点
void appendTail(const T& node);
// 删除队列的头结点
void deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T>
void CQueue<T>::display() {
stack<T> sq1(stack1);
stack<T> sq2(stack2);
while (sq2.size() > 0) {
cout << sq2.top() << " ";
sq2.pop();
}
while (sq1.size() > 0) {
T data = sq1.top();
sq1.pop();
sq2.push(data);
}
while (sq2.size() > 0) {
cout << sq2.top() << " ";
sq2.pop();
}
cout << endl;
}
template<typename T>
void CQueue<T>::appendTail(const T& element)
{
stack1.push(element);
}
template<typename T>
void CQueue<T>::deleteHead()
{
if(stack2.size()<= 0)
{
while(stack1.size()>0)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if (stack2.size() > 0)
stack2.pop();
return;
}
~~~
《剑指offer》中deleteHead函数返回被删除的元素，我认为没必要，因为STL中queue队列的删除返回就是void。当对空queue进行pop操作时，在VS2010下运行时会提示下图所示内容，但是g++下不会有任何提示，程序正确。
测试：
~~~
int main() {
CQueue<int> cq;
cq.appendTail(1);
cq.appendTail(2);
cq.appendTail(3);
cq.appendTail(4);
cq.display();
cq.deleteHead();
cq.deleteHead();
cq.display();
cq.appendTail(5);
cq.appendTail(6);
cq.display();
}
~~~
