本文档提供了 Hello Algo 项目中实现的栈和队列数据结构的概述。这些基本线性数据结构以特定的访问模式管理元素集合。有关作为底层实现的数组和链表的信息，请参阅数组和链表。
栈和队列是抽象数据类型（ADT），它们限制了元素的访问方式，为不同场景提供了专门的行为。
这些结构可以使用数组或链表实现，在内存使用和时间复杂度方面各有权衡。
来源：codes/c/chapter_stack_and_queue/array_stack.c codes/c/chapter_stack_and_queue/linkedlist_queue.c codes/python/chapter_stack_and_queue/linkedlist_deque.py
栈使用后进先出（LIFO）原则来限制元素的访问。就像一叠盘子一样，你只能从顶部添加或移除。
栈的关键操作包括：
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
| 推送 | 向顶部添加元素 | O(1) |
| 弹栈（Pop） | 移除并返回顶部元素 | O(1) |
| 查看/顶部 | 返回顶部元素而不移除它 | O(1) |
| isEmpty | 检查栈是否为空 | O(1) |
| size | 返回元素数量 | O(1) |
来源：codes/python/chapter_stack_and_queue/array_stack.py11-37 codes/c/chapter_stack_and_queue/array_stack.c33-66
栈可以用数组或链表实现，各有优缺点。
数组实现通过一个大小变量（作为数组索引）来跟踪栈顶。
在 C 语言中，ArrayStack 结构定义为：
基于数组的栈的关键考虑因素：
来源：codes/c/chapter_stack_and_queue/array_stack.c11-66 codes/python/chapter_stack_and_queue/array_stack.py8-42
链表实现使用一个指针来跟踪栈顶节点，新元素被添加为链表的新的头部。
在 C 语言中，LinkedListStack 结构定义为：
基于链表的栈的关键考虑因素：
来源：codes/c/chapter_stack_and_queue/linkedlist_stack.c9-70 codes/python/chapter_stack_and_queue/linkedlist_stack.py14-48
队列使用先进先出（FIFO）原则来限制元素的访问。就像排队的人一样，元素在队尾加入，在队头离开。
队列的关键操作包括：
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
| 入队/Push | 添加到队尾 | O(1) |
| 出队/Pop | 移除并返回队头元素 | O(1) |
| 查看/队头 | 返回队头元素而不移除它 | O(1) |
| isEmpty | 检查队列是否为空 | O(1) |
| size | 返回元素数量 | O(1) |
来源：codes/python/chapter_stack_and_queue/array_queue.py8-52 codes/c/chapter_stack_and_queue/array_queue.c33-75
队列可以使用数组或链表实现。
基于数组的队列使用**循环数组**设计来高效利用内存。这需要同时跟踪队头位置和大小（或队尾位置）。
在 C 语言中，ArrayQueue 结构定义为：
循环数组实现的关键方面：
(front + size) % capacity来源：codes/c/chapter_stack_and_queue/array_queue.c9-75 codes/python/chapter_stack_and_queue/array_queue.py8-61 codes/javascript/chapter_stack_and_queue/array_queue.js8-69
队列的链表实现同时维护了链表的前后指针，允许在 O(1) 时间内完成入队和出队操作。
在 C 语言中，LinkedListQueue 结构定义为：
基于链表的队列的关键考虑因素：
来源：codes/c/chapter_stack_and_queue/linkedlist_queue.c9-77 codes/python/chapter_stack_and_queue/linkedlist_queue.py14-58
双端队列（发音为“deck”）是一种允许在队头和队尾进行插入和移除操作的队列。
双端队列的关键操作包括：
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
| pushFirst | 添加到队头 | O(1) |
| pushLast | 添加到队尾 | O(1) |
| popFirst | 移除并返回队头元素 | O(1) |
| popLast | 移除并返回队尾元素 | O(1) |
| peekFirst | 返回队头元素而不移除它 | O(1) |
| peekLast | 返回队尾元素而不移除它 | O(1) |
| isEmpty | 检查双端队列是否为空 | O(1) |
| size | 返回元素数量 | O(1) |
来源：codes/python/chapter_stack_and_queue/linkedlist_deque.py18-107 codes/c/chapter_stack_and_queue/array_deque.c30-124 codes/python/chapter_stack_and_queue/array_deque.py8-86
双端队列可以使用数组或链表实现，各有考虑。
与循环数组队列类似，基于数组的双端队列使用模运算来处理循环。
在 C 语言中，ArrayDeque 结构定义为：
基于数组的双端队列的关键考虑因素：
来源：codes/c/chapter_stack_and_queue/array_deque.c9-124 codes/python/chapter_stack_and_queue/array_deque.py8-86
对于双端队列，双向链表特别有用，因为它允许在两端高效进行操作。C 语言的实现使用了以下结构：
其中 DoublyListNode 包含前向和后向指针。
基于链表的双端队列的关键考虑因素：
来源： codes/c/chapter_stack_and_queue/linkedlist_deque.c9-152 codes/python/chapter_stack_and_queue/linkedlist_deque.py8-107
| 考量因素 | 数组实现 | 链表实现 |
|---|---|---|
| 内存效率 | 已知大小更佳 | 未知大小更佳 |
| 内存开销 | 每个元素的开销较低 | 较高（指针） |
| 访问模式 | 更好的缓存局部性 | 内存中更分散 |
| 插入/删除 | 可能需要调整大小 | 使用适当的指针始终为 O(1) |
| 实现复杂度 | 栈更简单，循环队列更复杂 | 队列更简单，双端队列更复杂 |
根据您的具体要求进行选择
当以下情况时，使用基于数组的实现：
当以下情况时，使用基于链表的实现：
来源：stack_and_queue 目录中的所有文件