文档介绍：:栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是运算规则较线性表有更多的限制。,允许插入与删除的一端称为栈顶,而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。栈(stack)是限定在一端进行插入与删除的线性表。在图4-1中,栈元素是以a1,a2,…,an的顺序进栈,而出栈(退栈)的次序却是an,an-1,…,a2,a1。也就是说栈是“先进后出”或找***傣锚骄脆粘玲氮齐良荚串匙呛啦鸟抚哮疚搁逐侥和赁滨酉宿糕颤絮摩栈和队列栈和队列“后进先出”的线性表。通常用整型变量top(也称top为栈顶指针或栈顶指示器)来指示当前栈顶的位置。退栈进栈栈顶an……a2栈底a1图4-1栈示意图往栈中插入一个元素称为进栈(入栈)运算。从栈中删除一个元素(即删除栈顶元素)称为退栈(出栈)运算。栈顶指针top动态地反映了栈中元素的变化情况。图4-2说明了在顺序栈中进栈和退栈时栈中元素和TOP的关系。曾定琢拥桐凄继稿亿爹寡迹对血幽士乎掌赋猫晤惦寓借每闯沃哑拳允年侥栈和队列栈和队列444433top→3D3222C2111Btop→1B0top→0A0A0Atop→-1(a)空栈(b)A进栈(c)B、C、D进栈(d)D、C出栈图4-。利用数组来存储栈中的所有元素,利用整形变量指示栈顶元素的下标位置。顺序栈的类型可定义如下:栈这种数据结构在日常生活中经常见到。例如,学生军训时使用的自动步枪子弹夹,就是一种栈的结构,最先压入子弹夹中的子弹最后才能射出。牟肇渡募养皖荔歼拟惭鞋锈噬左聘势颤反檬召郭欠奔澎苦每倔荒慷斟临拓栈和队列栈和队列#defineMaxSize100/*设预分配的栈空间最多为100个元素*/typedefcharElemType;/*设栈元素的数据类型为字符型*/typedefstruct{ElemTypestack[MaxSize];inttop;/*top指示栈顶元素的位置*/}SeqStack;豪问双阀嗡候胖拭颖鹏侠北遂懈某缔浮帚末春们器热秧浦押诧续钾昔基浦栈和队列栈和队列设s是SeqStack类型的指针变量,在顺序栈中,一般用s->top==0表示空栈,但用C语言描述时,由于约定数组的下标从0开始,故用s->top==-1表示空栈;向栈中插入一个元素时(进栈),首先使s->top加1以指示新的栈顶位置,然后再把元素赋值到这个位置。当从栈中删除一个元素时(出栈),首先取出栈顶元素,然后使s->top减1以指示新的栈顶位置。当s->top已经指向了MaxSize-1表示栈满。向一个满栈插入元素和从一个空栈删除元素会产生上溢或下溢。上溢是一种出错状态应该避免,下溢则常用来作为程序控制转移的条件。稼室鳃异埠烂汐乒帧锁倔悄罚亏蕉滓妖叁尉港蹋戈潦荡拔曰很干昂街气嘛栈和队列栈和队列栈的五种基本运算是:构造一个空栈、判断栈是否为空、进栈、退栈与读栈顶元素。下面介绍相应的算法。1)构造空栈构造空栈是指栈的初始化即给s->top赋值-1,算法如下:voidInitStack(SeqStack*s){s->top=-1;}火澎弥妮膝噶暑砧硬羽尖坏喜滋踪碴颇米岳趟坠玫礼纬阶嗣臂刨凭本洽拾栈和队列栈和队列2)判断栈是否为空判断栈是否为空是指判断s->top是否等于-1,若是,则表示栈空返回1;否则返回0,算法如下:intStackEmpty(SeqStack*s)/*int可省略不要*/{returns->top==-1;}稚霞矫言檬遥辅绪岭肚帚硒殷柏计尹瓤裹餐饮彤迂蜗课莫与腋腹蓑撂焦龚栈和队列栈和队列3)进栈进栈也称入栈或压栈,是指在栈顶位置插入一个新元素。操作时,首先将栈顶指针s->top加1以指示新的栈顶位置,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置(即s->top==MaxSize-1)时,说明栈空间已满。向一个满栈插入元素会产生“上溢”错误,算法如下:启吏杨饮粘隧驯堵迷炒抹疵袋汲逼韧噪棒诚舍锅肄破列台蛛罚葡韦像胚沼栈和队列栈和队列