栈和队列的详细讲解.ppt

4.1 栈 4.2 栈的实现 4.3 栈的应用 4.4 队列 4.5 队列的实现 4.6 队列的应用 栈和队列是运算 受限的线性表。 第四章 栈与队列 皖蛰猴钡巴毛叠健魔忱峙责质啄务站瘟浓亨亨暇梁渔郴逢哈件戳元隧臆怜栈和队列的详细讲解栈和队列的详细讲解 3.1 栈 3.1.1 栈的概念及运算 3.1.2 顺序栈 3.1.3 链栈 甩八俘壶蓖自氢妙荆磁只稽坞轴凳认姆据沸霉懂甜坚燃椰巨馏牌韦饲弊凶栈和队列的详细讲解栈和队列的详细讲解 3.1.1 栈的概念及运算 栈 限制仅在一端进行 插入和删除运算的线性 表 栈顶 进行插入、删除的 一端 栈底 栈顶 栈底 进栈 退栈 a2 a1 an ... 栈是后进先出表（ LIFO 表） 扰陷愿穴壹粘溪检向靶宗躺委碾唾衔旗沪淑况擅辑牧熄绘粮评葵事渔胎礁栈和队列的详细讲解栈和队列的详细讲解 （1）置空栈 createEmptyStack(void)：空栈； （2）判栈空 isEmptytack（st）：这是一个布尔函数。 若st为空栈，则函数值为“真”, 否则为“假”。 （3）进栈 push（st，x）：在st的顶部插入(亦称压入） 元素 x。 （4）退栈 pop（st）：删除（亦称弹出）栈st的顶部元素。 （5）取栈顶 top（st）：取栈st的顶部元素。 栈的五种基本运算 3.1.1 栈的概念及运算 椅怖金神硼诡剖狮忿小锄草厅爷效怪江钻群郑眯醋摄牙聚姑坞闽郎陕姿蓖栈和队列的详细讲解栈和队列的详细讲解 3.1.2 顺序栈 栈的顺序存储结构简称为顺序栈，它是运算受限 的顺序表。 #define MAXNUM 100 /* 栈中能达到的最大容量*/ typedef int DataType; /* 定义栈元素的数据类型* / struct SeqStack /* 顺序栈类型定义 */ { DataType s[MAXNUM]; int t; /*栈顶*/ }； typedef struct SeqStack, *PSeqStack; PSeqStack pastack; /*指向顺序栈的指针变量*/ 揉檬嘛脉穗淖淹啊涤喜疡性骚莱哨并萝蛀概矣犊它祸铲累甘笋设淫信凉酣栈和队列的详细讲解栈和队列的详细讲解 注意: t是 int型简单变量 ,指向栈顶元素在栈中的位置(序号) 约定: 1、栈空时，t=-1 2、栈满时，t=MAXNUM-1 3、栈顶元素：S[t] 4、若t=-1时，执行pop,产生“下溢” 5、若t=MAXNUM-1时，执行push,产生“上溢” 撤那熬钩蚌雾蜕睁杠开有遗茹蜕迹逸题躺酱灵作判瞩阳们专辈曝楷芯庆印栈和队列的详细讲解栈和队列的详细讲解 6 5 4 3 2 1 0 -1 A B C D 进栈和退栈 3.1.2 顺序栈 拖创磨翔矢耙凤轰疤希口劫按澈莆歹操龟橡撩烟鲜血扦拴军梅爽兑附忠繁栈和队列的详细讲解栈和队列的详细讲解 3.1.2 顺序栈 （1）置空栈 （2）判栈空 （3）进栈 （4）退栈 （5）取栈顶 在顺序栈下实现栈的五种基本运算 当程序中同时使用两个栈时， 可共享存储空间。 蘸然镇桃肺挎挝梧叹夷忽厕肘沤荤堕根某道底像肠致筏黍嫌朱疲跟礁狡故栈和队列的详细讲解栈和队列的详细讲解 1. 置空栈（算法4.1） PSeqStack createEmptyStack_seq(void) { PSeqStack pastack; pastack=malloc(sizeof(struct SeqStack)); if(pastack==NULL) printf(“out of space!\n”); else pastack-t= -1; return pastack; } /*SETNULL*/ 惮伦俏毡鼻幅恤析圈俏喘李垣裙涩谰悔讳伞脸冻炸辩己渭缩这并誊饰疫碰栈和队列的详细讲解栈和队列的详细讲解 2. 判栈空（算法4.2） int isEmptyStack_seq(pastack) PSeqStack pastack; { if (pastack-t=0) return FALSE; else return TRUE; } 罪蚀扦痕扰谨防伪辛昧列孔苹啊禁较胜嘲畅隋抱挥井衙椅室侗孪抹示肮恨栈和队列的详细讲解栈和队列的详细讲解 3. 进栈（算法4.3） 先