1. 栈 (Stack)
栈是一种后进先出 (LIFO, Last In First Out) 的数据结构。也就是说，最后加入栈中的元素最先被移除。
栈的基本操作：
- 入栈 (Push)：将元素放入栈顶。
- 出栈 (Pop)：移除并返回栈顶的元素。
- 查看栈顶 (Peek/Top)：返回栈顶的元素但不移除它。
- 判空 (IsEmpty)：判断栈是否为空。
- 栈的大小 (Size)：返回栈中元素的数量。
栈的应用：
- 递归调用：函数调用的管理，操作系统使用栈来管理函数的递归调用。
- 表达式求值：例如，使用栈来求解中缀表达式转换为后缀表达式，或直接求解后缀表达式。
- 括号匹配：判断括号的配对是否合法，通常通过栈实现。
2. 队列 (Queue)
队列是一种先进先出 (FIFO, First In First Out) 的数据结构。即最先加入队列的元素最先被移除。
队列的基本操作：
- 入队 (Enqueue)：将元素添加到队尾。
- 出队 (Dequeue)：移除并返回队头的元素。
- 查看队头 (Front/Peek)：返回队头的元素但不移除它。
- 判空 (IsEmpty)：判断队列是否为空。
- 队列的大小 (Size)：返回队列中元素的数量。
队列的应用：
- 任务调度：例如，操作系统中的任务调度、进程调度等。
- 广度优先搜索 (BFS)：使用队列实现广度优先遍历。
- 缓冲区：网络数据传输、流媒体播放等使用队列来存储和处理数据流。
队列的变种：
- 双端队列 (Deque)：允许在队列两端进行入队和出队操作。
- 优先队列 (Priority Queue)：每个元素有优先级，优先级高的元素会优先出队。
1. 操作方式的区别：
- 栈 (Stack)：遵循后进先出 (LIFO) 原则。最后进入栈的元素最先被移除。
- 特点：只能在一端（栈顶）进行插入和删除操作。
- 队列 (Queue)：遵循先进先出 (FIFO) 原则。最先进入队列的元素最先被移除。
- 特点：在一端（队尾）进行插入操作，在另一端（队头）进行删除操作。
2. 插入与删除位置的区别：
- 栈：只允许在栈顶进行插入和删除操作。
- 队列：在队尾插入，在队头删除。
3. 数据流向的区别：
- 栈：数据在同一端进出，具有“递归”性质，常用于需要回溯的场景。
- 队列：数据从队尾进入，从队头离开，常用于顺序处理任务的场景。
4. 主要应用场景的区别：
-
栈的应用场景：
- 函数调用管理：递归调用时，函数返回值、局部变量保存在栈中。
- 表达式求值：中缀表达式转后缀表达式、后缀表达式求值。
- 括号匹配：验证表达式中括号的合法性。
- 深度优先搜索 (DFS)：使用栈实现图的深度优先遍历。
-
队列的应用场景：
- 任务调度：操作系统中的进程调度、打印任务调度等。
- 广度优先搜索 (BFS)：用队列来进行层次遍历。
- 数据缓冲区：例如在网络通信或流媒体处理中，用于存储和处理数据流。
- 事件处理系统：使用队列按顺序处理事件（例如消息队列）。
5. 数据存取顺序的区别：
- 栈：后进先出。即最近存入的数据最先被取出。
- 队列：先进先出。即最早存入的数据最先被取出。
| 特性 | 栈 (Stack) | 队列 (Queue) |
|---|---|---|
| 数据存储顺序 | 后进先出 (LIFO) | 先进先出 (FIFO) |
| 操作位置 | 仅在栈顶 | 队尾插入，队头删除 |
| 插入复杂度 | O(1) | O(1) |
| 删除复杂度 | O(1) | O(1) |
| 主要用途 | 递归、回溯、表达式求值 | 任务调度、广度优先搜索 |
使用链表实现栈和队列的操作，可以充分发挥链表动态分配内存的特性，避免数组实现中需要预定义大小的限制。
一、使用链表实现栈
栈遵循后进先出 (LIFO) 的原则，因此我们可以使用单向链表的头部作为栈的栈顶，实现入栈、出栈和查看栈顶的操作。
栈的链表节点结构：
typedef struct Node {int data;struct Node* next;
} Node;
栈的常见操作：
1.入栈 (Push)： 每次将新元素插入到链表的头部，这样插入的元素就相当于在栈顶。
void push(Node** top, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = *top;*top = newNode;
}
2. 出栈 (Pop)： 每次从链表的头部移除元素，相当于弹出栈顶元素。如果链表为空，表示栈为空。
int pop(Node** top) {if (*top == NULL) {printf("Stack Underflow\n");return -1; // 空栈的特殊情况处理}Node* temp = *top;int poppedValue = temp->data;*top = (*top)->next;free(temp);return poppedValue;
}
3. 查看栈顶 (Peek/Top)： 返回当前栈顶的值，但不移除它。
int peek(Node* top) {if (top == NULL) {printf("Stack is empty\n");return -1;}return top->data;
}
4.判空 (IsEmpty)： 检查栈是否为空，即链表是否为空。
int isEmpty(Node* top) {return top == NULL;
}
二、使用链表实现队列
队列遵循先进先出 (FIFO) 的原则，因此使用链表实现时，可以让链表的头部作为队列的队头，链表的尾部作为队尾。这样插入操作发生在队尾，删除操作发生在队头。
队列的链表节点结构：
typedef struct Node {int data;struct Node* next;
} Node;typedef struct Queue {Node* front;Node* rear;
} Queue;
队列的常见操作：
1.初始化队列 (InitQueue)： 初始化队列时，将 front 和 rear 都设置为 NULL，表示空队列。
void initQueue(Queue* q) {q->front = q->rear = NULL;
}
2. 入队 (Enqueue)： 将新元素插入到链表的尾部。如果队列为空，front 和 rear 都指向新节点。
void enqueue(Queue* q, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (q->rear == NULL) { // 队列为空q->front = q->rear = newNode;return;}q->rear->next = newNode;q->rear =
3.出队 (Dequeue)： 从链表的头部移除元素，即移除队列的队头。如果队列为空，则返回特定的错误值。移除队头后，需要更新 front 指针。如果移除后队列为空，还需要将 rear 也设置为 NULL。
int dequeue(Queue* q) {if (q->front == NULL) { // 队列为空printf("Queue Underflow\n");return -1; // 空队列时的特殊处理}Node* temp = q->front;int dequeuedValue = temp->data;q->front = q->front->next;// 如果队列变为空，更新 rear 为 NULLif (q->front == NULL) {q->rear = NULL;}free(temp);return dequeuedValue;
}
4. 查看队头 (Front/Peek)： 返回队列队头的元素但不移除它。如果队列为空，返回特定的错误值。
int peek(Queue* q) {if (q->front == NULL) {printf("Queue is empty\n");return -1;}return q->front->data;
}
5. 判空 (IsEmpty)： 检查队列是否为空，即 front 指针是否为 NULL。
int isEmpty(Queue* q) {return q->front == NULL;
}
6.队列大小 (Size)： 由于链表的实现不会像数组那样直接知道大小，所以需要遍历整个链表来计算队列的元素个数。
int size(Queue* q) {int count = 0;Node* current = q->front;while (current != NULL) {count++;current = current->next;}return count;
}