LeetCode刷题计划-Day 1:栈与队列
文章目录
回顾栈与队列
栈是一种具有 「先入后出」 特点的抽象数据结构,可使用数组或链表实现。

队列是一种具有 「先入先出」 特点的抽象数据结构,可使用链表实现。

剑指 Offer 09. 用两个栈实现队列
问题描述:
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 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 次调用
解题思路:
Go官方库中没有栈的实现,不介意题干里使用两个栈的条件的话,可以直接重新切片来完成:
type CQueue struct { Items []int } func Constructor() CQueue { return CQueue{Items: []int{}} } func (this *CQueue) AppendTail(value int) { this.Items = append(this.Items, value) } func (this *CQueue) DeleteHead() int { if len(this.Items) == 0 { return -1 } del := this.Items[0] this.Items = this.Items[1:] return del } /** * Your CQueue object will be instantiated and called as such: * obj := Constructor(); * obj.AppendTail(value); * param_2 := obj.DeleteHead(); */先使用
container包中的list结构实现一个栈:import "container/list" type Stack struct { list *list.List } func NewStack() *Stack { list := list.New() return &Stack{list} } func (stack *Stack) Push(value interface{}) { stack.list.PushBack(value) } func (stack *Stack) Pop() interface{} { e := stack.list.Back() if e != nil { stack.list.Remove(e) return e.Value } return nil } func (stack *Stack) Peak() interface{} { e := stack.list.Back() if e != nil { return e.Value } return nil } func (stack *Stack) Len() int { return stack.list.Len() } func (stack *Stack) Empty() bool { return stack.list.Len() == 0 }额外维护一个辅助栈,
DeleteHead方法调用时,若辅助栈为空则将数据栈逆序转存到辅助栈中,不为空则直接Pop辅助栈并返回:func Constructor() CQueue { return CQueue{ data: *NewStack(), // 数据栈 aux: *NewStack(), // 辅助栈 } } func (this *CQueue) AppendTail(value int) { this.data.Push(value) } func (this *CQueue) DeleteHead() int { if this.aux.Empty() { if this.data.Empty() { return -1 } dataLen := this.data.Len() for i := 0; i < dataLen; i++ { this.aux.Push(this.data.Pop()) } } return this.aux.Pop().(int) } /** * Your CQueue object will be instantiated and called as such: * obj := Constructor(); * obj.AppendTail(value); * param_2 := obj.DeleteHead(); */
剑指 Offer 30. 包含 min 函数的栈
问题描述:
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.提示:
- 各函数的调用总次数不超过 20000 次
解题思路:
额外维护一个辅助栈,以非严格降序的方式保存当前数据栈中的最小值,出栈时两个栈同步Pop,防止最小值也不在数据栈中:
type MinStack struct { data Stack // 数据栈 aux Stack // 辅助栈 } /** initialize your data structure here. */ func Constructor() MinStack { return MinStack{ data: *NewStack(), aux: *NewStack(), } } func (this *MinStack) Push(x int) { this.data.Push(x) if this.aux.Empty() { this.aux.Push(x) } else if x <= this.aux.Peak().(int) { this.aux.Push(x) } else { this.aux.Push(this.aux.Peak()) } } func (this *MinStack) Pop() { this.data.Pop() this.aux.Pop() } func (this *MinStack) Top() int { return this.data.Peak().(int) } func (this *MinStack) Min() int { return this.aux.Peak().(int) } /** * Your MinStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.Min(); */
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论