可以知道栈是先进后出的，把元素先压进第一个栈，之后再把元素抛出，压进第二栈，从第二个栈抛出的元素满足先进先出的原则。
实现queue的push操作：直接把元素都压入第一个栈即可。
实现queue的pop操作：1：判断第二个栈是否有元素？2：若第二个栈有元素，抛出第二个栈的栈顶元素即可。3：若第二个栈没元素，把第一个栈的所有元素都压进第二个栈，再抛出第二个栈的栈顶元素。
实现queue的front操作：原理同pop操作，只要返回第二个栈的栈顶元素即可。
实现queue的back操作：返回第一个栈的栈顶元素即可，若第一个栈无元素，需要先把第二个栈的所有元素压进第一个栈，再返回第一个栈的栈顶元素。
参考代码：
template<typename T> class queue { private: stack<T>st1, st2; public: void push(T x); void pop(); T front(); T back(); int size(); bool empty(); }; template<typename T> int queue<T>::size() { return st1.size() + st2.size(); } template<typename T> bool queue<T>::empty() { return st1.empty() && st2.empty(); } template<typename T> void queue<T>::push(T x) { st1.push(x); } template<typename T> void queue<T>::pop() { if (st2.empty()) { while (!st1.empty()) { st2.push(st1.top()); st1.pop(); } } if (!st2.empty()) { st2.pop(); } } template<typename T> T queue<T>::front() { assert(!st1.empty() || !st2.empty()); if (st2.empty()) { while (!st1.empty()) { st2.push(st1.top()); st1.pop(); } } return st2.top(); } template<typename T> T queue<T>::back() { assert(!st1.empty() || !st2.empty()); if (st1.empty()) { while (!st2.empty()) { st1.push(st2.top()); st2.pop(); } } return st1.top(); }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。