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

剑指-Offer 2021-11-24 20:43:59 2021-11-24 21:32:30 52 次浏览

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/