数据结构(C语言版)朱昌杰

### 数据结构(C语言版)朱昌杰 - 栈与队列 #### 3.1 栈 **3.1.1 栈的定义** 栈是一种特殊的线性表，其主要特征在于所有的插入和删除操作都在栈的一端进行，这一端被称为栈顶。栈的另一端是固定的，称为栈底。当栈为空时，我们称其为空栈。 **栈的特性**： - **后进先出 (LIFO)**：最后进入栈的元素总是第一个被移除。 - **先进后出 (FILO)**：最先进入栈的元素总是最后一个被移除。 **栈的基本操作**： - **初始化栈 (`InitStack`)**：创建一个空栈。 - **判断是否为空栈 (`StackEmpty`)**：检查栈是否为空。 - **判断是否为满栈 (`StackFull`)**：检查栈是否已满。 - **获取栈顶元素 (`GetTop`)**：返回栈顶元素。 - **入栈 (`Push`)**：向栈中添加一个新元素。 - **出栈 (`Pop`)**：移除栈顶元素。 **栈的抽象数据类型定义**： ``` ADT Stack { 数据对象 D：D = {ai | ai ∈ ElemSet, i = 1, 2, …, n, n ≥ 0} 数据关系 R：R = {<ai-1, ai> | ai-1, ai ∈ D, i = 2, …, n} 基本操作 P：InitStack(S), StackEmpty(S), StackFull(S), GetTop(S, e), Push(S, e), Pop(S, e) } ``` **3.1.2 栈的顺序存储结构** **顺序栈的类型定义**： 顺序栈通过一段连续的存储空间来存储栈中的元素，通常使用一个足够大的一维数组。栈顶指针 `top` 用于指示栈顶元素在数组中的位置。 ```c #define MAXSIZE 100 typedef struct { Elemtypedef data[MAXSIZE]; int top; } SqStack; ``` - **栈顶指针 `top` 的变化**： - 空栈时，`top = -1`。 - 栈满时，`top = MAXSIZE - 1`。 - 入栈时，`top += 1`。 - 出栈时，`top -= 1`。 **顺序栈的算法实现**： - **初始化栈**：分配内存空间并将栈顶指针置为 `-1`。 ```c int InitStack(SqStack *s) { if ((s = (SqStack *)malloc(sizeof(SqStack))) == NULL) return ERROR; s->top = -1; return OK; } ``` - **判断栈是否为空**：检查栈顶指针是否等于 `-1`。 ```c int StackEmpty(SqStack *s) { return (s->top == -1 ? TRUE : FALSE); } ``` - **判断栈是否已满**：检查栈顶指针是否等于 `MAXSIZE - 1`。 ```c int StackFull(SqStack *s) { return (s->top == MAXSIZE - 1 ? TRUE : FALSE); } ``` - **入栈 (`Push`)**：当栈未满时，在栈顶添加一个新元素。 ```c int Push(SqStack *s, Elemtypedef e) { if (StackFull(s)) return ERROR; s->data[++(s->top)] = e; return OK; } ``` - **出栈 (`Pop`)**：当栈非空时，移除栈顶元素。 ```c int Pop(SqStack *s, Elemtypedef *e) { if (StackEmpty(s)) return ERROR; *e = s->data[(s->top)--]; return OK; } ``` #### 3.2 队列 **队列的基本概念**：队列也是一种特殊的线性表，不同之处在于所有的插入操作都在队列的一端进行，称为队尾；而所有的删除操作都在队列的另一端进行，称为队首。 **队列的特点**： - **先进先出 (FIFO)**：最早进入队列的元素总是第一个被移除。 **队列的基本操作**： - **初始化队列 (`InitQueue`)**：创建一个空队列。 - **判断是否为空队列 (`QueueEmpty`)**：检查队列是否为空。 - **判断是否为满队列 (`QueueFull`)**：检查队列是否已满。 - **获取队首元素 (`GetFront`)**：返回队首元素。 - **入队 (`EnQueue`)**：向队列中添加一个新元素。 - **出队 (`DeQueue`)**：移除队首元素。 **队列的抽象数据类型定义**： ``` ADT Queue { 数据对象 D：D = {ai | ai ∈ ElemSet, i = 1, 2, …, n, n ≥ 0} 数据关系 R：R = {<ai-1, ai> | ai-1, ai ∈ D, i = 2, …, n} 基本操作 P：InitQueue(Q), QueueEmpty(Q), QueueFull(Q), GetFront(Q, e), EnQueue(Q, e), DeQueue(Q, e) } ``` **队列的顺序存储结构**：与顺序栈类似，顺序队列也需要一段连续的存储空间来存储队列中的元素，通常使用一个足够大的一维数组。队首指针 `front` 和队尾指针 `rear` 用于指示队首和队尾元素在数组中的位置。 ```c #define MAXSIZE 100 typedef struct { Elemtypedef data[MAXSIZE]; int front; int rear; } SqQueue; ``` - **队首指针 `front` 和队尾指针 `rear` 的变化**： - 空队列时，`front = 0`，`rear = 0`。 - 队列满时，`rear = MAXSIZE - 1`。 - 入队时，`rear += 1`。 - 出队时，`front += 1`。 **总结** 本章节介绍了栈和队列这两种线性表的特殊形式，它们各自具有独特的插入和删除规则。栈遵循后进先出 (LIFO) 的原则，而队列遵循先进先出 (FIFO) 的原则。通过具体的算法实现，我们可以更好地理解这两种数据结构的特点以及如何有效地利用它们解决实际问题。无论是顺序存储还是链式存储结构，栈和队列都是计算机科学中非常重要的基础数据结构之一，广泛应用于编程和算法设计中。