数据结构二版杨枨数据结构：第四章：栈和队列幻灯片.ppt

* 第 * 页 第四章 栈和队列 从逻辑关系的角度来看，栈和队列与线性表相同。 从运算的角度来看，栈和队列的操作是线性表操作的子集。 4.1 栈 4.2 栈的应用 4.3 队列 4.4 队列的应用 4.5 小结 * 第 * 页 4.1 栈 栈的定义 栈是指插入和删除都限定在表尾进行的线性表。 在栈中允许插入、删除的表尾叫做栈顶，不允许插入、删除的表头叫做栈底。 栈的结构 假设，栈Stack =（a1，a2，…，an），则a1为栈底元素，a1为栈顶元素。栈中元素的插入（进栈）次序为a1，a2，…，an。而删除（出栈）次序为an，an-1，…，a1。 栈中元素被处理时，按照先进后出的顺序进行，所以栈又称为先进后出（FILO - First In Last Out）的线性表。 ?图4-1-1栈的结构示意 a1 an a2 栈底 栈顶 进栈 出栈 ? * 第 * 页 4.1 栈 栈的基本操作 1. ? 初始化：生成一个新的空栈。 2. ? 进栈：向栈中加入一个新的元素，作为新的栈顶 3. ? 出栈：取得栈顶元素，并将它从栈中删除。 4. ? 取栈顶元素：取得栈顶元素的值。 5. 判空：判别一个栈是否为空。若为空，返回TRUE；否则，返回FALSE。 * 第 * 页 4.1.1 顺序栈 栈的顺序存储结构简称顺序栈。 利用一组地址连续的存储单元来存放栈中的数据元素。 在C语言中，通常用一维数组来定义顺序栈。 设置栈顶指针来指示栈顶元素的位置。 * 第 * 页 4.1.1 顺序栈（续1） 存储结构定义 #define STACK_SIZE 100 /* 栈的大小 */ typedef struct stack_st { ELEMENT data[STACK_SIZE]; /* ELEMENT为栈中元素的数据类型 */ int top; /* 栈顶元素的指针（下标）*/ } STACKE; 在C语言中，数组下标从0开始，所以，空栈的标志是top = -1。 (a) (b) (c) (d) 图4-1-2栈操作示例 (a)表示空栈，(b)栈中插入A，(c)依次插入B、C、D的情况， (d)从栈中弹出D、C后的情况。 top ? ? ? ? ? top A ? ? ? ? top A D C B ? top A ? ? B ? * 第 * 页 4.1.1 顺序栈（续2） 五种基本操作的实现 * 第 * 页 4.1.2 链接栈 链栈结构形式与单链表相似。 链栈的栈顶指针就是链表的头指针，结点的插入和删除操作只能在此进行。 链栈的所有操作只针对链栈的头部，故链栈不设头结点。 * 第 * 页 4.1.2 链接栈（续1） 链栈的结点结构定义 typedef struct node_st { ELEMENT data; /* 链栈结点的内容 */ struct node_st *next; /* 指向下一个栈元素的指针 */ } NODE; a2 a1 ^ an-1 an top data next 栈底 栈顶 图4-1-3链栈的结构示意 * 第 * 页 4.1.2 链接栈（续2） 五种基本操作的实现 * 第 * 页 4.2 栈的应用 函数调用与栈 递归与栈 迷宫求解 * 第 * 页 4.2.1 函数调用与栈 函数调用与栈 栈在函数调用、递归、语法分析、表达式求值等的实现中都要用到。 在函数调用中，函数调用 -- 返回关系的控制就是通过栈来实现的。 在递归过程中，子程序间的信息传递和控制转移也是通过栈来实现的。 * 第 * 页 4.2.2 递归与栈 递归是一种重要的程序设计方法。 如果在一个函数、过程或数据结构的定义内部又直接或间接地应用了定义本身，则称它们是递归的。 递归可以分为直接递归和间接递归两种。 例如，在常见的函数递归调用中，直接调用时，在函数内有调用本函数的语句，当执行到这条语句时，程序将会转到本函数的第1行重新开始执行本函数。 间接调用时，在f1函数内，先调用f2函数，在执行f2函数中，又有调用f1的函数。 f函数 调用f函数 f1函数 调用f2函数 调用f1函数 f2函数 直接调用本函数 图4-5 函数的递归调用 间接调用本函数 * 第 * 页 4.2.2 递归与栈（续1） 一个递归函数的运行类似于多个函数的嵌套调用。 系统设定一个递归工作栈，每进入一层递归调用时，将相应的信息（函数返回值及返回地址）压入栈顶，而每退出一层递归时，栈顶元素就是要返回的地址。 （1）调用 power(3) 时 函数返回地址r2 函