用两个栈实现队列

发表于2022-01-20更新于2022-04-08阅读次数

一上一下

推理思路：
因为栈只能控制一头，而队列需要控制两头，所以需要两个栈。
一个栈控制队头，另一个栈控制队尾。就像把两个栈上下合并起来，组成一个两端开口的队列。
上面的栈控制队头，有删除队头的功能，下面的栈控制队尾，负责添加队尾元素。
只不过这样合并的栈有个问题，就是中间有层隔阂，为两个栈的栈底。那么对于删除头元素时，这层隔阂是有影响的，对于添加队尾元素无影响。
因为当我们删除头元素删到栈底时，但下面的栈还有元素，此时到栈底了却删不了。
那么很显然，当队头删除到栈底时，解决办法就是将下面栈的元素移到上面的栈里面即可。

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
class CQueue {
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        tail.push(value);
    }
    
    int deleteHead() {
        if(front.empty() && tail.empty())  return -1;
        if(front.empty()){
            while(!tail.empty()){
                front.push(tail.top());
                tail.pop();
            }
        }
        int dle=front.top();
        front.pop();
        return dle;
        
    }
private:
    stack<int> front,tail;
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */