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

leetcode

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入： ["CQueue","appendTail","deleteHead","deleteHead","deleteHead"] [[],[3],[],[],[]] 输出：[null,null,3,-1,-1] 示例 2：

输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2] 提示：

1 <= values <= 10000 最多会对 appendTail、deleteHead 进行 10000 次调用 通过次数549,166提交次数780,078

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

叠栈法:
了解栈与队列的功能,\

• 栈是先入后出型数据
• 队列是先入先出型数据\

要用栈实现队列就是要将数据添加到栈底,做最后的输出

添加元素
因为是用两个栈来实现,我们可以令一个栈储存结果,另一个栈为临时的空栈,当数据添加的时候,将数据添加到空栈中,然后将结果栈的元素添加的临时栈中,新添加的元素就到了栈底,临时栈就变成了结果栈,结果栈变成空栈(临时),如果再添加元素就用相同的操作就可以了.
输出元素
直接从栈顶输出,然后指针后移就行了

比如这些数据1234要用队列的形式输入输出 1输入

2输入 结果

3输入

4输入

最后结果

输出的话就直接从栈顶依次输出就可以了

执行结果

法1

type CQueue struct {
 a1, a2 []int
}

func Constructor() CQueue {
 return CQueue{}
}

func (this *CQueue) AppendTail(value int) {
 this.a1 = append(this.a1, value)
 this.a2 = append(this.a2, this.a1...)
 this.a1 = nil
}

func (this *CQueue) DeleteHead() int {
 v := this.a2[0]
 this.a2 = this.a2[1:]
 return v
}

执行用时： 168 ms , 在所有 Go 提交中击败了 64.50% 的用户 内存消耗： 7.5 MB , 在所有 Go 提交中击败了 98.31% 的用户 通过测试用例： 55 / 55