栈（Stack）和队列（Queue）是计算机科学中两种基本的数据结构，广泛应用于各种算法和系统设计中。下面是对这两种数据结构的详细介绍。
栈（Stack）
1. 定义
栈是一种后进先出（LIFO, Last In, First Out）的数据结构。这意味着最后插入栈的数据将是最先被移除的。
2. 基本操作
- 压栈（Push）： 向栈顶添加一个元素。
- 弹栈（Pop）： 从栈顶移除一个元素。
- 查看栈顶元素（Peek/Top）： 获取栈顶元素的值但不移除它。
- 判断栈是否为空（IsEmpty）： 检查栈是否为空。
- 获取栈的大小（Size）： 获取栈中元素的数量。
3. 应用场景
- 递归调用： 计算机的函数调用是通过栈来实现的，每次调用都会把当前状态压入栈中，返回时再从栈中弹出。
- 表达式求值： 如逆波兰表达式（后缀表达式）的计算，括号匹配等。
- 深度优先搜索（DFS）： 栈用于保存当前路径。
4. 实现方式
- 数组实现： 栈可以通过数组来实现，通常定义一个固定大小的数组，并用一个变量表示栈顶位置。
- 链表实现： 使用链表可以实现一个动态的栈，避免数组的固定大小限制。
队列（Queue）
1. 定义
队列是一种先进先出（FIFO, First In, First Out）的数据结构。这意味着最先插入队列的数据将是最先被移除的。
2. 基本操作
- 入队（Enqueue）： 向队列的尾部添加一个元素。
- 出队（Dequeue）： 从队列的头部移除一个元素。
- 查看队头元素（Front/Peek）： 获取队列头部元素的值但不移除它。
- 判断队列是否为空（IsEmpty）： 检查队列是否为空。
- 获取队列的大小（Size）： 获取队列中元素的数量。
3. 应用场景
- 任务调度： 多任务操作系统中的任务排队、打印任务管理等都可以用队列来实现。
- 广度优先搜索（BFS）： 队列用于保存当前层的节点。
- 数据流处理： 处理流式数据或消息时，队列用于保证处理顺序。
4. 实现方式
- 数组实现： 可以使用数组来实现一个固定大小的队列，通过两个指针（头和尾）来标记队列的两端。注意需要处理队列满的情况，可以通过循环数组的方式来优化。
- 链表实现： 链表实现的队列可以动态调整大小，避免固定大小数组的限制。
栈与队列的区别
- 数据处理顺序不同： 栈是LIFO，队列是FIFO。
- 应用场景不同： 栈多用于需要后进先出的场景，如函数调用，表达式计算等；队列多用于需要先进先出的场景，如任务调度，广度优先搜索等。
扩展
- 双端队列（Deque）： 一种允许从两端进行入队和出队操作的队列结构，是栈和队列的结合。
- 优先队列（Priority Queue）： 一种特殊的队列，其中每个元素都有优先级，出队时总是优先级最高的元素先出队。
这些都是栈和队列在计算机科学中常见的实现与应用。了解这些基本数据结构对学习算法和编程非常有帮助。
