本文是算法与数据结构的学习笔记第四篇，将持续更新，欢迎小伙伴们阅读学习 。有不懂的或错误的地方，欢迎交流
栈
栈是一种线性数据结构，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶 (Top）, 另一端称为栈底 (Bottom)。栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则，即最后进入的元素最先被访问。
压栈（push）：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈（pop）：栈的删除操作叫做出栈，出数据也在栈顶。
下面的动图可以更直观的理解栈的出入栈
栈的特点
- 1.后进先出（LIFO）：最后进入栈的元素最先被访问，而最先进入栈的元素最后被访问。
- 2.只允许在一端进行插入和删除操作：栈通常只允许在栈顶进行插入和删除操作，而不允许在其他位置进行操作。
- 3.栈顶指针：栈顶指针指向栈顶元素，它随着元素的插入和删除而改变。
栈的应用
1.函数调用：编程语言中的函数调用过程使用栈来保存函数的返回地址、参数和局部变量等信息。每当一个函数被调用，其相关信息被压入栈中；当函数执行完毕，这些信息被弹出栈，控制权回到调用函数。
2.表达式求值：栈在表达式求值中起到重要作用。通过将中缀表达式转换为后缀表达式，并使用栈来存储操作数和运算符，可以实现对表达式的求值。
3.括号匹配：栈常用于检查表达式中括号是否匹配的问题。遍历表达式时，遇到左括号就将其压入栈中，遇到右括号时与栈顶元素进行匹配，如果匹配则弹出栈顶元素，继续遍历；如果不匹配，则括号不匹配。
4.撤销操作：在文本编辑器或图形处理软件中，栈可用于实现撤销操作。每次执行操作时，相关信息被压入栈中，当用户需要撤销操作时，将栈顶元素弹出，回退到上一个状态。
5.中断处理和现场保护：中断是计算机系统中常见的事件，例如硬件故障、外部设备请求等。当系统发生中断时，当前正在执行的程序需要被暂停，转而处理中断事件。栈在中断处理中扮演着重要角色，用于保存和恢复程序的执行现场。当发生中断时，系统会自动将当前程序的执行现场（包括程序计数器、寄存器等状态信息）保存到栈中。然后，中断服务程序（Interrupt Service Routine，ISR）被执行，处理中断事件。处理完成后，系统从栈中恢复之前保存的执行现场，继续原来被中断的程序的执行。通过栈的保存和恢复操作，确保中断处理的流程正确且不会破坏原有的程序执行。
栈的基本操作
- 1.初始化栈。
- 2.压栈，往栈中添加一个元素。
- 3.出栈，从栈顶删除一个元素。
- 4.获取栈顶元素。
- 5.判断栈是否为空、是否满栈。
- 6.栈的销毁。
注意：在操作栈时，要避免“上溢”和“下溢”
上溢：指栈已满，若继续存数据，则会上溢，出现报错（栈满再存出现上溢）
下溢：指栈已空，若继续取数据，则会下溢，出现报错（栈空再取出现下溢）
C 语言
栈有两种实现方式，一种是使用数组来实现，另一种是使用链表来实现。下面是总结的用数组和链表实现的优缺点。
用数组实现的优点
1 . 数组在内存中是连续存储的，因此访问元素时速度较快。CPU高速缓存命中率会更高。
2. 下标的随机访问。尾插尾删效率不错.
3. 数组实现相对简单，不需要额外的指针来维护元素之间的关系。
数组实现的缺点
1 . 数组的大小是固定的，因此在栈空间不足时需要进行扩容操作，这可能会导致性能下降。
2 . 在删除元素时，需要移动数组中的其他元素，这也可能会导致性能下降。
用链表实现的优点
1 .链表的大小可以动态调整，因此可以更好地利用空间。
2 . 任意位置插入删除O(1) ，链表的性能较高，因为不需要移动其他元素。
链表实现的缺点
1 . CPU高速缓存命中率会更低,不是连续存储的，因此访问元素时速度较慢。
2. 不支持下标的随机访问.
用链表还是用数组结构实现，这个问题的答案取决于具体的应用场景和需求，下面我们给出了数组栈和链表栈的 C 语言实现。
数组栈
#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 // 定义栈结构 typedef struct { int data[MAX_SIZE]; // 用数组存储栈的元素 int top; // 栈顶指针 } Stack; // 初始化栈 void init(Stack *stack) { stack->top = -1; // 初始化栈顶指针为-1，表示栈为空 } // 判断栈是否为空 int isEmpty(Stack *stack) { return stack->top == -1; } // 判断栈是否已满 int isFull(Stack *stack) { return stack->top == MAX_SIZE - 1; } // 入栈操作 void push(Stack *stack, int item) { if (isFull(stack)) { printf("Stack overflow\n"); return; } stack->top++; // 栈顶指针加1 stack->data[stack->top] = item; // 将元素入栈 } // 出栈操作 int pop(Stack *stack) { int item; if (isEmpty(stack)) { printf("Stack underflow\n"); return -1; } item = stack->data[stack->top]; // 获取栈顶元素 stack->top--; // 栈顶指针减1 return item; } // 获取栈顶元素 int peek(Stack *stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return -1; } return stack->data[stack->top]; } // 销毁栈 void destroy(Stack *stack) { stack->top = -1; // 将栈顶指针重置为-1，表示栈为空 } int main() { Stack stack; init(&stack); push(&stack, 1); push(&stack, 2); push(&stack, 3); printf("Top element: %d\n", peek(&stack)); printf("Popped element: %d\n", pop(&stack)); printf("Popped element: %d\n", pop(&stack)); printf("Top element: %d\n", peek(&stack)); destroy(&stack); return 0; }
链表栈
#include <stdio.h> #include <stdlib.h> // 定义链表节点 typedef struct Node { int data; struct Node* next; } Node; // 定义栈结构 typedef struct { Node* top; // 栈顶指针 } Stack; // 初始化栈 void init(Stack* stack) { stack->top = NULL; // 初始化栈顶指针为空 } // 判断栈是否为空 int isEmpty(Stack* stack) { return stack->top == NULL; } /* 由于链表实现的栈理论上没有大小限制，因此不存在“栈满”的情况。在入栈操作时只需要创建新节点，并将其插入到链表头部即可。 如需限制栈的大小，可以通过设置一个变量来记录当前栈中存储的元素个数，然后在入栈时进行判断，若已满则不允许再次入栈。*/ // 入栈操作 void push(Stack* stack, int item) { Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点 if (newNode == NULL) { printf("Memory allocation failed\n"); return; } newNode->data = item; // 设置新节点的数据为要入栈的元素 newNode->next = stack->top; // 将新节点插入到栈顶 stack->top = newNode; // 更新栈顶指针 } // 出栈操作 int pop(Stack* stack) { if (isEmpty(stack)) { printf("Stack underflow\n"); return -1; } Node* topNode = stack->top; // 获取栈顶节点 int item = topNode->data; // 获取栈顶元素 stack->top = topNode->next; // 更新栈顶指针 free(topNode); // 释放栈顶节点的内存 return item; } // 获取栈顶元素 int peek(Stack* stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return -1; } return stack->top->data; } // 销毁栈 void destroy(Stack* stack) { while (!isEmpty(stack)) { pop(stack); } } int main() { Stack stack; init(&stack); push(&stack, 1); push(&stack, 2); push(&stack, 3); printf("Top element: %d\n", peek(&stack)); printf("Popped element: %d\n", pop(&stack)); printf("Popped element: %d\n", pop(&stack)); printf("Top element: %d\n", peek(&stack)); destroy(&stack); return 0; }
队列
队列是栈的兄弟结构，是只允许在一端进行插入元素操作，在另一端进行删除元素操作的线性数据结构。进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中的数据元素遵守先进先出 FIFO（First In First Out）的原则，即最先进入的元素最先被访问。
队列的特点
1.先进先出（FIFO）：第一个插入的元素是第一个被删除的元素，因此表现为先进先出的顺序。
2.元素只能从队尾插入（入队）和从队头删除（出队）。
队列的应用
1.消息传递:在消息传递模型中，消息被发送到队列中等待接收方进行处理。发送方可以通过入队操作向队列发送消息，而接收方则通过出队操作从队列中获取消息。
2.缓存区管理：在网络通信、磁盘I/O等场景中，队列被用于管理数据的缓冲区。接收到的数据被放入队列中，然后按照一定的规则从队列中取出，保证数据按照顺序传输。
3.任务调度：操作系统中的任务调度通常使用队列来管理待执行的任务，按照先来先服务（First-Come-First-Served，FCFS）的原则进行调度。
4.广度优先搜索：图的广度优先搜索算法（BFS）使用队列来保存待访问的节点。从起始节点开始，将其放入队列中，然后不断从队列中取出节点，并将其邻接节点放入队列，直到队列为空。
队列的基本操作
1.入队（enqueue）：将元素插入到队列的末尾。
2.出队（dequeue）：从队列的头部删除一个元素并返回。
3.获取队列头部元素的值。
4.获取队列中元素的个数。
5.判断队列是否为空、是否已满。
6.队列的销毁
C 语言
队列有两种实现方式，一种是使用数组来实现，另一种是使用链表来实现。下面是总结的用数组和链表实现的优缺点。
用数组实现的优点
1 . 数组在内存中是连续存储的，因此访问元素时速度较快。CPU高速缓存命中率会更高。
2 . 数组实现相对简单，不需要额外的指针来维护元素之间的关系。
数组实现的缺点
1 . 需要事先确定队列的最大长度，这可能会导致性能下降。
2 . 需要移动元素来保持队列的顺序。
用表实现的优点
1 . 不需要事先确定队列的最大长度，可以动态扩展。
2 . 插入和删除操作只需要修改指针，不需要移动元素。
3 . 可以实现多个队列共享一个链表。
链表实现的缺点
1 . CPU高速缓存命中率会更低,不是连续存储的，因此访问元素时速度较慢。
2 .实现相对复杂。
用链表还是用数组结构实现，这个问题的答案取决于具体的应用场景和需求，下面我们给出了数组队列和链表队列的 C 语言实现。
数组队列
#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 // 队列的最大大小 // 定义队列结构体 struct queue { int* arr; // 数组指针 int front; // 队首位置 int rear; // 队尾位置 int size; // 当前队列中存储的元素个数 }; // 初始化队列 struct queue* init() { struct queue* q = (struct queue*)malloc(sizeof(struct queue)); q->arr = (int*)malloc(MAX_SIZE * sizeof(int)); q->front = 0; q->rear = -1; q->size = 0; return q; } // 判断队列是否为空 int is_empty(struct queue* q) { return q->size == 0; } // 判断队列是否已满 int is_full(struct queue* q) { return q->size == MAX_SIZE; } // 入队 void enqueue(struct queue* q, int value) { if (is_full(q)) { printf("Queue Overflow\n"); return; } q->rear = (q->rear + 1) % MAX_SIZE; q->arr[q->rear] = value; q->size++; } // 出队 int dequeue(struct queue* q) { if (is_empty(q)) { printf("Queue Underflow\n"); return -1; } int value = q->arr[q->front]; q->front = (q->front + 1) % MAX_SIZE; q->size--; return value; } // 获取队首元素 int front(struct queue* q) { if (is_empty(q)) { printf("Queue Underflow\n"); return -1; } return q->arr[q->front]; } // 获取队列长度 int size(struct queue* q) { return q->size; } // 销毁队列 void destroy(struct queue* q) { free(q->arr); free(q); } int main() { struct queue* q = init(); enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); printf("%d\n", dequeue(q)); // 输出10 printf("%d\n", front(q)); // 输出20 enqueue(q, 40); printf("%d\n", dequeue(q)); // 输出20 printf("%d\n", dequeue(q)); // 输出30 printf("%d\n", dequeue(q)); // 输出40 printf("%d\n", dequeue(q)); // 输出Queue Underflow destroy(q); // 销毁队列 return 0; }
链表队列
#include <stdio.h> #include <stdlib.h> // 定义队列节点结构体 struct queue_node { int data; struct queue_node* next; }; // 定义队列结构体 struct queue { struct queue_node* front; // 队首指针 struct queue_node* rear; // 队尾指针 int size; // 当前队列中存储的元素个数 }; // 初始化队列 struct queue* init() { struct queue* q = (struct queue*)malloc(sizeof(struct queue)); q->front = NULL; q->rear = NULL; q->size = 0; return q; } // 判断队列是否为空 int is_empty(struct queue* q) { return q->size == 0; } // 同链表栈，链表队列没有固定的大小限制，因此不需要判断队列是否已满 // 入队 void enqueue(struct queue* q, int value) { // 创建新节点 struct queue_node* new_node = (struct queue_node*)malloc(sizeof(struct queue_node)); new_node->data = value; new_node->next = NULL; if (is_empty(q)) { q->front = new_node; q->rear = new_node; } else { q->rear->next = new_node; q->rear = new_node; } q->size++; } // 出队 int dequeue(struct queue* q) { if (is_empty(q)) { printf("Queue Underflow\n"); return -1; } struct queue_node* temp = q->front; int value = temp->data; if (q->front == q->rear) { q->front = NULL; q->rear = NULL; } else { q->front = q->front->next; } free(temp); q->size--; return value; } // 获取队首元素 int front(struct queue* q) { if (is_empty(q)) { printf("Queue Underflow\n"); return -1; } return q->front->data; } // 获取队列长度 int size(struct queue* q) { return q->size; } // 销毁队列 void destroy(struct queue* q) { while (!is_empty(q)) { dequeue(q); } free(q); } int main() { struct queue* q = init(); enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); printf("%d\n", dequeue(q)); // 输出10 printf("%d\n", front(q)); // 输出20 enqueue(q, 40); printf("%d\n", dequeue(q)); // 输出20 printf("%d\n", dequeue(q)); // 输出30 printf("%d\n", dequeue(q)); // 输出40 printf("%d\n", dequeue(q)); // 输出Queue Underflow destroy(q); // 销毁队列 return 0; }
结论
栈和队列作为常见的数据结构，在算法和程序设计中扮演着重要的角色。本文总结了栈和队列的特点、应用场景以及C语言实现。通过深入理解它们的原理和应用，可以更好地解决问题和优化算法。希望本文能够对读者对栈和队列的学习和应用提供帮助。
