本文共 1271 字，大约阅读时间需要 4 分钟。

用两个栈实现一个队列：

• 实现添加appendTail（在队列尾部插入整数）与删除deleteHead（在队列头部删除整数）函数的功能；
• 若队列中没有元素，deleteHead 操作返回-1；

题解分析

队列是先进先出，而栈是先进后出；为了能使队列移除头部元素，就需要保证栈顶元素是最先进入的元素：

• 使用双队列：一个存放正常入队的元素的input，另外一个存放倒序元素（从第一个出栈，再入栈即为倒序）的output；
• 入队：直接加入栈input即可；
• 出队：若output不为空，则弹出栈顶元素；否则，若input为空返回-1，不为空则经input中元素放入output中（一个个从input出栈，然后入栈output），再弹出栈顶元素；

复杂度：

• 时间：appendTail，直接入栈input，所以为O(1)；deleteHead需要把N个元素倒序，在O(N)级别；
• 空间：最差也是所有元素在栈中，即O(N)；

代码实现

golang中没有默认的stack库，使用切片模拟（只在尾部插入与删除）：

• 插入时用append；
• 删除时通过切片操作实现；

队列定义：

type CQueue struct {
   	Input  []int	Output []int}

在使用队列前，需要先通过Constructor构造出队列：

func Constructor() CQueue {
   	//instance := new(CQueue)	instance := CQueue{
   		Input:  make([]int, 0),		Output: make([]int, 0),	}	return instance}func (this *CQueue) AppendTail(value int) {
   	this.Input = append(this.Input, value)}func (this *CQueue) DeleteHead() int {
   	if len(this.Output) == 0 {
   		for index := len(this.Input) - 1; index >= 0; index-- {
   			this.Output = append(this.Output, this.Input[index])		}		this.Input = this.Input[:0]	}	size := len(this.Output)	if size == 0 {
   		return -1	}	result := this.Output[size-1]	this.Output = this.Output[:size-1]	return result}func TestQueue() {
   	qu := Constructor()	qu.AppendTail(1)	qu.AppendTail(2)	fmt.Println(qu.DeleteHead())}

转载地址：http://qwilf.baihongyu.com/