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

剑指 Offer 09. 用两个栈实现队列
思路
定义两个栈s1s2s1作为队尾,s2作为队头

对于入队,只要s1不满,就可以入队;
(这里好像并不考虑满不满的情况,
直接从s1入队s1.push(value)

对于出队,如果两个都为空,说明没有元素可出队,return -1
else
如果s1不为空,s2为空,则将s1的元素全部倒入s2中,此时s2不为空
如果s1为空,s2不为空,则直接从s2出队。
如果s1不为空,s2不为空,则直接从s2出队

class CQueue {
public:
    stack<int> s1, s2;
    CQueue() {

    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        // 两个空栈 出队失败
        if(s1.empty() && s2.empty()){
            return -1;
        }

        // s2为空,s1不为空,将s1的全部倒入s2,再从s2出队
        else if(!s1.empty() && s2.empty()){
            while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
            }
        }

        // 此时,s1已经空了(如果没执行else if,说明本来就是空的),直接从s2出队;
        int ans;
        ans = s2.top();
        s2.pop();
        return ans;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
上一篇:字节跳动Java岗6月9号一面经验分享


下一篇:[算法题打卡-1] 剑指 Offer 09. 用两个栈实现队列