栈与队列：数据结构中的 孪生兄弟 的本质差异
个人主页-爱因斯晨
文章专栏-数据结构
文章目录
1. 引言
在数据结构中，栈和队列是两种重要的线性结构，它们在数据的存储和操作方式上有着显著的不同，各自适用于不同的应用场景。本文将详细阐述栈和队列的概念、差异，并通过 C 语言实现示例，帮助读者深入理解这两种数据结构。
2. 栈和队列的概念界定
2.1 栈
栈是一种遵循 “后进先出”（Last In First Out，LIFO）原则的线性数据结构。它只允许在一端进行插入和删除操作，这一端被称为栈顶，另一端则被称为栈底。
例如，日常生活中叠放的盘子，最后放在上面的盘子可以最先被拿走，这就是栈的典型体现。
2.2 队列
队列是一种遵循 “先进先出”（First In First Out，FIFO）原则的线性数据结构。它允许在一端进行插入操作（队尾），在另一端进行删除操作（队头）。
就像在银行柜台前排队办理业务的人群，先排队的人先办理业务，后排队的人需要等待前面的人办理完毕，这符合队列的特性。
3. 栈和队列的核心差异
4. 栈的 C 语言实现
4.1 栈的结构体定义
#include #include #define STACK_SIZE 50 // 栈的最大容量typedef struct { int data[STACK_SIZE]; // 用于存储栈中元素的数组 int top; // 栈顶指针，指向栈顶元素所在位置} Stack;4.2 栈的基本操作函数
4.2.1 初始化栈
// 功能：初始化栈，使栈为空// 参数：stack - 指向栈结构体的指针void InitStack(Stack *stack) { stack->top = -1; // 栈顶指针为-1时，表示栈为空}4.2.2 判断栈是否为空
// 功能：判断栈是否为空// 参数：stack - 指向栈结构体的指针// 返回值：1 - 栈为空；0 - 栈不为空int IsEmpty(Stack *stack) { return stack->top == -1;}4.2.3 判断栈是否已满
// 功能：判断栈是否已满// 参数：stack - 指向栈结构体的指针// 返回值：1 - 栈已满；0 - 栈未满int IsFull(Stack *stack) { return stack->top == STACK_SIZE - 1;}4.2.4 入栈操作
// 功能：向栈顶插入元素// 参数：stack - 指向栈结构体的指针；value - 要插入的元素值// 返回值：1 - 入栈成功；0 - 入栈失败（栈已满）int Push(Stack *stack, int value) { if (IsFull(stack)) { return 0; } stack->top++; stack->data[stack->top] = value; return 1;}4.2.5 出栈操作
// 功能：从栈顶删除元素，并返回该元素值// 参数：stack - 指向栈结构体的指针；value - 用于存储出栈元素值的指针// 返回值：1 - 出栈成功；0 - 出栈失败（栈为空）int Pop(Stack *stack, int *value) { if (IsEmpty(stack)) { return 0; } *value = stack->data[stack->top]; stack->top--; return 1;}5. 队列的 C 语言实现
5.1 队列的结构体定义
#include #include #define QUEUE_SIZE 50 // 队列的最大容量typedef struct { int data[QUEUE_SIZE]; // 用于存储队列中元素的数组 int front; // 队头指针，指向队头元素 int rear; // 队尾指针，指向队尾元素的下一个位置} Queue;5.2 队列的基本操作函数
5.2.1 初始化队列
// 功能：初始化队列，使队列为空// 参数：queue - 指向队列结构体的指针void InitQueue(Queue *queue) { queue->front = 0; queue->rear = 0;}5.2.2 判断队列是否为空
// 功能：判断队列是否为空// 参数：queue - 指向队列结构体的指针// 返回值：1 - 队列为空；0 - 队列不为空int IsQueueEmpty(Queue *queue) { return queue->front == queue->rear;}5.2.3 判断队列是否已满
// 功能：判断队列是否已满// 参数：queue - 指向队列结构体的指针// 返回值：1 - 队列已满；0 - 队列未满int IsQueueFull(Queue *queue) { return (queue->rear + 1) % QUEUE_SIZE == queue->front;}5.2.4 入队操作
// 功能：向队尾插入元素// 参数：queue - 指向队列结构体的指针；value - 要插入的元素值// 返回值：1 - 入队成功；0 - 入队失败（队列已满）int EnQueue(Queue *queue, int value) { if (IsQueueFull(queue)) { return 0; } queue->data[queue->rear] = value; queue->rear = (queue->rear + 1) % QUEUE_SIZE; return 1;}5.2.5 出队操作
// 功能：从队头删除元素，并返回该元素值// 参数：queue - 指向队列结构体的指针；value - 用于存储出队元素值的指针// 返回值：1 - 出队成功；0 - 出队失败（队列为空）int DeQueue(Queue *queue, int *value) { if (IsQueueEmpty(queue)) { return 0; } *value = queue->data[queue->front]; queue->front = (queue->front + 1) % QUEUE_SIZE; return 1;}6. 栈和队列操作的差异总结
7. 结论
栈和队列作为两种重要的线性数据结构，由于其操作规则的不同，在实际应用中有着不同的用途。栈适用于需要 “后进先出” 特性的场景，如函数调用、表达式求值等；队列适用于需要 “先进先出” 特性的场景，如任务调度、缓冲处理等。
|
| 指针变化 | 仅栈顶指针变化 | 队头和队尾指针均可能变化（循环队列中通过取模实现循环） |
7. 结论
栈和队列作为两种重要的线性数据结构，由于其操作规则的不同，在实际应用中有着不同的用途。栈适用于需要 “后进先出” 特性的场景，如函数调用、表达式求值等；队列适用于需要 “先进先出” 特性的场景，如任务调度、缓冲处理等。
通过 C 语言的实现，可以更清晰地看到它们在存储结构和操作方式上的差异，理解这些差异对于正确选择和使用这两种数据结构至关重要。
