用AI赚第一桶💰低成本搭建一套AI赚钱工具,源码可二开。 广告
队列是先进先出的数据结构,栈时先进后出的数据结构,可以使用栈和队列模拟彼此。 # 两个队列模拟栈 使用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(); } ~~~ ![](https://box.kancloud.cn/2016-06-07_575683c158b07.jpg) # 两个栈模拟队列 使用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++下不会有任何提示,程序正确。 ![](https://box.kancloud.cn/2016-06-07_575683c1698c5.jpg) 测试: ~~~ 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(); } ~~~ ![](https://box.kancloud.cn/2016-06-07_575683c17db72.jpg)