栈和队列

Narcissus 收录于算法学习

2021-10-05 约 2449 字预计阅读 5 分钟

队列是一种先进先出的数据结构，栈是一种先进后出的数据结构。这两种数据结构底层都是数组或者链表实现的，只是API限定了它们的特性。

栈实现队列

队列API如下：

思路

使用两个栈s1,s2就能实现一个队列的功能。

当调用push让元素入队时，只要把元素压入s1即可，例如push进三个元素分别是1、2、3，底层结构如下：

当调用pop或则peek时，按道理队头元素应该是1，但是在s1中1被压在栈底，就需要s2起到一个中转作用。

当s2为空时，可以把s1的所有元素取出再添加进s2，这时候s2中元素就是先进先出顺序了。

最后如何判断队列是否为空呢？如果两个栈都为空的话，说明队列为空。

代码实现

type MyQueue struct {
    S1, S2 []int
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    // S1做队尾，S2做队首
    var s1, s2 []int
    return MyQueue{
        S1: s1,
        S2: s2,
    }
}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.S1 = append(this.S1, x)
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    // 先调用peek保证S2非空
    topNum := this.Peek()
    this.S2 = this.S2[:len(this.S2) - 1]
    return topNum
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
    if len(this.S2) == 0 {
        // 将S1元素压入S2
        for len(this.S1) != 0 {
            this.S2 = append(this.S2, this.S1[len(this.S1) - 1])
            this.S1 = this.S1[:len(this.S1) - 1]
        }
    }
    return this.S2[len(this.S2) - 1]
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    return len(this.S1) == 0 && len(this.S2) == 0
}

时间复杂度分析

其他操作都是O(1)。只有peek操作，调用它时可能触发while循环，遮掩的话时间复杂度是O(N)。由于pop操作调用了peek,故时间复杂度和peek相同。故最坏时间复杂度是O(N),均摊时间复杂度是O(1)。

用队列实现栈

用队列实现栈就比较简单粗暴了，只需要一个队列作为底层数据结构。栈的API如下：

思路

pushAPI，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要top查看栈顶元素的话可以直接返回。

每次pop只能从队头取元素；但是栈是后进先出，也就是说popAPI要从队尾取元素。解决办法就是：把队列前面的都取出来再加入队尾，让之前队尾元素排到对头：

代码实现

type MyStack struct {
    Q1 []int
}

/** Initialize your data structure here. */
func Constructor() MyStack {
    var q1 []int
    return MyStack{
        Q1: q1,
    }
}

/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    size := len(this.Q1)
    this.Q1 = append(this.Q1, x)
    for ; size > 0; size-- {
        this.Q1 = append(this.Q1, this.Q1[0])
        this.Q1 = this.Q1[1:]
    }
}

/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    top_element := this.Q1[0]
    this.Q1 = this.Q1[1:]
    return top_element
}

/** Get the top element. */
func (this *MyStack) Top() int {
    return this.Q1[0]
}

/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    return len(this.Q1) == 0
}

单调栈

单调栈实际上就是栈，只是利用一些巧妙地逻辑，使得每次新元素入栈后，栈内的元素都保持有序。

1、下一个更大元素

通过单调栈实现，代码如下：

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    // 单调栈
    var stack []int
    numberPairMap := map[int]int{}
    for _, val := range nums2 {
        if len(stack) == 0 || stack[len(stack) - 1] > val {
            // 入栈
            stack = append(stack, val)
        } else {
            for len(stack) != 0 && stack[len(stack) - 1] < val {
                // 出栈
                top := stack[len(stack) - 1]
                stack = stack[: len(stack) - 1]
                numberPairMap[top] = val
            }
            stack = append(stack, val)
        }
    }
    // 依次出栈
    for len(stack) != 0 {
        // 出栈
        top := stack[len(stack) - 1]
        stack = stack[: len(stack) - 1]
        numberPairMap[top] = -1
    }

    for _, v := range nums1 {
        stack = append(stack, numberPairMap[v])
    }
    return stack
}

2、下一个更大元素II

本题难点是如何处理环形数组，处理环形数组一般有以下思路：

通过运算符%求模，获得环形特效。index % len(array)

func nextGreaterElements(nums []int) []int {
    // 单调栈
    // 为了方便，栈中存放元素索引而不存放元素
    var stack []int
    n := len(nums)
    result := make([]int, n)
    for i := 0; i < n; i++ {
        result[i] = -1
    }
    for i := 0; i < 2 * n; i++ {
        // 入栈
        if len(stack) == 0 || nums[stack[len(stack)-1]] >= nums[i%n] {
            stack = append(stack, i % n)
        } else {
            for len(stack) != 0 && nums[stack[len(stack)-1]] < nums[i%n] {
                // 出栈
                topIndex := stack[len(stack)-1]
                stack = stack[: len(stack) - 1]
                result[topIndex] = nums[i%n]
            }
            stack = append(stack, i % n)
        }
    }

    return result
}

可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。
为了方便将数据存入结果数组，单调栈中存放的是索引而不是元素。

3、去除重复字母

要找到字典序最小的串(删去中间任意字符)，可以使用单调栈。但这样不能保证每个字符出现仅出现一次。因此需要特殊处理：用哈希记录栈中出现字符（防止同一字符出现多次）；记录当前字符后面还有多少个相同字符（保证每个字符都出现一次），哈希表实现。

代码如下：

func removeDuplicateLetters(s string) string {
    // 单调栈
    var stack []byte
    inStack, freqChar := make([]int, 26), make([]int, 26)
    for _, v := range s {
        freqChar[int(v - 'a')]++
    }
    for i := 0; i < len(s); i++ {
        cur := s[i]
        // 如果栈中存在，不需要入栈
        if inStack[int(cur - 'a')] != 0 {
            freqChar[int(cur - 'a')]--
            continue
        }
        // 入栈
        if len(stack) == 0 || stack[len(stack) - 1] < cur {
            stack = append(stack, cur)
            inStack[int(cur - 'a')]++
        } else {
            // 出栈
            for len(stack) != 0 && stack[len(stack) - 1] > cur {
                last := stack[len(stack) - 1] 
                // 后面没有栈顶元素，这栈顶元素不需要出栈
                if freqChar[int(last- 'a')] == 0 {
                    break
                }
                inStack[int(last - 'a')]--
                stack = stack[: len(stack) - 1]
            }
            stack = append(stack, cur)
            inStack[int(cur - 'a')]++ 
        }
        freqChar[int(cur - 'a')]--
    }

    return string(stack)
}

单调队列

单调队列就是一个队列，只是使用了一些巧妙地方法，使得队列中的元素全都是单调的。

单调栈一般解决数据持续输入，求最值；单调队列一般解决数据不仅输入同时还会输出，求最值。

单调队列就能够在O(1)时间内得出最值。单调队列操作如下：

单调队列的实现

单调队列需要数据结构能够支持在头部和尾部进行插入和删除，采用双链表或者数组数据结构。

push方法依然在队尾添加元素，但是要把前面比自己小的元素都删除，代码如下：

如果每个元素加入时都执行这样的操作，最终单调队列中的元素大小会保持单调递减的顺序，则max方法代码如下：

pop方法在对头删除元素n，之所以要判断data.front() == n,是因为要删除的队头元素n可能已经被前面插入时删除了，这时就不用删除。代码如下：

完整单调队列实现代码：

// 单调队列数据结构
type MonotonicQueue struct {
    Queue []int
}

// 在队尾添加元素n
func (q *MonotonicQueue) push(n int) {
    // 将前面小于自己的元素都删除
    for len(q.Queue) != 0 && q.Queue[len(q.Queue) - 1] < n {
        q.Queue = q.Queue[: len(q.Queue) - 1]
    }
    q.Queue = append(q.Queue, n)
}

// 返回当前队列中的最大值
func (q *MonotonicQueue) max() int {
    return q.Queue[0]
}

// 队头元素如果是 n，删除它
func (q *MonotonicQueue) pop(n int) {
    if n == q.Queue[0] {
        q.Queue = q.Queue[1 :]
    }
}

滑动窗口中的最大值

代码如下：

func maxSlidingWindow(nums []int, k int) []int {
    // 单调队列
    var (
        window MonotonicQueue
        result []int
    )
    for i := 0; i < len(nums); i++ {
        if i < k - 1 {
            // 先填满窗口的前 k - 1
            window.push(nums[i])
        } else {
            // 窗口向前滑动，添加新元素
            window.push(nums[i])
            // 将当前窗口最大值加入结果数组
            result = append(result, window.max())
            // 移除旧数据
            window.pop(nums[i - k + 1])
        }
    }
    return result
}

// 单调队列数据结构
type MonotonicQueue struct {
    Queue []int
}

// 在队尾添加元素n
func (q *MonotonicQueue) push(n int) {
    // 将前面小于自己的元素都删除
    for len(q.Queue) != 0 && q.Queue[len(q.Queue) - 1] < n {
        q.Queue = q.Queue[: len(q.Queue) - 1]
    }
    q.Queue = append(q.Queue, n)
}

// 返回当前队列中的最大值
func (q *MonotonicQueue) max() int {
    return q.Queue[0]
}

// 队头元素如果是 n，删除它
func (q *MonotonicQueue) pop(n int) {
    if n == q.Queue[0] {
        q.Queue = q.Queue[1 :]
    }
}

复杂度分析

单独看push操作的复杂度确实不是O(1)，但是算法整体的复杂度依然是O(N)线性时间。要这样想，nums中的每个元素最多被push_back和pop_back一次，没有任何多余操作，所以整体的复杂度还是O(N)。空间复杂度就是窗口的大小O(k)。

目录

栈和队列

栈实现队列

思路

代码实现

时间复杂度分析

用队列实现栈

思路

代码实现

单调栈

1、下一个更大元素

2、下一个更大元素II

3、去除重复字母

单调队列

单调队列的实现

滑动窗口中的最大值

复杂度分析