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

    
        标签：
        
            剑指 Offer
        
    发布于：2021-11-24 20:43:59
    编辑于：2021-11-24 21:32:30
    浏览量：937

概述

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

直接法

两个栈，栈一拿来装数据，压入时直接压入即可；弹出时先将数据装入栈二，拿到最后一个值后再将数据从栈二中挨个取回。

插入操作 O(1)，删除操作 O(n)。

class CQueue {
public:
    stack<int> a;
    stack<int> b;

    CQueue() {

    }
    
    void appendTail(int value) {
        a.push(value);
    }
    
    int deleteHead() {
        if (a.empty()) return -1;
        int last = -1;
        while (!a.empty()) {
            last = a.top();
            a.pop();
            b.push(last);
        }
        b.pop();
        while (!b.empty()) {
            a.push(b.top());
            b.pop();
        }
        return last;
    }
};

改进方法

栈一只负责入，栈二只负责出，当栈二为空时从栈一从获取其所有值。

插入操作 O(1)，删除操作当栈二中有值时 O(1)，无值时 O(n)，平均下来 O(1)。

class CQueue {
public:
    stack<int> a;
    stack<int> b;

    CQueue() {

    }
    
    void appendTail(int value) {
        a.push(value);
    }
    
    int deleteHead() {
        int last = -1;
        if (!b.empty()) {
            last = b.top();
            b.pop();
        } else {
            if (a.empty()) return -1;
            while (!a.empty()) {
                b.push(a.top());
                a.pop();
            }
            last = b.top();
            b.pop();
        }
        return last;
    }
};

Links: sword-offer-09