分享程序员开发的那些事...
更新时间：2022-08-22 08:46:19
3.5 实现一个MyQueue类，该类用两个栈来实现一个队列。
队列是先进先出的数据结构(FIFO)，栈是先进后出的数据结构(FILO)， 用两个栈来实现队列的最简单方式是：进入队列则往第一个栈压栈， 出队列如果第二个栈不为空，则直接从第二个栈出队列，否则将第一个栈的数据依次压入第二个栈，然后出栈。每次有数据进入队列，直接进入第一个栈； 每次有数据出队列，在第二个栈不为空时直接从第二个栈出队。
C++实现代码：
#include<iostream> #include<stack> using namespace std; class MyQueue { private: stack<int> s1; stack<int> s2; public: void push(int x) { s1.push(x); } void pop() { if(s1.empty()&&s2.empty()) return; if(s2.empty()&&!s1.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } s2.pop(); } else s2.pop(); } int front() { if(s1.empty()&&s2.empty()) return 0; if(!s2.empty()) return s2.top(); while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } return s2.top(); } int size() { return s1.size()+s2.size(); } bool empty() { return s1.empty()&&s2.empty(); } }; int main() { MyQueue q; for(int i=0; i<10; ++i) { q.push(i); } cout<<q.front()<<endl; q.pop(); q.push(10); cout<<q.front()<<endl; cout<<q.size()<<" "<<q.empty()<<endl; return 0; }