栈

栈的基本概念

栈是一种特殊的线性结构，总在栈尾处增加（push）或删除（pop）元素，是典型的LIFO数据结构。

img

在Java中的使用

​ 在java中栈是Vector的一个子类，正是由于这个原因Stack继承了Vector的所有方法，并可以在任意位置添加或删除元素。这种能力无疑是破坏了栈这种数据结构的封装性。由于这种原因官方推荐使用Deque（双端队列）接口来代替栈的功能，但是双端队列可以双端操作，还是会破坏栈这种数据结构的封装性。但是这是历史遗留问题。现在工程中可以自己封装一个真正的栈来使用。

image-20231225213124369
操作 成功 失败
push void void
pop 栈顶元素 NoSuchElementException
peek 栈顶元素 空返回null 
// 1. 初始化队列
Deque<Integer> stack = new ArrayDeque<>();
// 2. 入栈
stack.push(1);
// 3. 查看栈顶元素
System.out.println(stack.peek());
// 4. 出栈
System.out.println(stack.pop());
System.out.println(stack.peek());// 空返回null
System.out.println(stack.pop()); // 空抛出异常NoSuchElementException

队列

队列的基本概念

队列是一种特殊的线性结构，总在队列头删除（dequeue）元素，队列结尾插入（enqueue）元素，是典型的FIFO数据结构。

img

在Java中的使用

分类

  1. 单向队列（Queue）：只能在一端插入数据，在另一端删除数据。
  2. 双向队列（Deque）：每一端都可以进行插入数据和删除数据的操作。
  3. 优先级队列：优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

java类图

image-20231226110249047

队列常用操作

操作 功能 结果
add 添加一个元素 如果队列已满，则抛出一个
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回null
peek 返回队列头部的元素 如果队列为空则返回null
poll 移除并返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素 如果队列为空，则阻塞

Queue接口

image-20231226113239001

public class Queue_ {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        // 添加元素
        queue.offer(1);
        // 获取队首元素，如果没有返回null
        System.out.println(queue.peek());
        // 获取队首元素并删除，如果没有返回null
        System.out.println(queue.poll());
    }
}

Deque接口

image-20231226235105641

PriorityQueue类

优先队列，底层使用堆实现

参考

Java 程序员，别用 Stack？！_工作中会用到stack类么-CSDN博客

队列 & 栈 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

搞懂Java中的队列以及使用场景 - 掘金 (juejin.cn)