算法与数据结构课件第3章 栈和队列.pptVIP

第3章 栈和队列 栈和队列的特点 两者的逻辑结构与线性表相同，但是插入和删除操作受到了限制，称为操作受限的线性表； 栈只允许在线性表的一端进行插入和删除操作，队列则允许在一端插入另一端删除； 栈按照“后进先出”的规则进行操作，队列则按照“先进先出”的规则进行。 3.1 栈 3.1.1 栈的定义及其基本运算 定义 限制在表的一端进行插入和删除操作的线性表； 表中允许进行插入、删除操作的一端称为栈顶，另一个固定端称为栈底。 当栈中没有数据元素时，称为空栈。 操作原则 后进先出（Last In First Out）, LIFO 先进后出（ First In Last Out）, FILO 举例 穿衣、脱衣过程； 餐馆洗好的一叠盘子； 建筑工地上使用的砖； 函数的嵌套调用； 栈的示意图 练 习 1 依次输入3个元素A、B、C到栈中，可得到哪几种不同的输出？ 解：共5种 (1) A,B,C (2) A,C,B (3) B,A,C (4) B,C,A (5) C,B,A 栈结构的基本操作 （1）栈初始化 Init_Stack(s) （2）判栈空 Empty_Stack (s) （3）入栈 Push_Stack(s,x) （4）出栈 Pop_Stack(s) （5）读栈顶元素 Top_Stack(s) 3.1.2 栈的存储结构和基本运算的实现 顺序存储结构：顺序栈 链式存储结构：链栈 1. 顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素； 在数组上实现时，栈底位置可以设置在数组的任一个端点（通常设置在0下标处），而栈顶是随着插入和删除而变化的，可以用一个整形变量top指示栈顶元素在顺序栈中的位置； 数据入栈或出栈时，整形变量 top分别执行加1或减1的操作。 顺序栈的类型描述 顺序栈基本操作的实现 ⑴ 置空栈 【算法思想】首先建立栈空间，然后初始化栈顶指针。 SeqStack *Init_SeqStack() { SeqStack *s; s=malloc(sizeof(SeqStack)); s-top= -1; return s; } 时间复杂度为O(1) ⑵ 判空栈 int Empty_SeqStack(SeqStack *s) { if (s-top= = -1) return 1; else return 0; } ⑶ 入栈 int Push_SeqStack (SeqStack *s, datatype x) { if (s-top= =MAXSIZE-1) return 0; //栈满不能入栈 else { s-top++; s-data[s-top]=x; return 1; } } ⑷ 出栈 int Pop_SeqStack(SeqStack *s, datatype *x) { if (Empty_SeqStack ( s ) ) return 0; //栈空不能出栈 else { *x=s-data[s-top]; s-top--; return 1; } } ⑸ 取栈顶元素 datatype Top_SeqStack(SeqStack *s) { if ( Empty_SeqStack ( s ) ) return 0; /*栈空*/ else return (s-data[s-top] ); } 注意: 取栈顶元素与出栈的操作是不同的，虽然取得了栈顶元素，但是指针没有改变。 2. 链栈 若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。 用链式存储结构实现的栈称为链栈。 通常链栈用单链表表示，因此其结点结构与单链表的结构相同。 链栈的栈顶？ 链栈示意图 ⑴ 置空栈 LinkStack Init_LinkStack（） { return NULL; } ⑵ 判栈空 int Empty_LinkStack（LinkStack top ） { if（top==NULL） return 1; else return 0; } ⑶ 入栈 LinkStack Push_LinkStack（LinkStack top, datatype x） { StackNode *s;