栈与队列理论基础

代码随想录

https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

stack:栈 后进先出
queue: 队列 先进先出

使用

Deque

【Java】Java双端队列Deque使用详解
菜鸟教程 Java Deque 接口
Java Deque 手册
Java Deque接口 使用方法(栈、队列、双端队列)

初始化

1
2
3
Deque<String> Deque1 = new ArrayDeque<>();

Deque<String> Deque2 = new LinkedList<>();

Why is ArrayDeque better than LinkedList

Deque接口可以实现 栈、队列、双端队列 的功能,虽然功能很丰富,但是使用时一定要格外小心。

接口的实现类
实现了这个接口的类有两个:ArrayDequeLinkedList
ArrayDeque 不支持 null,出现null将会抛出异常
例如:@throws NullPointerException if the specified element is null and this deque does not permit null elements
使用情景:
频繁的插入、删除操作 或 未知的初始数量:LinkedList
频繁的随机访问操作:ArrayDeque

下表总结了上述 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()

PriorityQueue

Java PriorityQueue(优先队列)

Stack

【java】栈(Stack)的基本使用
菜鸟教程 Java Stack 类
PriorityQueue常用方法

1
2
3
4
5
6
7
8
9
10
11
import java.util.Stack;	//引用栈
//初始化
Stack<Integer> stack = new Stack<Integer>();
//进栈
stack.push(Element);
//出栈
stack.pop();
//取栈顶值(不出栈)
stack.peek();
//判断栈是否为空
stack.isEmpty()

注:Java堆栈 Stack类 已经过时,Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法:push()、pop()、peek()。
JAVA 栈,为什么要使用Deque,而不推荐使用Stack,Deque中ArrayDeque与LinkedList的区别,Deque方法详解

Queue

【java】队列(Queue)的基本使用
【Java】Java队列Queue使用详解
菜鸟教程 Java 实例 - 队列(Queue)用法

压入元素(添加):add()、offer()
相同:未超出容量,从队尾压入元素,返回压入的那个元素。
区别:在超出容量时,add()方法会对抛出异常,offer()返回false

弹出元素(删除):remove()、poll()
相同:容量大于0的时候,删除并返回队头被删除的那个元素。
区别:在容量为0的时候,remove()会抛出异常,poll()返回false

获取队头元素(不删除):element()、peek()
相同:容量大于0的时候,都返回队头元素。但是不删除。
区别:容量为0的时候,element()会抛出异常,peek()返回null。

抛出异常 返回特殊值 队列可能阻塞
插入 add(e) offer(e) put(e)
删除 remove() poll() take()
检查 element() peek()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Queue;	//引用队列
import java.util.LinkedList;
//初始化
Queue<Integer> queue = new LinkedList<Integer>();
//增加一个元素
queue.add(value);//如果队列已满,则抛出一个IIIegaISlabEepeplian异常
queue.offer(value);//如果队列已满,则返回false
queue.put(value);//如果队列满,则阻塞
//移除并返回队列头部的元素
queue.remove(); //如果队列为空,则抛出一个NoSuchElementException异常
queue.poll(); // 如果队列为空,则返回null
queue.take();//如果队列为空,则阻塞
//返回队列头部的元素
queue.element();//如果队列为空,则抛出一个NoSuchElementException异常
queue.peek();//如果队列为空,则返回null
//判断队列是否为空
queue.isEmpty()

栈与队列理论基础
http://yuanql.top/2023/07/03/02_leetcode/栈与队列理论基础/
作者
Qingli Yuan
发布于
2023年7月3日
许可协议