当前位置： 首页 > ops >正文

013【入门】队列和栈-链表、数组实现

ops 2025/7/18 5:19:19

🔍 队列和栈详解 | [数据结构]-[入门]-[基础组件]

▶ JDK8+ | ⏱️ 操作时间复杂度 O(1)

核心应用场景

  1. 队列应用场景

    • 任务调度系统：操作系统进程调度、线程池任务分配
    • 消息队列：分布式系统中的异步消息传递
    • 缓冲区管理：生产者-消费者模式的数据缓冲
    • 广度优先搜索：图算法和树的层序遍历

  2. 栈应用场景

    • 函数调用栈：程序执行时的方法调用管理
    • 表达式求值：中缀、后缀表达式的计算
    • 括号匹配：编译器语法检查、代码格式化
    • 深度优先搜索：图算法和树的遍历

核心概念对比

特性队列 (Queue)栈 (Stack)
数据结构特性先进先出 (FIFO)后进先出 (LIFO)
插入操作offer() - 队尾插入push() - 栈顶插入
删除操作poll() - 队首删除pop() - 栈顶删除
查看操作peek() - 查看队首peek() - 查看栈顶
典型应用BFS、任务调度DFS、函数调用

实现方式对比

实现方式时间复杂度空间复杂度优点缺点适用场景
链表实现O(1)O(n)动态扩容，无需预分配额外引用开销，内存碎片元素数量不确定，频繁增删
数组实现O(1)O(n)内存连续，访问高效固定容量，可能溢出元素数量可预估，性能敏感
环形数组O(1)O(n)空间复用，避免假溢出实现复杂，边界条件多固定大小缓冲区，消息队列

💻 队列实现

1. 链表实现队列 [Java]-[入门]-[集合框架]

/*** 基于链表的队列实现* 核心思想：使用单链表，头部出队，尾部入队* 时间复杂度：所有操作O(1)* 空间复杂度：O(n)*/
public class LinkedQueue<T> {/*** 链表节点定义*/private static class Node<T> {T data;           // 节点数据Node<T> next;     // 指向下一个节点的引用Node(T data) {this.data = data;this.next = null;}}private Node<T> head;  // 队首指针private Node<T> tail;  // 队尾指针private int size;      // 队列大小/*** 构造函数，初始化空队列*/public LinkedQueue() {head = tail = null;size = 0;}/*** 元素入队（队尾插入）* @param data 待入队元素*/public void offer(T data) {Node<T> newNode = new Node<>(data);if (isEmpty()) {// 空队列时，头尾指针都指向新节点head = tail = newNode;} else {// 非空队列时，在尾部添加新节点tail.next = newNode;tail = newNode;}size++;}/*** 元素出队（队首删除）* @return 队首元素，队列为空时返回null*/public T poll() {if (isEmpty()) {return null;}T data = head.data;head = head.next;// 如果队列变空，尾指针也要置空if (head == null) {tail = null;}size--;return data;}/*** 查看队首元素（不删除）* @return 队首元素，队列为空时返回null*/public T peek() {return isEmpty() ? null : head.data;}/*** 判断队列是否为空* @return 队列是否为空*/public boolean isEmpty() {return head == null;}/*** 获取队列大小* @return 队列中元素个数*/public int size() {return size;}
}

性能特点：

  • ⏱️ 时间复杂度：offer、poll、peek均为O(1)
  • 🧠 空间复杂度：O(n)，n为队列中元素个数
  • 🔍 内存布局：节点分散存储，每个节点额外8字节引用开销
  • ⚠️ 注意事项：需要维护头尾两个指针，空队列时的边界处理

2. 数组实现队列 [Java]-[入门]-[数组操作]

/*** 基于数组的队列实现（简单版本）* 核心思想：使用头尾指针标记队列边界* 时间复杂度：所有操作O(1)* 空间复杂度：O(n)* ⚠️ 缺陷：不支持空间复用，存在假溢出问题*/
public class ArrayQueue {private int[] queue;     // 存储队列元素的数组private int head;        // 队首指针private int tail;        // 队尾指针（指向下一个空位）private final int capacity;  // 队列容量/*** 构造函数，初始化指定容量的队列* @param capacity 队列容量*/public ArrayQueue(int capacity) {this.capacity = capacity;this.queue = new int[capacity];this.head = 0;this.tail = 0;}/*** 元素入队（队尾插入）* @param num 待入队元素* @return 入队是否成功*/public boolean offer(int num) {// 检查队列是否已满（假溢出检查）if (tail >= capacity) {return false;}queue[tail++] = num;return true;}/*** 元素出队（队首删除）* @return 队首元素* @throws RuntimeException 队列为空时抛出异常*/public int poll() {if (isEmpty()) {throw new RuntimeException("队列为空，无法出队");}return queue[head++];}/*** 查看队首元素（不删除）* @return 队首元素* @throws RuntimeException 队列为空时抛出异常*/public int peek() {if (isEmpty()) {throw new RuntimeException("队列为空，无法查看");}return queue[head];}/*** 判断队列是否为空* @return 队列是否为空*/public boolean isEmpty() {return head >= tail;}/*** 获取队列当前大小* @return 队列中元素个数*/public int size() {return tail - head;}/*** 判断队列是否已满* @return 队列是否已满*/public boolean isFull() {return tail >= capacity;}
}

性能特点：

  • ⏱️ 时间复杂度：offer、poll、peek均为O(1)
  • 🧠 空间复杂度：O(n)，n为预分配容量
  • 🔍 实现细节：tail指针指向下一个空位，head指针指向队首元素
  • ⚠️ 假溢出问题：当head > 0时，前面的空间无法复用，导致空间浪费

算法要点说明：

  1. 指针含义：head指向队首元素，tail指向下一个可插入位置
  2. 边界条件：空队列时head == tail，满队列时tail == capacity
  3. 空间浪费：出队操作只移动head指针，不回收前面空间
  4. 改进方向：使用环形数组解决假溢出问题

🔄 栈实现

1. 数组实现栈 [Java]-[入门]-[数组操作]

/*** 基于数组的栈实现* 核心思想：数组尾部作为栈顶，使用size指针管理栈顶位置* 时间复杂度：所有操作O(1)* 空间复杂度：O(n)*/
public class ArrayStack {private int[] stack;        // 存储栈元素的数组private int size;           // 栈顶指针（指向下一个空位）private final int capacity; // 栈容量/*** 构造函数，初始化指定容量的栈* @param capacity 栈容量*/public ArrayStack(int capacity) {this.capacity = capacity;this.stack = new int[capacity];this.size = 0;}/*** 元素入栈* @param num 待入栈元素* @return 入栈是否成功*/public boolean push(int num) {// 检查栈是否已满if (size >= capacity) {return false;}stack[size++] = num;return true;}/*** 元素出栈* @return 栈顶元素* @throws RuntimeException 栈为空时抛出异常*/public int pop() {if (isEmpty()) {throw new RuntimeException("栈为空，无法出栈");}return stack[--size];}/*** 查看栈顶元素（不删除）* @return 栈顶元素* @throws RuntimeException 栈为空时抛出异常*/public int peek() {if (isEmpty()) {throw new RuntimeException("栈为空，无法查看");}return stack[size - 1];}/*** 判断栈是否为空* @return 栈是否为空*/public boolean isEmpty() {return size == 0;}/*** 判断栈是否已满* @return 栈是否已满*/public boolean isFull() {return size >= capacity;}/*** 获取栈当前大小* @return 栈中元素个数*/public int size() {return size;}
}

2. 链表实现栈 [Java]-[入门]-[集合框架]

/*** 基于链表的栈实现* 核心思想：链表头部作为栈顶，头插法实现入栈，头删法实现出栈* 时间复杂度：所有操作O(1)* 空间复杂度：O(n)*/
public class LinkedStack<T> {/*** 链表节点定义*/private static class Node<T> {T data;           // 节点数据Node<T> next;     // 指向下一个节点的引用Node(T data) {this.data = data;this.next = null;}}private Node<T> top;  // 栈顶指针private int size;     // 栈大小/*** 构造函数，初始化空栈*/public LinkedStack() {top = null;size = 0;}/*** 元素入栈（头插法）* @param data 待入栈元素*/public void push(T data) {Node<T> newNode = new Node<>(data);newNode.next = top;top = newNode;size++;}/*** 元素出栈（头删法）* @return 栈顶元素*/public T pop() {if (isEmpty()) {return null;}T data = top.data;top = top.next;size--;return data;}/*** 查看栈顶元素（不删除）* @return 栈顶元素*/public T peek() {return isEmpty() ? null : top.data;}/*** 判断栈是否为空* @return 栈是否为空*/public boolean isEmpty() {return top == null;}/*** 获取栈大小* @return 栈中元素个数*/public int size() {return size;}
}

性能特点对比：

实现方式时间复杂度空间复杂度优点缺点
数组实现O(1)O(n)内存连续，缓存友好固定容量，可能溢出
链表实现O(1)O(n)动态扩容，无容量限制额外引用开销，内存碎片

算法要点说明：

  1. 数组栈：size指针指向下一个空位，栈顶元素在stack[size-1]
  2. 链表栈：top指针指向栈顶元素，使用头插法和头删法
  3. 边界处理：空栈检查是关键，避免数组越界和空指针异常
  4. 性能优势：比Java内置Stack类（基于Vector）效率更高

🌟 环形队列实现 [算法]-[中级]-[高频考点]

/*** 环形队列实现（力扣622题标准解法）* 核心思想：使用环形数组解决假溢出问题，通过size变量区分空满状态* 时间复杂度：所有操作O(1)* 空间复杂度：O(n)* 🔗 LeetCode 622: https://leetcode.cn/problems/design-circular-queue/*/
class MyCircularQueue {private int[] queue;     // 环形数组private int head;        // 队首指针private int tail;        // 队尾指针private int size;        // 当前元素数量private final int capacity;  // 队列容量/*** 构造函数，设置队列长度为k* @param k 队列容量*/public MyCircularQueue(int k) {this.capacity = k;this.queue = new int[k];this.head = 0;this.tail = 0;this.size = 0;}/*** 向循环队列插入一个元素* @param value 待插入元素* @return 是否成功插入*/public boolean enQueue(int value) {if (isFull()) {return false;}queue[tail] = value;tail = (tail + 1) % capacity;  // 环形移动size++;return true;}/*** 从循环队列中删除一个元素* @return 是否成功删除*/public boolean deQueue() {if (isEmpty()) {return false;}head = (head + 1) % capacity;  // 环形移动size--;return true;}/*** 获取队首元素* @return 队首元素，队列为空时返回-1*/public int Front() {if (isEmpty()) {return -1;}return queue[head];}/*** 获取队尾元素* @return 队尾元素，队列为空时返回-1*/public int Rear() {if (isEmpty()) {return -1;}// 获取队尾元素索引：tail的前一个位置int rearIndex = (tail - 1 + capacity) % capacity;return queue[rearIndex];}/*** 检查队列是否为空* @return 队列是否为空*/public boolean isEmpty() {return size == 0;}/*** 检查队列是否已满* @return 队列是否已满*/public boolean isFull() {return size == capacity;}
}

环形队列可视化

enQueue(x)
是
否
deQueue()
是
否
Front()
是
否
Rear()
是
否
环形数组初始化
head=0, tail=0, size=0
执行操作
队列是否已满
返回false
queue[tail] = x
tail = (tail+1) % capacity
size++
队列是否为空
返回false
head = (head+1) % capacity
size--
队列是否为空
返回-1
返回queue[head]
队列是否为空
返回-1
计算rearIndex
返回queue[rearIndex]

核心技巧：

  1. 环形移动公式：(index + 1) % capacity 实现指针环形递增
  2. 队尾索引计算：(tail - 1 + capacity) % capacity 获取队尾元素位置
  3. 状态判断优化：使用size变量避免head == tail的歧义
  4. 数学证明：
    • 空队列：size == 0
    • 满队列：size == capacity
    • 有效元素：从head到tail（环形）共size个

算法要点说明：

  1. 防溢出处理：(tail - 1 + capacity) % capacity 确保负数取模正确
  2. 空间复用：解决普通数组队列的假溢出问题
  3. 边界条件：head和tail可以在数组中任意位置，通过size判断状态
  4. 工程优化：相比两指针方案，减少了边界判断的复杂度

🔄 数据结构相互实现 [算法]-[中级]-[面试高频]

1. 用栈实现队列 [力扣232]

/*** 用栈实现队列的通用模板* 核心思想：双栈设计，一个负责入队，一个负责出队* 🔗 LeetCode 232: https://leetcode.cn/problems/implement-queue-using-stacks/*/
class MyQueue {private Stack<Integer> inStack;   // 入队栈private Stack<Integer> outStack;  // 出队栈/*** 构造函数，初始化两个栈*/public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();}/*** 元素入队* @param x 待入队元素*/public void push(int x) {inStack.push(x);}/*** 元素出队* @return 队首元素*/public int pop() {// 确保outStack有元素if (outStack.isEmpty()) {// 将inStack所有元素转移到outStackwhile (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.pop();}/*** 查看队首元素* @return 队首元素*/public int peek() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.peek();}/*** 判断队列是否为空* @return 队列是否为空*/public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
}

2. 用队列实现栈 [力扣225]

/*** 用队列实现栈（单队列优化版本）* 核心思想：每次push后，将前面的元素重新排列到队尾* 🔗 LeetCode 225: https://leetcode.cn/problems/implement-stack-using-queues/*/
class MyStack {private Queue<Integer> queue;/*** 构造函数，初始化队列*/public MyStack() {queue = new LinkedList<>();}/*** 元素入栈* @param x 待入栈元素*/public void push(int x) {int size = queue.size();queue.offer(x);// 将前面的元素重新排列，使新元素位于队首for (int i = 0; i < size; i++) {queue.offer(queue.poll());}}/*** 元素出栈* @return 栈顶元素*/public int pop() {return queue.poll();}/*** 查看栈顶元素* @return 栈顶元素*/public int top() {return queue.peek();}/*** 判断栈是否为空* @return 栈是否为空*/public boolean empty() {return queue.isEmpty();}
}

复杂度分析

用栈实现队列
  • 摊还时间复杂度：虽然单次pop可能是O(n)，但n次操作的总时间仍为O(n)
  • 分析原理：每个元素最多被移动2次（inStack→outStack→出队），总移动次数为O(n)
  • 实际性能：在实际使用中，大部分pop操作都是O(1)的
用队列实现栈
  • 时间复杂度：push为O(n)，pop、top、empty为O(1)
  • 空间复杂度：O(n)，n为栈中元素个数
  • 性能权衡：push操作较慢，但其他操作保持高效

性能对比表格

操作原生队列栈实现队列摊还分析原生栈队列实现栈
push/offerO(1)O(1)O(1)O(1)O(n)
pop/pollO(1)O(1)/O(n)O(1)O(1)O(1)
peek/topO(1)O(1)/O(n)O(1)O(1)O(1)
emptyO(1)O(1)O(1)O(1)O(1)

视频链接

左老师的视频链接
013【入门】队列和栈-链表、数组实现

http://www.xdnf.cn/news/15522.html

相关文章：

  • TCP 拥塞控制算法 —— 慢启动（Slow Start）笔记
  • 【add vs commit】Git 中的 add 和 commit 之间的区别
  • HTTP协议介绍
  • 堆排序算法详解：原理、实现与C语言代码
  • Opencv---cv::minMaxLoc函数
  • 激活函数LeakyReLU
  • ai 编程工具，简单总结
  • C++设计模式之创建型模式
  • WSL2更新后Ubuntu 24.04打不开（终端卡住，没有输出）
  • Java对象的比较
  • 每日算法刷题Day49:7.16:leetcode 差分5道题，用时2h
  • 什么是数据仓库？数据库与数据仓库有什么关系？
  • 格密码--Ring-SIS和Ring-LWE
  • Python 日志轮换处理器的参数详解
  • 【python】sys.executable、sys.argv、Path(__file__) 在PyInstaller打包前后的区别
  • C语言：第07天笔记
  • smolagents - 如何在mac用agents做简单算术题
  • STM32外设介绍3：(UART 和 USART 通信详解＜含重定向与 DMA＞)
  • 大端序与小端序
  • 【机器学习】数据理解：数据导入、数据审查与数据可视化
  • 2.库操作
  • 自动驾驶激光3D点云处理系统性阐述及Open3D库函数应用
  • 百炼Agent MCP与IoT实战（二）：阿里云MQTT Broker配置
  • 控制Vue对话框显示隐藏
  • fastadmin会员单点登录
  • python的慈善捐赠平台管理信息系统
  • MyBatis详解以及在IDEA中的开发
  • 数据结构与算法学习（一）
  • 个人笔记(linux/tr命令)
  • LVS：高性能负载均衡利器