数据结构学习（days04）

栈（Stack）

定义
栈是一种只允许在一端进行插入和删除操作的线性存储结构。这一端被称为栈顶（Top）。

栈的特点
先进后出（FILO：First In Last Out）
插入操作称为：入栈（Push）
删除操作称为：出栈（Pop）

栈的结构分类
（1）栈顶状态：
满栈：栈顶达到预设最大容量
空栈：栈顶指针位于初始位置

（2）栈的生长方向：
根据栈顶指针增长的方向不同，可分为：

因此，也可衍生出四种状态描述方式：
满增栈、满减栈、空增栈、空减栈

栈的典型应用
函数调用栈（递归）
表达式求值（中缀转后缀）
括号匹配
回溯算法（DFS）

队列（Queue）

定义
队列是一种只允许从一端插入、从另一端删除的线性结构。
插入操作称为：入队（Enqueue）
删除操作称为：出队（Dequeue）

队列的特点
先进先出（FIFO：First In First Out）
插入端称为：队尾（Rear）
删除端称为：队头（Front）

循环队列（Circular Queue）

普通队列在用数组实现时，会存在“假溢出”问题——即使数组有空闲空间，但由于队尾已到达数组末尾，无法继续插入。
为了解决这个问题，引入循环队列：将队列首尾相连形成一个环状结构。

判空与判满逻辑（关键点）
为了区分队空和队满的情况，通常循环队列会少存储一个元素，也就是如果数组长度为 N，最多只能存储 N-1 个元素。

判空条件：

front == rear

即：队头指针与队尾指针重合时，队列为空。

判满条件：

(rear + 1) % capacity == front

即：队尾向前移动一位后刚好等于队头，表示队列已满。

模运算实现循环
循环的关键是使用模运算实现“回绕”：

rear  = (rear + 1) % capacity;
front = (front + 1) % capacity;

栈与队列对比总结表