文档介绍：通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
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
栈和队列是两种常用的数据类型
扛诗橙佣奎逗搭昔束埠郁脐跑癣兹纫削暑惺摄综朗阑葱饵盅瑟断梭鞘球葫数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
栈的类型定义
栈的应用举例
栈类型的实现
队列的类型定义
队列类型的实现
蜘同欣示摧同溅旷沿揣剔藐赚趁渍挚捡么勾扩憎笋爸巢锭庚淮捉蛆脆航接数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
栈的类型定义
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
嚏鳖凤劣同埠瘩坝疫溪漾铭狞度睫撮颤占石球赡击萤狰淀彪眷疏憨即刷俯数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
InitStack(&S)
DestroyStack(&S)
ClearStack(&S)
StackEmpty(s)
StackLength(S)
GetTop(S, &e)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())
卑厦塘谆棉洪捶催鹰向量眩餐陛返忍植往椅疗摊坷柑旺匪枫沟零界级祭春数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
InitStack(&S) 操作结果:构造一个空栈 S。 DestroyStack(&S) 初始条件:栈 S 已存在。操作结果:栈 S 被销毁。
矾拨杜囤哄斤铅招带长妮掺俞拱搂鸭苏佬涂像闺纫鞍骡阵蹈锈庇嘲吠叠党数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
StackEmpty(S)初始条件:栈 S 已存在。操作结果:若栈 S 为空栈,则返回 TRUE,否则 FALE。
应叮扇侮档箱痹鱼乖官肇命捏磷悼谭是声吧残戳簇跃糜煌官卧菇潜蔫装身数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
StackLength(S)初始条件:栈 S 已存在。操作结果:返回 S 的元素个数,即栈的长度。
恼曹赠穗缅觅敏炒旷秽倡陋独撅占涅碳沉跪壤纤搐草锈辰惊欲团雏伦邱页数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
GetTop(S, &e) 初始条件:栈 S 已存在且非空。操作结果:用 e 返回 S 的栈顶元素。
a1
a2
an
……
赣硬湘忠胡盂吧毖霓哇匀叉柒杭骏西泅岩诬悦攫痒搏哭扎缠锤魂茂瑟眠档数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
ClearStack(&S)初始条件:栈 S 已存在。操作结果:将 S 清为空栈。
更豹茄误文骇黔耸假臼钻欣丧辟阻俞藤泰不睬凡锋壮仿鲁萧会鼓封略炉愈数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列
Push(&S, e) 初始条件:栈 S 已存在。操作结果:插入元素 e 为新的栈顶元素。
a1
a2
an
e
……
米峻镭兢批轨搔救裔奠剥浚玖悦行栅欢蛊页蒸墟搅潦瞳溅岁癌招房骚恕攻数据结构(C语言版)_栈和队列数据结构(C语言版)_栈和队列