LeetCode刷题计划-Day 1:栈与队列

回顾栈与队列

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

    Picture4png

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

    Picture5png

剑指 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 次调用
  • 解题思路:

    1. 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();
      */
    2. 先使用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();
     */

评论

暂无评论