用链表实现队列/栈

raw/articles/2026/05/链表实现队列和栈

核心要点

本文是 labuladong 数据结构基础系列教程，讲解如何以链表作为底层结构实现栈和队列，所有操作均达到 O(1) 时间复杂度。

用链表实现栈

  • 使用双链表（java.util.LinkedList）作为底层存储
  • 可将双链表的头部或尾部作为栈顶：两端增删操作均为 O(1)
  • 示例代码 MyLinkedStack：
    • push(E e)：向栈顶添加元素 → list.addLast(e)（尾部作为栈顶）
    • pop()：弹出栈顶元素 → list.removeLast()
    • peek()：查看栈顶 → list.getLast()
  • 若改为头部作为栈顶，只需将 addLast → addFirst、removeLast → removeFirst、getLast → getFirst

用链表实现队列

  • 同样使用双链表作为底层存储
  • 将双链表头部作为队头、尾部作为队尾：头部删除 O(1)，尾部添加 O(1)
  • 示例代码 MyLinkedQueue：
    • push(E e)：入队 → list.addLast(e)（队尾添加）
    • pop()：出队 → list.removeFirst()（队头删除）
    • peek()：查看队头 → list.getFirst()
  • 也可反转方向，将头部作为队尾、尾部作为队头，只需调整对应 API 调用

相关概念

相关实体

Link to this note

栈

type: concept tags: [数据结构, 操作受限, 线性结构] created: 2026-05-03 updated: 2026-05-03栈（Stack）定义栈是一种操作受限的线性数据结构，遵循**先进后出（LIFO, Last In First Out）**原则。核心特性只能在栈顶插入和删除元素类比：一摞盘子，最后放的在最上面，最先被拿走基本 API| 方法 | 描述 | 时间复杂度 | |------|------|-----------| | push(E e) | 向栈顶插入元素 | O(1) | | pop() | 从栈顶删除并返回元素 | O(1) | | peek() / top() | 查看栈顶元素（不删除） | O(1) | | size()

队列

type: concept tags: [数据结构, 操作受限, 线性结构] created: 2026-05-03 updated: 2026-05-03队列（Queue）定义队列是一种操作受限的线性数据结构，遵循**先进先出（FIFO, First In First Out）**原则。核心特性只能在队尾插入元素（入队，enqueue）只能在队头删除元素（出队，dequeue）类比：排队买票，先到先服务基本 API|------|------|-----------| | push(E e) / enqueue(E e) | 向队尾插入元素 | O(1) | | pop() / dequeue() | 从队头删除并返回元素 | O(1) | | peek() / front() | 查看队头元素（不删除） | O(1) | | size() |

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

Interactive Graph