重生之“我打数据结构，真的假的？”--3.栈和队列（无习题）

栈和队列

C语言中的栈和队列总结

在C语言中，**栈（Stack）和队列（Queue）**是两种非常重要的数据结构。它们广泛用于各种应用中，比如内存管理、任务调度、表达式求值等。本文将对这两种数据结构进行详细的介绍，并展示如何在C语言中实现它们。

1. 栈（Stack）

栈是一种先进后出（LIFO，Last In First Out）数据结构，类似于一摞盘子，最后放上去的盘子最先被拿下来。

1.1 栈的特点

• 先进后出（LIFO）：最后入栈的元素最先出栈。
• 单端操作：栈的插入和删除操作都发生在栈顶。

1.2 栈的基本操作

• 压栈（Push）：将元素压入栈顶。
• 弹栈（Pop）：从栈顶移除元素。
• 查看栈顶元素（Peek/Top）：获取栈顶元素但不删除它。
• 判断栈是否为空（isEmpty）。

1.3 栈的实现方式

栈可以通过数组或链表来实现。以下分别讨论栈的数组实现和链表实现。

1.3.1 使用数组实现栈

以下是用C语言实现栈的数组版：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct Stack {int items[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack->top == -1;
}// 判断栈是否已满
bool isFull(Stack* stack) {return stack->top == MAX_SIZE - 1;
}// 压栈操作
void push(Stack* stack, int value) {if (isFull(stack)) {printf("栈已满，无法压入元素。\n");return;}stack->items[++stack->top] = value;printf("压入元素：%d\n", value);
}// 弹栈操作
int pop(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，无法弹出元素。\n");return -1;}return stack->items[stack->top--];
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，没有栈顶元素。\n");return -1;}return stack->items[stack->top];
}// 遍历栈
void traverseStack(Stack* stack) {if (isEmpty(stack)) {printf("栈为空。\n");return;}for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->items[i]);}printf("\n");
}int main() {Stack stack;initStack(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printf("栈的内容：");traverseStack(&stack);printf("弹出元素：%d\n", pop(&stack));printf("栈顶元素：%d\n", peek(&stack));printf("栈的内容：");traverseStack(&stack);return 0;
}

1.3.2 使用链表实现栈

以下是使用链表实现栈的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int data;struct Node* next;
} Node;typedef struct Stack {Node* top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = NULL;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack->top == NULL;
}// 压栈操作
void push(Stack* stack, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = stack->top;stack->top = newNode;printf("压入元素：%d\n", value);
}// 弹栈操作
int pop(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，无法弹出元素。\n");return -1;}Node* temp = stack->top;int poppedValue = temp->data;stack->top = stack->top->next;free(temp);return poppedValue;
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，没有栈顶元素。\n");return -1;}return stack->top->data;
}// 遍历栈
void traverseStack(Stack* stack) {Node* current = stack->top;if (isEmpty(stack)) {printf("栈为空。\n");return;}while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {Stack stack;initStack(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printf("栈的内容：");traverseStack(&stack);printf("弹出元素：%d\n", pop(&stack));printf("栈顶元素：%d\n", peek(&stack));printf("栈的内容：");traverseStack(&stack);return 0;
}

1.4 栈的应用

• 函数调用栈：计算机系统使用栈来保存函数调用的返回地址。
• 表达式求值和括号匹配：在表达式求值中，栈用于临时保存操作数和操作符。
• 深度优先搜索（DFS）：在图的遍历中，栈可以用于实现深度优先搜索。

2. 队列（Queue）

队列是一种先进先出（FIFO，First In First Out）数据结构，类似于排队买票，第一个到达的人先买票。

2.1 队列的特点

• 先进先出（FIFO）：第一个入队的元素第一个出队。
• 双端操作：插入操作发生在队尾，而删除操作发生在队头。

2.2 队列的基本操作

• 入队（Enqueue）：在队尾添加一个元素。
• 出队（Dequeue）：从队头移除一个元素。
• 查看队头元素（Front）。
• 判断队列是否为空（isEmpty）。

2.3 队列的实现方式

队列可以通过数组或链表来实现。以下分别介绍这两种实现方式。

2.3.1 使用数组实现队列

以下是使用数组实现队列的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct Queue {int items[MAX_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue* queue) {queue->front = -1;queue->rear = -1;
}// 判断队列是否为空
bool isEmpty(Queue* queue) {return queue->front == -1;
}// 判断队列是否已满
bool isFull(Queue* queue) {return queue->rear == MAX_SIZE - 1;
}// 入队操作
void enqueue(Queue* queue, int value) {if (isFull(queue)) {printf("队列已满，无法入队元素。\n");return;}if (isEmpty(queue)) {queue->front = 0;}queue->items[++queue->rear] = value;printf("入队元素：%d\n", value);
}// 出队操作
int dequeue(Queue* queue) {if (isEmpty(queue)) {printf("队列为空，无法出队元素。\n");return -1;}int value = queue->items[queue->front];if (queue->front >= queue->rear) {// 队列为空queue->front = queue->rear = -1;} else {queue->front++;}return value;
}// 查看队头元素
int front(Queue* queue) {if (isEmpty(queue)) {printf("队列为空，没有队头元素。\n");return -1;}return queue->items[queue->front];
}// 遍历队列
void traverseQueue(Queue* queue) {if (isEmpty(queue)) {printf("队列为空。\n");return;}for (int i = queue->front; i <= queue->rear; i++) {printf("%d ", queue->items[i]);}printf("\n");
}int main() {Queue queue;initQueue(&queue);enqueue(&queue, 10);enqueue(&queue, 20);enqueue(&queue, 30);printf("队列的内容：");traverseQueue(&queue);printf("出队元素：%d\n", dequeue(&queue));printf("队头元素：%d\n", front(&queue));printf("队列的内容：");traverseQueue(&queue);return 0;
}

2.3.2 使用链表实现队列

以下是使用链表实现队列的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int data;struct Node* next;
} Node;typedef struct Queue {Node* front;Node* rear;
} Queue;// 初始化队列
void initQueue(Queue* queue) {queue->front = NULL;queue->rear = NULL;
}// 判断队列是否为空
bool isEmpty(Queue* queue) {return queue->front == NULL;
}// 入队操作
void enqueue(Queue* queue, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (isEmpty(queue)) {queue->front = queue->rear = newNode;} else {queue->rear->next = newNode;queue->rear = newNode;}printf("入队元素：%d\n", value);
}// 出队操作
int dequeue(Queue* queue) {if (isEmpty(queue)) {printf("队列为空，无法出队元素。\n");return -1;}Node* temp = queue->front;int value = temp->data;queue->front = queue->front->next;if (queue->front == NULL) {queue->rear = NULL;}free(temp);return value;
}// 查看队头元素
int front(Queue* queue) {if (isEmpty(queue)) {printf("队列为空，没有队头元素。\n");return -1;}return queue->front->data;
}// 遍历队列
void traverseQueue(Queue* queue) {Node* current = queue->front;if (isEmpty(queue)) {printf("队列为空。\n");return;}while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {Queue queue;initQueue(&queue);enqueue(&queue, 10);enqueue(&queue, 20);enqueue(&queue, 30);printf("队列的内容：");traverseQueue(&queue);printf("出队元素：%d\n", dequeue(&queue));printf("队头元素：%d\n", front(&queue));printf("队列的内容：");traverseQueue(&queue);return 0;
}

2.4 队列的应用

• 操作系统中的任务调度：队列用于实现任务调度和处理。
• 广度优先搜索（BFS）：在图的遍历中，队列用于实现广度优先搜索。
• 缓存（Buffer）：队列可用于实现环形缓冲区或缓冲机制。

3. 栈和队列的对比

特性	栈（Stack）	队列（Queue）
数据结构类型	线性	线性
操作模式	LIFO（后进先出）	FIFO（先进先出）
插入/删除位置	只在一端操作（栈顶）	两端操作（队头和队尾）
应用场景	函数调用、递归、括号匹配	任务调度、广度优先搜索

4. 小结

栈和队列都是重要的线性数据结构，栈采用LIFO原则，而队列采用FIFO原则。栈和队列的操作非常简单，但它们在实际应用中起到了至关重要的作用。在C语言中，栈和队列可以通过数组或链表来实现，每种实现方式都有其优缺点。

在理解了这些数据结构的基本操作后，可以更好地应用它们来解决实际问题，如表达式求值、任务调度、图遍历等。掌握这些基础数据结构也为进一步学习更加复杂的数据结构（如树、图等）打下了坚实的基础。