栈与队列：数据结构中的 孪生兄弟 的本质差异

个人主页-爱因斯晨

文章专栏-数据结构

文章目录

• 个人主页-爱因斯晨
• 文章专栏-数据结构
• 1. 引言
• 2. 栈和队列的概念界定
  • 2.1 栈
  • 2.2 队列
• 3. 栈和队列的核心差异
• 4. 栈的 C 语言实现
  • 4.1 栈的结构体定义
  • 4.2 栈的基本操作函数
    • 4.2.1 初始化栈
    • 4.2.2 判断栈是否为空
    • 4.2.3 判断栈是否已满
    • 4.2.4 入栈操作
    • 4.2.5 出栈操作
• 5. 队列的 C 语言实现
  • 5.1 队列的结构体定义
  • 5.2 队列的基本操作函数
    • 5.2.1 初始化队列
    • 5.2.2 判断队列是否为空
    • 5.2.3 判断队列是否已满
    • 5.2.4 入队操作
    • 5.2.5 出队操作
• 6. 栈和队列操作的差异总结
• 7. 结论
• 7. 结论

1. 引言

在数据结构中，栈和队列是两种重要的线性结构，它们在数据的存储和操作方式上有着显著的不同，各自适用于不同的应用场景。本文将详细阐述栈和队列的概念、差异，并通过 C 语言实现示例，帮助读者深入理解这两种数据结构。

2. 栈和队列的概念界定

2.1 栈

栈是一种遵循 “后进先出”（Last In First Out，LIFO）原则的线性数据结构。它只允许在一端进行插入和删除操作，这一端被称为栈顶，另一端则被称为栈底。

例如，日常生活中叠放的盘子，最后放在上面的盘子可以最先被拿走，这就是栈的典型体现。

2.2 队列

队列是一种遵循 “先进先出”（First In First Out，FIFO）原则的线性数据结构。它允许在一端进行插入操作（队尾），在另一端进行删除操作（队头）。

就像在银行柜台前排队办理业务的人群，先排队的人先办理业务，后排队的人需要等待前面的人办理完毕，这符合队列的特性。

3. 栈和队列的核心差异

4. 栈的 C 语言实现

4.1 栈的结构体定义

#include<stdio.h>#include<stdlib.h>#defineSTACK_SIZE50// 栈的最大容量typedefstruct{int data[STACK_SIZE];// 用于存储栈中元素的数组int top;// 栈顶指针，指向栈顶元素所在位置} Stack;

4.2 栈的基本操作函数

4.2.1 初始化栈

// 功能：初始化栈，使栈为空// 参数：stack - 指向栈结构体的指针voidInitStack(Stack *stack){ stack->top =-1;// 栈顶指针为-1时，表示栈为空}

4.2.2 判断栈是否为空

// 功能：判断栈是否为空// 参数：stack - 指向栈结构体的指针// 返回值：1 - 栈为空；0 - 栈不为空intIsEmpty(Stack *stack){return stack->top ==-1;}

4.2.3 判断栈是否已满

// 功能：判断栈是否已满// 参数：stack - 指向栈结构体的指针// 返回值：1 - 栈已满；0 - 栈未满intIsFull(Stack *stack){return stack->top == STACK_SIZE -1;}

4.2.4 入栈操作

// 功能：向栈顶插入元素// 参数：stack - 指向栈结构体的指针；value - 要插入的元素值// 返回值：1 - 入栈成功；0 - 入栈失败（栈已满）intPush(Stack *stack,int value){if(IsFull(stack)){return0;} stack->top++; stack->data[stack->top]= value;return1;}

4.2.5 出栈操作

// 功能：从栈顶删除元素，并返回该元素值// 参数：stack - 指向栈结构体的指针；value - 用于存储出栈元素值的指针// 返回值：1 - 出栈成功；0 - 出栈失败（栈为空）intPop(Stack *stack,int*value){if(IsEmpty(stack)){return0;}*value = stack->data[stack->top]; stack->top--;return1;}

5. 队列的 C 语言实现

5.1 队列的结构体定义

#include<stdio.h>#include<stdlib.h>#defineQUEUE_SIZE50// 队列的最大容量typedefstruct{int data[QUEUE_SIZE];// 用于存储队列中元素的数组int front;// 队头指针，指向队头元素int rear;// 队尾指针，指向队尾元素的下一个位置} Queue;

5.2 队列的基本操作函数

5.2.1 初始化队列

// 功能：初始化队列，使队列为空// 参数：queue - 指向队列结构体的指针voidInitQueue(Queue *queue){ queue->front =0; queue->rear =0;}

5.2.2 判断队列是否为空

// 功能：判断队列是否为空// 参数：queue - 指向队列结构体的指针// 返回值：1 - 队列为空；0 - 队列不为空intIsQueueEmpty(Queue *queue){return queue->front == queue->rear;}

5.2.3 判断队列是否已满

// 功能：判断队列是否已满// 参数：queue - 指向队列结构体的指针// 返回值：1 - 队列已满；0 - 队列未满intIsQueueFull(Queue *queue){return(queue->rear +1)% QUEUE_SIZE == queue->front;}

5.2.4 入队操作

// 功能：向队尾插入元素// 参数：queue - 指向队列结构体的指针；value - 要插入的元素值// 返回值：1 - 入队成功；0 - 入队失败（队列已满）intEnQueue(Queue *queue,int value){if(IsQueueFull(queue)){return0;} queue->data[queue->rear]= value; queue->rear =(queue->rear +1)% QUEUE_SIZE;return1;}

5.2.5 出队操作

// 功能：从队头删除元素，并返回该元素值// 参数：queue - 指向队列结构体的指针；value - 用于存储出队元素值的指针// 返回值：1 - 出队成功；0 - 出队失败（队列为空）intDeQueue(Queue *queue,int*value){if(IsQueueEmpty(queue)){return0;}*value = queue->data[queue->front]; queue->front =(queue->front +1)% QUEUE_SIZE;return1;}

6. 栈和队列操作的差异总结

7. 结论

栈和队列作为两种重要的线性数据结构，由于其操作规则的不同，在实际应用中有着不同的用途。栈适用于需要 “后进先出” 特性的场景，如函数调用、表达式求值等；队列适用于需要 “先进先出” 特性的场景，如任务调度、缓冲处理等。

|
| 指针变化 | 仅栈顶指针变化 | 队头和队尾指针均可能变化（循环队列中通过取模实现循环） |

7. 结论

栈和队列作为两种重要的线性数据结构，由于其操作规则的不同，在实际应用中有着不同的用途。栈适用于需要 “后进先出” 特性的场景，如函数调用、表达式求值等；队列适用于需要 “先进先出” 特性的场景，如任务调度、缓冲处理等。

通过 C 语言的实现，可以更清晰地看到它们在存储结构和操作方式上的差异，理解这些差异对于正确选择和使用这两种数据结构至关重要。