[Lc]面试题09用两个栈实现队列

题目

题解

腾讯的客户端开发就是面的这个。。。，当时还想了半天幸苦想出来了，可惜还是凉

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

1. 快存慢取

这个方法存的时候特别快，取得时候比较慢
存的时候
直接加入s1

取的时候

• 若s2中有数，从s2的顶取数；
• 若没数，把s1中的数全部挨个压入s2中，再取数

class CQueue {
    stack<int> s1;
    stack<int> s2;
public:
    CQueue() {
    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if(s2.empty()){
            while(!s1.empty()){
                int tmp = s1.top();
                s2.push(tmp);
                s1.pop();
            }
        }
        if(s2.empty()) return -1;
        int res = s2.top();s2.pop();
        return res;        
    }
};

2. 慢存快取

这个方法刚好反过来，顾名思义。
存的过程

1. 存的时候先看s1有没有数
   • 若有，则全部按顺序取出放到s2；
   • 否则执行下一步
2. 压入value
3. 看s2中有没有数（即第一步放过去的）
   • 若有，全部按顺序放入s1
   • 没有，不操作

取的过程

1. 取的时候直接从最上面取，注意判断s1是不是为空 、

class CQueue {
    stack<int> s1;
    stack<int> s2;
public:
    CQueue() {}
    
    void appendTail(int value) {
        while(!s1.empty()){
            s2.push(s1.top());s1.pop();
        }
        s1.push(value);
        while(!s2.empty()){
            s1.push(s2.top());s2.pop();
        }
    }
    
    int deleteHead() {
        if(s1.empty()) return -1;
        int res = s1.top();s1.pop();
        return res;
    }
};

两个队列模拟一个栈

这个问题只有一个方法，慢存快取
存的时候

1. 挨个取出q1的数放入q2
2. 存入valse
3. 挨个取出q2的数放入q1
   取的时候
   直接从队首取值