栈和队列的相互模拟

深藏阁楼爱情的钟 2022-08-01 02:55 198阅读 0赞

队列是先进先出的数据结构，栈时先进后出的数据结构，可以使用栈和队列模拟彼此。

# 两个队列模拟栈 #

使用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();
    }

![Center][]

# 两个栈模拟队列 #

使用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++下不会有任何提示，程序正确**。

![Center 1][]

测试：

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();
    }

![Center 2][]

[Center]: /images/20220731/d75d8329a5e14e08a75558ed7d35242f.png
[Center 1]: /images/20220731/0433a14d27594cf69c5d7dbc3eb60ca0.png
[Center 2]: /images/20220731/bae6e18d5e8e43f48a3a12fc6751f523.png