题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]

题解

本题考查基本数据结构栈和队列

栈

栈是一种运算受限的线性表，仅能在表尾进行插入（入栈）和删除（出栈）；可运算的表尾被称之为栈顶，相对的表首称之为栈底

栈的操作类似于往箱子里装书，装（入栈）的越多，先装的就越在下面；拿（出栈）的时候，只能先拿最近装（入栈）的

队列

队列是一种运算受限的线性表，仅能在表尾进行插入（入队），表首进行删除（出队）；进行插入的端称为队尾，进行删除的端称为队首

队列的操作类似在食堂排队打饭，新来的同学只能排在队伍的末尾（入队），排在前面的打完才轮到后面的同学（出队）

思路

根据栈先进后出的特性，要实现队列先进先出的特性，需要先全部出栈，再按出栈的顺序入栈，此时再出栈即为先进先出

示例
入栈：A B C D E，此时栈顶为E
出栈：E D C B A
入栈：E D C B A，此时栈顶为A
出栈：A B C D E

成员变量：

• 维护两个栈，分别用来进行入队（inStack）和出队（outStack）操作

初始化：

• 初始化inStack和outStack为空

入队：

• inStack入栈

出队：

• outStack为空，将inStack元素全部出栈，并插入outStack
• outStack非空，outStack出栈
• outStack为空，返回-1

代码

type CQueue struct {
	inStack  []int // 入队-栈
	outStack []int // 出队-栈
}

func Constructor() CQueue {
	return CQueue{
		inStack:  make([]int, 0),
		outStack: make([]int, 0),
	}
}

func (this *CQueue) AppendTail(value int) {
	this.inStack = append(this.inStack, value)
}

func (this *CQueue) DeleteHead() int {
	var value int = -1
	// 出队-栈为空且入队-栈有元素
	if len(this.outStack) == 0 && len(this.inStack) > 0 {
		// 入队-栈=>出队-栈
		for i := len(this.inStack) - 1; i >= 0; i-- {
			this.outStack = append(this.outStack, this.inStack[i])
		}
		// 清空入队-栈
		this.inStack = make([]int, 0)
	}

	// 出队
	if len(this.outStack) > 0 {
		value = this.outStack[len(this.outStack)-1]
		this.outStack = this.outStack[0 : len(this.outStack)-1]
	}
	return value
}