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

[yankewei]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

解答

这个题不难，但是有一个前提就是需要用两个栈实现队列，一般情况下，实现队列只需一个数组即可，可以实现先进先出。但是栈的特性我们都知道，是后进先出。
我们可以使用两个栈，一个in用来进栈，一个out用来出栈。
当我们push元素的时候直接添加到in的栈顶即可。
当我们pop元素的时候如果我们的out中还有元素，可以直接取栈顶的元素，否则out中没有元素了，我们可以获取in的栈顶元素push到out中，直到in中没有元素了。执行完之后out的栈顶元素就是in的栈底元素，最后把out的栈顶元素弹出即可。

package main

import "fmt"

type CQueue struct {
    pushStack []int
    popStack  []int
}

func Constructor() CQueue {
    return CQueue{
	pushStack: []int{},
	popStack:  []int{},
    }
}

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

func (this *CQueue) DeleteHead() int {
    ret := -1
    pushLen := len(this.pushStack)
    popLen := len(this.popStack)
    if pushLen == 0 && popLen == 0 {
	return ret
    }
    if popLen == 0 {
	for len(this.pushStack) > 0 {
	    index := len(this.pushStack) - 1
	    value := this.pushStack[index]
	    this.pushStack = this.pushStack[:index]
	    this.popStack = append(this.popStack, value)
	}
    }
    popLen = len(this.popStack)
    ret = this.popStack[popLen-1]
    this.popStack = this.popStack[:popLen-1]
    return ret
}

func main() {
    obj := Constructor()
    obj.AppendTail(1)
    obj.AppendTail(2)
    obj.AppendTail(3)
    obj.AppendTail(4)
    fmt.Println(obj.DeleteHead())
    fmt.Println(obj.DeleteHead())
    obj.AppendTail(5)
    fmt.Println(obj.DeleteHead())
    fmt.Println(obj.DeleteHead())
    fmt.Println(obj.DeleteHead())
    fmt.Println(obj.DeleteHead())
}