剑指Offer之栈与队列专题

栈与队列专题

剑指Offer09.用两个栈实现队列

题目描述：

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

算法代码：

type CQueue struct {
    // 栈 A，用于添加元素
    stackA []int
    // 栈 B，用于取出元素
    stackB []int
}

// CQueue 的构造函数
func Constructor() CQueue {
    // 返回一个新的 CQueue
    return CQueue{}
}

// 往队列插入整数
func (this *CQueue) AppendTail(value int)  {
    // 在 stackA 的末尾追加 value
    this.stackA = append(this.stackA, value)
}

// 从队列取出整数并删除
func (this *CQueue) DeleteHead() int {
    // 如果 stackB 没有元素则从 stackA 中取出所有
    if len(this.stackB) == 0 {
        // 如果 stackA 里也没有元素，则队列为空返回 -1
        if len(this.stackA) == 0 {
            return -1
        }
        // 将 stackA 的所有元素转移到 stackB
        for len(this.stackA) > 0 {
            // 获取 stackA 最末尾元素的下标
            index := len(this.stackA) - 1
            // 获取 stackA 最末尾元素的值 value
            value := this.stackA[index]
            // 向 stackB 的末尾追加 value
            this.stackB = append(this.stackB, value)
            // 从 stackA 中裁剪出末尾元素
            this.stackA = this.stackA[:index]
        }
    }
    // 这时候表示 stackB 内已有元素
    // 获取 stackB 最末尾元素的下标
    index := len(this.stackB) - 1
    // 获取 stackB 最末尾元素的值 value
    value := this.stackB[index]
    // 从 stackB 中裁剪出末尾元素
    this.stackB = this.stackB[:index]
    // 返回 value
    return value
}


/**
 * Your CQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AppendTail(value);
 * param_2 := obj.DeleteHead();
 */

算法思路：

用两个栈来模拟队列先进先出的特性，栈A用来添加元素，栈B用来取出元素，取出元素通过将A栈中元素取出倒序添加进入B栈中实现，去掉栈B的栈首元素即为去掉栈A的栈底元素。

以此来模拟队列中的先进先出特性。

剑指Offer30.包含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 次

算法代码：

type MinStack struct {
    stack []int
    minstack []int

}


/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        minstack: []int{math.MaxInt64},
    }
}


func (this *MinStack) Push(x int)  {
    this.stack = append(this.stack , x)
    this.minstack = append(this.minstack , min(this.minstack[len(this.minstack) - 1] , x))
}


func (this *MinStack) Pop()  {
    
    this.minstack = this.minstack[:len(this.minstack) - 1]
    
    this.stack = this.stack[:len(this.stack) - 1]
}


func (this *MinStack) Top() int {
    return this.stack[len(this.stack) - 1]
}


func (this *MinStack) Min() int {
    return this.minstack[len(this.minstack) - 1]
}

func min(x int , y int )  int {
    if x >= y {
        return y
    }else {
        return x
    }
}

/**
 * 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();
 */

算法思路：

利用一个辅助栈来存放较小值，在辅助栈的栈顶总是为所有元素的最小值。

注意：

不能直接返回return MinStack{}

func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        minstack: []int{math.MaxInt64},
    }
}

当测试用例如下时：

["MinStack","push","push","push","top","pop","min","pop","min","pop","push","top","min","push","top","min","pop","min"]
[[],[2147483646],[2147483646],[2147483647],[],[],[],[],[],[],[2147483647],[],[],[-2147483648],[],[],[],[]]