栈、队列、双端队列、优先队列
程序员文章站
2024-02-11 13:48:58
...
文章目录
1 栈和队列
1.1 原理图
1.2 Stack & Queue 关键点
- Stack:先入后出;添加、删除皆为 O(1)
- Queue:先入先出;添加、删除皆为 O(1)
2 Deque: Double-End Queue
-
简单理解:两端可以进出的 Queue Deque - double ended queue
-
插入和删除都是 O(1) 操作
3 Stack、Queue、Deque 的工程实现
Java、Python、C++ 等已有基础实现 如何查询接口信息?如何使用?(Demo)
示例代码 - Stack
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack);
System.out.println(stack.search(4));
stack.pop();
stack.pop();
Integer topElement = stack.peek();
System.out.println(topElement);
System.out.println(" 3的位置 " + stack.search(3));
示例代码 - Queue
Queue<String> queue = new LinkedList<String>();
queue.offer("one");
queue.offer("two");
queue.offer("three");
queue.offer("four");
System.out.println(queue);
String polledElement = queue.poll();
System.out.println(polledElement);
System.out.println(queue);
String peekedElement = queue.peek();
System.out.println(peekedElement);
System.out.println(queue);
while(queue.size() > 0) {
System.out.println(queue.poll());
}
示例代码 - Deque
Deque<String> deque = new LinkedList<String>();
deque.push("a");
deque.push("b");
deque.push("c");
System.out.println(deque);
String str = deque.peek();
System.out.println(str);
System.out.println(deque);
while (deque.size() > 0) {
System.out.println(deque.pop());
}
System.out.println(deque);
Priority Queue
- 插入操作:O(1)
- 取出操作:O(logN) - 按照元素的优先级取出
- 底层具体实现的数据结构较为多样和复杂:heap、bst、treap
Java 的 PriorityQueue:
https://docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html
5 Stack 和 Queue 的实现(源码分析)
Stack: http://developer.classpath.org/doc/java/util/Stack-source.html
Queue: http://fuseyism.com/classpath/doc/java/util/Queue-source.html
Priority Queue: http://developer.classpath.org/doc/java/util/PriorityQueue-source.html
6 复杂度分析
7 小结
- Stack、Queue、Deque 的原理和操作复杂度
- PriorityQueue 的特点和操作复杂度
- 查询 Stack、Queue、Deque、PriorityQueue 的系统接口的方法
8 实战题目
预习题目
- https://leetcode-cn.com/problems/valid-parentheses/ - 最近相关性 —> 栈!
- https://leetcode-cn.com/problems/min-stack/
实战题目
- https://leetcode-cn.com/problems/largest-rectangle-in-histogram
- https://leetcode-cn.com/problems/sliding-window-maximum