剑指 Offer 09. 用两个栈实现队列

思路

代码实现

 1 class CQueue {
 2 private:
 3     stack<int> s1;  //用于插入
 4     stack<int> s2;  //用于删除
 5 public:
 6     CQueue() {
 7         
 8     }
 9     
10     void appendTail(int value) {
11         s1.push(value);
12     }
13     
14     int deleteHead() {
15         if(s2.empty()) {
16             if(s1.empty()) {
17                 return -1;
18             } else {
19                 while(!s1.empty()) {
20                     s2.push(s1.top());
21                     s1.pop();
22                 }
23                 
24                 int x = s2.top();
25                 s2.pop();
26                 return x;
27             }
28         } else {
29             int x = s2.top();
30             s2.pop();
31             return x;
32         }
33     }
34 };
35 
36 /**
37  * Your CQueue object will be instantiated and called as such:
38  * CQueue* obj = new CQueue();
39  * obj->appendTail(value);
40  * int param_2 = obj->deleteHead();
41  */

复杂度分析

参考

用两个栈实现队列-LeetCode官方

面试题09. 用两个栈实现队列（清晰图解）