232.用栈实现队列
#栈 2024-08-15 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MyQueue {  
public:  
    MyQueue() {}  
      
    void push(int x) {   // 将元素 x 推到队列的末尾  
        dataSrc.push(x);  
    }  
      
    int pop() { // 从队列的开头移除并返回元素  
        int val = peek();  
        dataTop.pop();  
        return val;  
    }  
      
    int peek() {    // 返回队首元素  
  
        if(dataTop.empty()){  
            while(!dataSrc.empty()){  
                dataTop.push(dataSrc.top());  
                dataSrc.pop();  
            }  
        }  
  
        return dataTop.top();  
    }  
      
    bool empty() {  
        if(dataTop.empty() && dataSrc.empty()) return true;  
        return false;  
    }  
private:  
    stack<int> dataSrc;  
    stack<int> dataTop;  
};

这里面巧妙的地方在于，返回队首元素时：

  • 如果 dataTop 不为空就返回对应的 top 即可
  • 如果 dataTop 为空，就把 dataSrc 全部转移到 dataTop 中即可，返回对应的 top 之后，并不需要把 dataTop 中的元素返回到 dataSrc 中（我记得第一次做这道题是这么搞的，其实可以被这样优化）