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

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 09.用两个栈实现队列。

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

二、题目解析

我用大白话来翻译一下 示例 2

["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
这个表示每一次操作的集合数组
[[],[],[5],[2],[],[]]
这个表示每一次操作后对应的参数的集合数组

1、CQueue

首先初始化,没有参数,所以是 [],然后我们注意到 CQueue() 函数是没有返回值的,用 null 来表示(不要问我为什么用 null 表示。。。)

2、deleteHead

删除操作,没有参数,所以是 [],根据题意若队列中没有元素,deleteHead 操作返回 -1 ,所以输出值为 -1

3、appendTail

插入操作,有参数,此时是 **5 **,并且 appendTail() 函数没有返回值的,用 null 来表示。

4、appendTail

插入操作,有参数,此时是 **2 **,并且 appendTail() 函数没有返回值的,用 null 来表示。

5、deleteHead

删除操作,没有参数,所以是 [],此时队列中有元素,先进入的是 5,后进入的是 2,根据队列 先进先出 的性质,元素 5 出列,所以返回值是 5

6、deleteHead

删除操作,没有参数,所以是 [],此时队列中有元素,只有元素 2,所以返回值是 2


基本上看完上面的大白话翻译就可以理解题意,解决问题也不难了。

入队操作

如果是栈的插入操作,那我们可以把元素都先插入到 stack1 中,也就实现了队列的 入队操作

出队操作

  • 当 stack2 中不为空时,直接操作,此时在 stack2 中的栈顶元素是最先进入队列的元素,返回该元素即可;
  • 如果 stack2 为空且 stack1 也为空,返回 -1;
  • 如果 stack2 为空且 stack1 不为空,首先需要把 stack1 中的元素逐个弹出并压入到 stack2 中,然后返回 stack2 的栈顶元素即可。

示例

三、动画描述

四、图片描述

面试题09. 用两个栈实现队列.003

面试题09. 用两个栈实现队列.004

面试题09. 用两个栈实现队列.005

面试题09. 用两个栈实现队列.006

面试题09. 用两个栈实现队列.007

面试题09. 用两个栈实现队列.008

面试题09. 用两个栈实现队列.009

面试题09. 用两个栈实现队列.010

面试题09. 用两个栈实现队列.011

面试题09. 用两个栈实现队列.012

面试题09. 用两个栈实现队列.013

面试题09. 用两个栈实现队列.014

面试题09. 用两个栈实现队列.015

面试题09. 用两个栈实现队列.016

面试题09. 用两个栈实现队列.017

面试题09. 用两个栈实现队列.018

面试题09. 用两个栈实现队列.019

面试题09. 用两个栈实现队列.020

面试题09. 用两个栈实现队列.021

面试题09. 用两个栈实现队列.022

面试题09. 用两个栈实现队列.023

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class CQueue {

    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

    public CQueue() {
        // 初始化 stack1 与 stack2
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }

    public void appendTail(int value) {
        // 直接将元素存放到 stack1 中
        stack1.addLast(value);
    }

    public int deleteHead() {
        // stack2 栈不为空,直接操作,返回 stack2 的栈顶元素
        if(!stack2.isEmpty()) {
           return stack2.removeLast(); 
        }
        // 走到这一步的时候,stack2 是为空的状态
        // 根据题意,当 stack1 为空时,直接返回 -1
        if(stack1.isEmpty()){
            return -1;   
        }
        // 将 stack1 中的元素依次倒序放入 stack2 中
        while(!stack1.isEmpty()){
            stack2.addLast(stack1.removeLast()); 
        }
        // 返回 stack2 的栈顶元素  
        return stack2.removeLast();
    }
}

六、复杂度分析

插入元素操作

  • 时间复杂度:O(N)。插入元素时,对于已有元素,每个元素都要弹出栈两次,压入栈两次,因此是线性时间复杂度。
  • 空间复杂度:O(N)。需要使用额外的空间存储已有元素。

删除元素操作

  • 时间复杂度:O(1)。判断元素个数和删除队列头部元素都使用常数时间。
  • 空间复杂度:O(1)。从第一个栈弹出一个元素,使用常数空间。

七、相关标签

  • 队列

发表评论

邮箱地址不会被公开。 必填项已用*标注