面试题9：用两个栈实现队列

题目：用两个栈实现队列功能

#include <iostream> #include <stack> using namespace std; template<class T> class MyQueue { private: stack<T> s1; stack<T> s2; public: MyQueue(){} ~MyQueue(){} void pushData(T val) { s1.push(val); } bool queueEmpty() { if (s1.empty() && s2.empty()) return true; else return false; } T popData() { T ret; if (queueEmpty()) return -1; if (s2.empty()) { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } } ret = s2.top(); s2.pop(); return ret; } }; int main() { MyQueue<int> q; for(int i = 0; i < 10; ++i) q.pushData(i); while (!q.queueEmpty()) cout << q.popData() << endl; }

题目：用两个队列实现一个栈

#include <iostream> #include <queue> using namespace std; template<class T> class MyStack { private: queue<T> q1; queue<T> q2; public: MyStack(){} ~MyStack(){} bool isEmpty() { if (q1.empty() && q2.empty()) return true; else return false; } void pushData(T val) { if (!q1.empty()) q1.push(val); else q2.push(val); } T popData() { T ret; if (!q1.empty()) { while (q1.size() > 1) { q2.push(q1.front()); q1.pop(); } ret = q1.front(); q1.pop(); } else { while (q2.size() > 1) { q1.push(q2.front()); q2.pop(); } ret = q2.front(); q2.pop(); } return ret; } }; int main() { MyStack<int> s; for (int i = 0; i < 10; ++i) { s.pushData(i); } while (!s.isEmpty()) cout << s.popData() << endl; }