hongyangwu

主题

栈、队列 ​

栈 ​

先进后出 ​

时间复杂度 ​

添加、删除：O(1)

查找：O(n)

代码 ​

java
Stack<Integer> stack = new Stack<>();

// 测试堆栈是否为空，返回 Boolean
stack.empty();
// 查看栈顶对象
stack.peek();
// 弹出栈顶对象
stack.pop();
// 向栈顶添加对象
stack.push(Object o);
// 查看对象的下标
stach.search(Object o);

单调栈 ​

  1. 单调栈分为单调递增栈和单调递减栈

    • 单调递增栈即栈内元素保持单调递增的栈
    • 同理单调递减栈即栈内元素保持单调递减的栈

  2. 操作规则（下面都以单调递增栈为例）

    • 如果新的元素比栈顶元素大，就入栈
    • 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

  3. 加入这样一个规则之后，会有什么效果

    • 栈内的元素是递增的

    • 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素

      假设现在索引在 6 ，栈里是 1 5 6

      接下来新元素是 2 ，那么 6 需要出栈

      当 6 出栈时，右边 2 代表是 6 右边第一个比 6 小的元素

    • 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

      当 6 出栈时，5 成为新的栈顶，那么 5 就是 6 左边第一个比 6 小的元素

  4. 代表题目：柱状图中最大的矩形

队列 ​

先进先出 ​

时间复杂度 ​

添加、删除：O(1)

查找：O(n)

代码 ​

java
Queue<String> queue = new LinkedList<String>();

// 向队尾添加对象
queue.offer(Object o);
// 查看队首对象
queue.peek();
// 弹出队首对象
queue.poll();

双端队列 ​

队首队尾都可以插入删除 ​

时间复杂度 ​

添加、删除：O(1)

查找：O(n)

代码 ​

java
// 基于数组实现的线性双向队列
Deque<String> deque = new ArrayDeque<>();
// 基于链表实现的链式双向队列
Deque<String> deque = new LinkedList<>();

// 向队头插入元素，如果插入成功返回true，否则返回false
deque.offerFirst(Object o);
// 向队尾插入元素，如果插入成功返回true，否则返回false
deque.offerLast(Object o);
// 返回并移除队头元素，如果队列无元素，则返回null
deque.pollFirst();
// 返回并移除队尾元素，如果队列无元素，则返回null
deque.pollLast();
// 获取队头元素但不移除，如果队列无元素，则返回null
deque.peekFirst();
// 获取队尾元素但不移除，如果队列无元素，则返回null
deque.peekLast();

经典题目 ​

  1. 窗口滑动最大值

优先队列 ​

自定义排序的单向队列 ​

时间复杂度 ​

添加、删除：O(1)

查找：O(logn)

代码 ​

java
Comparator<Integer> comparator = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
};
Queue<Integer> queue = new PriorityQueue<>(comparator);

// 有 Queue 上的所有方法
// 如果此队列包含指定的元素，则返回 true 
queue.contains(Object o);
// 从此队列中删除指定元素的单个实例（如果存在）
queue.remove(Object o);

底层具体实现的数据结构较为多样和复杂：堆、二叉搜索树、treap

Copyright © 2021-2024 hongyangwu