栈和队列：Swift 为什么没有 Stack 类型

栈按 LIFO 顺序取出数据，队列按 FIFO 顺序取出。本文介绍 Swift 没有专用 Stack 类型的原因、如何用 Array 实现栈，以及队列中 removeFirst 带来的性能陷阱。

SeokWoo Lee资深 iOS 软件工程师发布 2026年8月4日更新 2026年8月27日5 分钟阅读

开始学习数据结构时，最先遇到的两个兄弟就是栈（Stack）和队列（Queue）。

概念本身五分钟就能学会。但到了 Swift，会发现一个疑问：标准库有 Array、Dictionary 和 Set，却没有 **Stack 和 Queue 类型。**本文解释为什么没有，以及没有它们时该怎么用。

用数组模拟队列时遇到的性能陷阱（removeFirst()），是编程题超时的常见原因，因此单独详细说明。

本文所说的栈是数据结构，不是内存分配区域。同名概念的区别见内存栈 vs 堆；队列拥有优先级的下一步内容见堆与优先队列。

概念就是盘子和排队

栈是 LIFO（Last In, First Out）。最后放入的最先取出。想象一摞盘子：从顶部 push，也从顶部 pop。从中间取出就违反规则了。

队列是 FIFO（First In, First Out）。最先放入的最先取出。就像收银台排队：从队尾 enqueue，从队首 dequeue。

每种结构都只有两个操作。

	放入	取出	查看
栈	push	pop	peek(top)
队列	enqueue	dequeue	front

这么简单，为什么重要？因为这条规则是 iOS 开发许多部分的基础。

调用栈：函数调用和返回正是 push/pop。递归过深时出现的崩溃叫 stack overflow，并非没有原因。
UINavigationController：pushViewController / popViewController——页面切换本质上就是栈。
撤销（undo）：把命令压入栈，再按相反顺序恢复。
GCD（Grand Central Dispatch）的 DispatchQueue：顾名思义，它就是队列。放入 serial queue 的任务会按加入顺序执行。
BFS/DFS：图遍历使用队列就是 BFS（Breadth-First Search，广度优先搜索），使用栈就是 DFS（Depth-First Search，深度优先搜索）。选择数据结构就是选择算法。

Swift 为什么没有 Stack

先说结论：因为Array 已经是完美的栈。

var stack: [Int] = []
stack.append(3)      // push — O(1)
stack.append(7)
let top = stack.last // peek — O(1)
let popped = stack.popLast() // pop — O(1), 为空时 nil

在数组末尾放入和取出元素都是 O(1)；更准确地说是 amortized O(1)，只有内部缓冲区填满时才需要扩容。单独定义类型也只是包一层 Array，所以标准库没有添加它。

如果想表达意图，通常加一层薄封装即可。

struct Stack<Element> {
    private var storage: [Element] = []
    var isEmpty: Bool { storage.isEmpty }
    var top: Element? { storage.last }
    mutating func push(_ element: Element) { storage.append(element) }
    mutating func pop() -> Element? { storage.popLast() }
}

它会阻止subscript，通过类型强制栈的规则：“禁止访问中间元素”。

并列展示栈 push/pop 与队列 enqueue/dequeue 方向的 LIFO/FIFO 图解 — 只要记住放入和取出的方向，就不会混淆。

用数组创建队列会掉进陷阱

用和栈相同的逻辑创建队列，会变成这样。

var queue: [Int] = []
queue.append(1)              // enqueue — O(1), 没有问题
let first = queue.removeFirst() // dequeue — O(n), 陷阱就在这里

removeFirst()会移除第一个元素，并让**其余元素全部向前移动一格。**如果有十万个元素，一次 dequeue 就会产生十万次移动。在 BFS 这样反复 dequeue 数万次的算法中，整体复杂度会变成 O(n²)，编程题就会超时。

解决方案有三个。

1. 用索引推进队首（编程题标准做法）

var queue: [Int] = []
var head = 0
// enqueue
queue.append(5)
// dequeue
let value = queue[head]
head += 1

不真正移除元素，只移动读取位置。dequeue 变为 O(1)；前面已用的内存仍会保留，但在编程题中几乎总是够用。

2. 用两个栈创建队列（面试常见题）

放入时压入 in 栈；取出时如果 out 栈为空，就把 in 整体反转后转移，再 pop。每个元素最多移动两次，因此是 amortized O(1)。这也是“用栈实现队列”面试题的标准答案。

3. swift-collections 的 Deque（生产环境答案）

Apple 维护的swift-collections包提供了Deque，基于环形缓冲区，因此两端插入和删除都是 O(1)。

import DequeModule

var queue: Deque<Int> = []
queue.append(1)            // enqueue
let v = queue.popFirst()   // dequeue — O(1)

它的 API 几乎与 Array 相同，因此替换成本很低。生产环境需要队列时，直接使用它，不要自己实现。

选择哪一种的判断标准

感到困惑时，问一个问题即可：“应该先处理后来的吗，还是先处理先来的？”

撤销、括号匹配、回溯访问路径、深度优先搜索 → 最新的优先 → 栈
任务等待队列、事件处理、打印机输出、广度优先搜索 → 保证到达顺序 → 队列

括号匹配是栈的典型应用：遇到左括号就 push，遇到右括号就 pop 并检查是否匹配；结束时栈为空，表达式才有效。编译器检查代码大括号的原理也一样。

用传送带表现 Swift 数组 removeFirst O(n) 性能陷阱的队列插图 — 每取出一个，后面的所有元素都会向前移动一格。

总结

栈是 LIFO，队列是 FIFO——盘子和收银台排队就能说明全部概念。
调用栈、导航栈、undo 属于栈；DispatchQueue、事件处理、BFS 属于队列。它们早已遍布 iOS 开发。
Swift 没有 Stack 类型，是因为Array 的 append/popLast 已经是 O(1) 栈。
用数组创建队列时，removeFirst()是 O(n)——编程题超时的常见原因。
解决方案是 head 索引、两个栈，或者生产环境使用 swift-collections 的Deque。
选择栈还是队列，只需问一个问题：“优先处理最新的，还是优先遵循到达顺序？”

下一篇将继续介绍它们的应用版本：堆和优先队列，以及 Dictionary 背后的哈希表。