栈与队列

基础知识

栈

灵魂四问：

C++中 stack，queue 是容器么？
我们使用的 stack，queue 是属于那个版本的 STL？
我们使用的 STL 中 stack，queue 是如何实现的？
stack，queue 提供迭代器来遍历空间么？

栈和队列是 STL（C++标准库）里面的两个数据结构，C++标准库是有多个版本的，要知道我们使用的 STL 是哪个版本，才能知道对应的栈和队列的实现原理。

三个最为普遍的 STL 版本：

HP STL 其他版本的 C++ STL，一般是以 HP STL 为蓝本实现出来的，HP STL 是 C++ STL 的第一个实现版本，而且开放源代码。
P.J.Plauger STL 由 P.J.Plauger 参照 HP STL 实现出来的，被 Visual C++编译器所采用，不是开源的。
SGI STL 由 Silicon Graphics Computer Systems 公司参照 HP STL 实现，被 Linux 的 C++编译器 GCC 所采用，SGI STL 是开源软件，源码可读性甚高。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。所以 STL 中栈往往不被归类为容器，而被归类为 container adapter（容器适配器）。

STL 中栈是用什么容器实现的？栈的底层实现可以是 vector，deque，list 都是可以的，主要就是数组和链表的底层实现。

我们常用的 SGI STL，如果没有指定底层实现的话，默认是以 deque 为缺省情况下栈的底层结构。

deque 是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

SGI STL 中队列底层实现缺省情况下一样使用 deque 实现的。

队列

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL 中队列一样是以 deque 为缺省情况下的底部结构。

STL 队列也不被归类为容器，而被归类为 container adapter（容器适配器）。

双端队列 Deque 解释

Deque 是一个双端队列接口，继承自 Queue 接口，Deque 的实现类是 LinkedList、ArrayDeque、LinkedBlockingDeque，其中 LinkedList 是最常用的。

Deque 有三种用途：

普通队列(一端进另一端出): Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出) Deque deque = new LinkedList()
堆栈 Deque deque = new LinkedList()

注意：Java 堆栈 Stack 类已经过时，Java 官方推荐使用 Deque 替代 Stack 使用。Deque 堆栈操作方法：push()、pop()、peek()。

Deque 是一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

下表总结了上述 12 种方法：

	第一个元素 (头部)	最后一个元素 (尾部)
	抛出异常	特殊值	抛出异常	特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

Deque 接口扩展(继承)了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

Queue 方法	等效 Deque 方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

堆栈方法	等效 Deque 方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

优先级队列

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下 priority_queue 利用 max-heap（大顶堆）完成对元素的排序，这个大顶堆是以 vector 为表现形式的 complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用 priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

232.用栈实现队列

力扣题目链接

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

解答：

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void push(int x) {
        stackIn.push(x);
    }

    public int pop() {
        dumpstackIn();
        return stackOut.pop();
    }

    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }

    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    private void dumpstackIn(){
        if(!stackOut.isEmpty()) return;
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }
    }
}

225. 用队列实现栈

力扣题目链接

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解答：

//两个 Queue 实现
class MyStack {

    Queue<Integer> queue1; // 和栈中保持一样元素的队列
    Queue<Integer> queue2; // 辅助队列

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queue_temp;
        queue_temp = queue1;
        queue1 = queue2;
        queue2 = queue_temp;
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

// 优化，使用一个 Queue 实现
class MyStack {

    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    ////每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
    public void push(int x) {
        queue.offer(x);
        int size = queue.size();

        while(size-- > 1){
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

20. 有效的括号

力扣题目链接

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

解答：

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque= new LinkedList<>();
        char[] ss = s.toCharArray();
        int len = ss.length;
        if(len%2 == 1) return false;
        for(char c : ss){
            if(c == '('){
                deque.push(')');
            } else if(c == '['){
                deque.push(']');
            } else if(c == '{'){
                deque.push('}');
            } else{
                if(deque.isEmpty() || c != deque.pop()) return false;
            }
        }
        return deque.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

力扣题目链接

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

解答：

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> deque = new LinkedList<>();
        char[] ss = s.toCharArray();
        for(char c : ss){
            if(!deque.isEmpty()){
                if(deque.peek() == c){
                    deque.pop();
                    continue;
                }
            }
            deque.push(c);
        }
        char[] res = new char[deque.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = deque.pollLast();
        }
        return new String(res);
    }
}

150. 逆波兰表达式求值

力扣题目链接

根据逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入: ["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]
输出: 22

解释:该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

解答：

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new LinkedList<>();
        int temp1 = 0, temp2 = 0;
        for(String c : tokens){
            if(c.equals("+")){
                temp1 = deque.pop();
                temp2 = deque.pop();
                deque.push(temp2 + temp1);
            } else if(c.equals("-")){
                temp1 = deque.pop();
                temp2 = deque.pop();
                deque.push(temp2 - temp1);
            } else if(c.equals("*")){
                temp1 = deque.pop();
                temp2 = deque.pop();
                deque.push(temp2 * temp1);
            } else if(c.equals("/")){
                temp1 = deque.pop();
                temp2 = deque.pop();
                deque.push(temp2 / temp1);
            } else {
                deque.push(Integer.valueOf(c));
            }
        }
        return deque.pop();
    }
}

239. 滑动窗口最大值

力扣题目链接

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值

进阶：

你能在线性时间复杂度内解决此题吗？

解答：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++){
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，因为出现大数时，数组中前面的小数就没用了
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
                deque.pollLast();
            }

            deque.offer(i);

            if(i >= k - 1){
                res[index++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

347.前 K 个高频元素

力扣题目链接

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 $O (n lo g n)$ , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

解答：

//基于大顶堆实现
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[k];
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);//lambda表达式，表达式为正时，右边的数先进队列，pair[1]在后面表示map的Value
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        for(int i = 0; i < k; i++){

            res[i] = pq.poll()[0];
        }
        return res;
    }
}

//基于小顶堆实现
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[k];
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(pq.size() < k){
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else{
                if(entry.getValue() > pq.peek()[1]){
                    pq.poll();
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        for(int i = 0; i < k; i++){
            res[i] = pq.poll()[0];
        }
        return res;
    }
}

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解答:

优先队列

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a-b);
        int len = 0;
        for(int i = 0; i < n; i++){
            len = pq.size();
            if(len < k){
                pq.add(nums[i]);
                continue;
            }

            if(pq.peek() >= nums[i]) continue;

            pq.remove();
            pq.add(nums[i]);
        }
        return pq.peek();
    }
}

复杂度分析：

时间复杂度： $O (n lo g k)$ ，每个元素最多进行一次堆操作；
空间复杂度： $O (k)$ ，「优先队列」的大小。

快速选择

import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        k = n - k

        def dfs(low: int, high: int) -> int:
            if low > high or low > k or high < k:
                return -1

            pi = self.partition(nums, low, high)
            if pi == k:
                return pi

            return max(dfs(pi+1, high), dfs(low, pi-1))

        return nums[dfs(0, n-1)]

    def partition(self, nums: List[int], low: int, high: int) -> int: # 快排思想
        temp = random.randint(low, high)
        pivot = nums[temp]
        nums[high], nums[temp] = nums[temp], nums[high]
        i, j = low, high-1
        while True:
            while i <= j and nums[i] < pivot:
                i += 1

            while i <= j and nums[j] > pivot:
                j -= 1

            if i > j:
                break

            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

        nums[i], nums[high] = nums[high], nums[i]
        return i

总结

在栈与队列系列中，我们强调栈与队列的基础。使用抽象程度越高的语言，越容易忽视其底层实现，而 C++相对来说是比较接近底层的语言。

我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。接着，通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用，以及使用技巧。通过求滑动窗口最大值，以及前 K 个高频元素介绍了两种队列：单调队列和优先级队列，这是特殊场景解决问题的利器。

其他

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

解答:

优先队列(Java),最小堆(Python)

class MedianFinder:

    def __init__(self):
        self.left = [] # 入堆的元素取相反数，变成最大堆, 放大数
        self.right = [] # 最小堆, 放小数

    def addNum(self, num: int) -> None:
        if len(self.left) == len(self.right):
            heappush(self.left, -heappushpop(self.right, num))
        else:
            heappush(self.right, -heappushpop(self.left, -num))

    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return -self.left[0]
        else:
            return (self.right[0] - self.left[0]) / 2.0

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

复杂度分析

时间复杂度：初始化和 findMedian 都是 $O (1)$ ，addNum 是 $O (lo g q)$ ，其中 q 是 addNum 的调用次数。每次操作堆需要 $O (lo g q)$ 的时间。

空间复杂度： $O (q)$ 。

二分法:

class MedianFinder:

    def __init__(self):
        self.lists = []
        self.n = 0

    def addNum(self, num: int) -> None:
        self.n += 1
        if self.n == 1:
            self.lists.append(num)
            return
        left, right = 0, self.n-2
        while left <= right:
            mid = left + (right - left) // 2
            if self.lists[mid] > num:
                right = mid - 1
            elif self.lists[mid] < num:
                left = mid + 1
            else:
                self.lists.insert(mid, num)
                return
        self.lists.insert(left, num)

    def findMedian(self) -> float:
        if (self.n & 1) == 0:
            return (self.lists[self.n//2] + self.lists[self.n//2-1]) / 2.0
        else:
            return self.lists[self.n//2] / 1.0

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

基础知识​

栈​

队列​

双端队列 Deque 解释​

Deque 有三种用途：​

优先级队列​

232.用栈实现队列​

225. 用队列实现栈​

20. 有效的括号​

1047. 删除字符串中的所有相邻重复项​

150. 逆波兰表达式求值​

239. 滑动窗口最大值​

347.前 K 个高频元素​

215. 数组中的第K个最大元素​

总结​

其他​

295. 数据流的中位数​

基础知识

栈

队列

双端队列 Deque 解释

Deque 有三种用途：

优先级队列

232.用栈实现队列

225. 用队列实现栈

20. 有效的括号

1047. 删除字符串中的所有相邻重复项

150. 逆波兰表达式求值

239. 滑动窗口最大值

347.前 K 个高频元素

215. 数组中的第K个最大元素

总结

其他

295. 数据流的中位数