Leetcode-面试题09-用两个栈实现队列

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

题目描述

• 用两个栈实现一个队列。

• 队列的声明如下，请实现它的两个函数appendTail和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

方法：两个栈实现队列

遇到的问题

• 栈无法实现队列的功能：栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈
• 双栈可以实现列表的倒序：

设有含三个元素的栈 
A = [1,2,3] 和空栈 B = []。
若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A = [] , B = [3,2,1]，即 栈 B 元素实现栈 A 元素倒序 。

• 利用栈B删除队首元素：倒序后，B执行出栈就相当于删除了A的栈底元素，即对应队首元素

算法：

• 题目只要求实现 加入队尾appendTail() 和 删除队首deleteHead() 两个函数的正常工作
  • 因此我们可以设计栈A用于加入队尾的操作，栈B用于将元素倒序，从而实现删除队首的元素。
  • 加入队尾appendTail() 将数字val加入到栈A即可
  • 删除队首deleteHead() 有以下三种情况
    • 栈B不为空：说明B中有已完成倒序的元素，因此直接返回B的栈顶元素
    • 栈B为空，A也为空：说明两个栈都为空，没有元素存在，返回-1
    • 栈B为空，A不为空：将栈A元素全部转移至栈B。实现元素的倒序，并返回栈B的栈顶元素

举个例子:

1. appendTail()

2. deleteHead()

代码实现

class CQueue{
    LinkedList<Integer> A,B;

    public CQueue(){
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

    // 入队操作，只需要在A栈最后添加元素即可
    public void appendTail(int value){
        A.addLast(value);
    }

    // 出队操作
    public int deleteHead(){
        // 1. 如果B不是空的，删除B的最后一个元素并返回
        if (!B.isEmpty()) return B.removeLast();
        // 2. 如果A空了，说明还没有入队，返回-1
        if (A.isEmpty()) return -1;
        // 3. 如果A不是空的，B不断添加A的栈顶（相当于B是A的倒序）
        while (!A.isEmpty()){
            B.addLast(A.removeLast());
        }
        // 删除B的最后一个元素返回即可
        return B.removeLast();
    }
}

复杂度分析：

• 时间复杂度：O(n) appendTail() 函数为O(1) ,deleteHead 要完成N个元素的倒序
• 空间复杂度 : O(n) 。 最差情况下 栈A 栈B共要保存n个元素

打赏