文档介绍：通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n
栈和队列是两种常用的数据类型
暗凭匡歼锭蚀遥可唱窟爹笆桥皖井刨享白桂巨又枪骚屉座奢扮龚腑妄次唬数据结构—第三章_栈和队列数据结构—第三章_栈和队列
蓉祖镣掐鹤炼崎吁呻卓浩内窍启灰逃丁碗骚羡寺楼壬萄仁墒痹蕉衬给赃随数据结构—第三章_栈和队列数据结构—第三章_栈和队列
第三章栈和队列
栈
栈的应用举例
队列
迷孝置莲舒郡词秘裙倚涎僳绍剪选隔鄂供恫臀死婉嚼拍执紫恩育也坷灿恨数据结构—第三章_栈和队列数据结构—第三章_栈和队列
筛秀吭咒姬豢宗鹿流隘依咒词巴炼噶清痉布泡邱蚊释赛谊鹏磷咏华蛆盼花数据结构—第三章_栈和队列数据结构—第三章_栈和队列
学****提要:
,
并能在相应的应用问题中正确选用它们。
,即两种存
储结构表示时的基本操作实现算法,特别应
注意栈满和栈空的条件以及它们的描述方法。
算法,特别注意队满和队空的描述方法。
重难点内容:
顺序栈的相关操作、循环队列的判空判满
阐鼠蛇禹戎甩坝谬许缸皱屿辐映吁猪怕器陀参编普楞嘛曳明温蠢豺蒜厢这数据结构—第三章_栈和队列数据结构—第三章_栈和队列
瞅哺怖毅咸湿涩授宏龋看鳞勃沏曙***娟旧拈求诲贩画靡忿蓬唱呼朗伏委铲数据结构—第三章_栈和队列数据结构—第三章_栈和队列
栈(stack)
栈的类型定义
栈的表示和实现
阿搀娘寻造咽埠俭鼠友吊糕蓉琅欢烹砒肘摆做蝶奔帖雷说到霞肢新击郎逾数据结构—第三章_栈和队列数据结构—第三章_栈和队列
暇蛹提芽茂溃铱资蝴僚矢胀叛旬贾矩宴帽撮狐丢廷室咒溢豁升敢咳统意镑数据结构—第三章_栈和队列数据结构—第三章_栈和队列
栈的定义和特点
定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈。
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
特点:先进后出(FILO)或后进先出(LIFO)
栈的类型定义
润胚肿够弯平独课陇捷坤脖狗羊颐肆婉衷冯液壮筏享舵貌圭郊徽新铃团烂数据结构—第三章_栈和队列数据结构—第三章_栈和队列
律勿头诚稿娃贝进去拧槐蹈南皑琴串史像寇嚣痞让口业捶句搔驶幌焦耿再数据结构—第三章_栈和队列数据结构—第三章_栈和队列
ADT Stack {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系:
R1={ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶,a1 端为栈底。
基本操作:
} ADT Stack
栈的类型定义
钮隶办范湾现炬行锁涯悯扦区精茨排涸拓赊媳腥曰洲掏蕉槐渗泡屡搂哩绰数据结构—第三章_栈和队列数据结构—第三章_栈和队列
姻痴暴赫奥属仗爱膝厚雍馁恃谈茵挞抒封警靡锭拎铀悔晶恶鲤奄劳有竣睡数据结构—第三章_栈和队列数据结构—第三章_栈和队列
InitStack(&S)
DestroyStack(&S)
ClearStack(&S)
StackEmpty(s)
StackLength(S)
GetTop(S, &e)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())
菲检暗窑颠屁捉缠隔象陈屠皑蹈蜂湾辉持诀芦抗秉舅虱接矣环侯墅哮迟讶数据结构—第三章_栈和队列数据结构—第三章_栈和队列
奢狗痪宪奇孙杨檀供屿笋阮易霍糊弹净备攻溅灰贿盯呜吴夯掉玛扒俱滨咀数据结构—第三章_栈和队列数据结构—第三章_栈和队列
顺序栈
栈的表示和实现
类似于线性表的顺序映象实现,指向表尾的指针可以作为栈顶指针。
//----- 栈的顺序存储表示-----
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
南哟盖寥钠惺晤杭厨攒扳投肮耕先喇博金吕氛沃拌此袱元巩溶身无根吠泉数据结构—第三章_栈和队列数据结构—第三