今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题09. 用两个栈实现队列。
题目链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail
和 deleteHead
,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,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],[],[]]
这个表示每一次操作后对应的参数的集合数组
首先初始化,没有参数,所以是 []
,然后我们注意到 CQueue()
函数是没有返回值的,用 null 来表示(不要问我为什么用 null 表示。。。)
删除操作,没有参数,所以是 []
,根据题意若队列中没有元素,deleteHead
操作返回 -1
,所以输出值为 -1
。
插入操作,有参数,此时是 5,并且 appendTail()
函数没有返回值的,用 null 来表示。
插入操作,有参数,此时是 2,并且 appendTail()
函数没有返回值的,用 null 来表示。
删除操作,没有参数,所以是 []
,此时队列中有元素,先进入的是 5,后进入的是 2,根据队列 先进先出 的性质,元素 5 出列,所以返回值是 5 。
删除操作,没有参数,所以是 []
,此时队列中有元素,只有元素 2,所以返回值是 2 。
基本上看完上面的大白话翻译就可以理解题意,解决问题也不难了。
如果是栈的插入操作,那我们可以把元素都先插入到 stack1 中,也就实现了队列的 入队操作 。
示例
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();
}
}