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

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

题目如下

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead *** 作返回 -1 )
示例 1：
输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]

---

首先我相信很多同学看到这道题目时候和我初识这题一样，一脸懵逼根本看不懂题目的意思，更是无从解题。

我来给大家解读一下这道题目的意义。

1.题目解读

appendTail 和 deleteHead 是两种方法，他们分别的作用是
appendTail 方法是在队列尾部插入整数
deleteHead 方法是在队列头部删除整数
我们要编写appendTail 和 deleteHead方法具体代码实现方法。

---

Q1:其中题目要求输入[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”] [[],[3],[],[]]和其中出现的CQueue是什么意思？

Q2:为什么会输出[null,null,3,-1]？

A1:[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]这4个引号里面的都是方法。
需要计算机从左到右执行这4个方法。
其中CQueue也是一种方法，创建一个CQueue对象。
[[],[3],[],[]]表示着我们需要给方法传入的参数。其中只有appendTail方法需要我们传参进入方法,其余的[]表示不需要传参（传入空参）。

A2:[null,null,3,-1]表示返回值，4个方法被执行，会返回4个返回值。
CQueue为创建队列，返回值为null
appendTail为在队列尾部插入整数，为一个添加动作，无返回值，返回值为null
deleteHead为在队列头部删除整数，为一个删除动作，将刚刚appendTail方法传参3给删除掉，并且返回删除的值3
接着deleteHead继续删除栈底的元素，但是没有元素了，根据题目要求，所以返回-1

---

2.题目解法

这里我使用java汇编语言进行解答，代码中的注解详细梳理了我的解答过程

//创建2个栈stack1和stack2
class CQueue {
    linkedList stack1;
	linkedList stack2;

//实现队列
	public CQueue() {
		stack1 = new linkedList<>();
		stack2 = new linkedList<>();
	}

//向队列中尾部添加整数
	public void appendTail(int value) {
		stack1.add(value);
	}

//从队列中头部删除整数
	public int deleteHead() {
	//如果stack2队列是空的，返回值为1
		if (stack2.isEmpty()) {
			if (stack1.isEmpty()) return -1;
			while (!stack1.isEmpty()) {
			//如果队列stack1不是空的，那么重复执行向队列stack2添加stack1被删除的整数
				stack2.add(stack1.pop());
			}
			return stack2.pop();
				//如果stack2队列不是空的，则返回队列stack2删除值
		} else return stack2.pop();
	}
}

此题没有使用官方使用Stack的方式来做这道题
Stack会造成速度较慢； 原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用linkedList来做Stack的容器，因为linkedList实现了Deque接口，所以Stack能做的事linkedList都能做，其本身结构是个双向链表，扩容消耗少。

测试结果

时间复杂度为o(4)