算法与数据结构课件PPT第三章

【栈和队列的概念】 栈和队列是两种基本的线性数据结构，它们都是操作受限的线性表。栈（Stack）具有“后进先出”（LIFO，Last In First Out）或“先进后出”（FILO，First In Last Out）的特性，即新加入的数据元素（入栈）通常会在旧元素之前被移除（出栈）。在栈中，插入（push）和删除（pop）操作只允许在栈顶进行。 队列（Queue）则遵循“先进先出”（FIFO，First In First Out）或“后进后出”（LILO，Last In Last Out）原则，意味着最先添加到队列的数据元素会首先被移除。在队列中，插入（enqueue）发生在队尾，删除（dequeue）发生在队头。 【栈混洗】 栈混洗是指当n个数据元素按顺序进入栈中，然后随机出栈，形成的任意出栈序列。例如，如果有三个元素(i, j, k)依次入栈，可能的出栈顺序有(i, j, k), (k, j, i), (i, k, j), (j, i, k), (j, k, i)。但是，(k, i, j)是不可能的出栈顺序，因为它违反了栈的后进先出原则。一般地，对于长度为n的输入序列，每个合法的栈混洗都对应着一个push和pop操作的序列，只要满足在任何时候，push的次数不小于pop的次数，该序列就是一个有效的栈混洗。 【顺序栈】 顺序栈是栈的一种实现方式，它使用一组连续的内存空间来存储数据元素。栈顶的指示器（top）用于追踪当前栈顶的位置。在初始状态下，空栈的top值为-1。当元素入栈时，top指针加1，而出栈时top指针减1。顺序栈的元素下标通常从0开始。 在C语言中，我们可以这样定义一个顺序栈的结构： ```c typedef int DataType; struct Stack { int MAX; // 最大容量 int top; // 栈顶指针 DataType *elem; // 存放元素的数组起始指针 }; typedef struct Stack *SeqStack; // 定义顺序栈类型 ``` 创建顺序栈的函数可以如下编写： ```c SeqStack SetNullStack_Seq(int m) { SeqStack sstack = (SeqStack)malloc(sizeof(struct SeqStack)); if (sstack != NULL) { sstack->elem = (DataType *)malloc(sizeof(DataType) * m); if (sstack->elem != NULL) { sstack->MAX = m; // 顺序栈最大容量 sstack->top = -1; // 设置栈顶初值为-1 return sstack; } else { free(sstack); return NULL; } } else { printf("out of space"); return NULL; } } ``` 判断顺序栈是否为空的函数可以这样实现： ```c int IsNullStack(SeqStack sstack) { return (sstack->top == -1); } ``` 顺序栈的入栈操作（Push_seq）需要检查栈是否已满，如果未满则进行插入操作： ```c void Push_seq(SeqStack sstack, int x) { if (sstack->top >= (sstack->MAX - 1)) // 检查栈是否满 printf("Stack is full\n"); else { sstack->top++; // 修改栈顶指针 sstack->elem[sstack->top] = x; // 入栈 } } ``` 这些基础知识构成了算法与数据结构课程中的重要部分，理解和掌握它们对于后续学习和解决实际问题至关重要。无论是编程竞赛、软件开发还是系统设计，栈和队列都是解决许多问题的有效工具。通过深入理解这些概念，你可以更好地运用它们来处理递归、回溯、动态规划等问题，以及在内存管理、任务调度等领域发挥重要作用。