计算机软件技术基础教师：曾晓东
计算机软件技术基础 教 师：曾晓东
3.4栈一、栈的定义二、栈的运算三、 栈的存储结构及算法四、栈的应用数据结构一一栈和队列计算机软件技术基础
3.4 栈 一、栈的定义 二、栈的运算 三、栈的存储结构及算法 四、栈的应用 计算机软件技术基础 数据结构——栈和队列
栈的定义一、木进栈出栈栈是限定只能在表的一端进行插anstack[n-1]top入和册删除操作的线性表。允许插栈an-1入和删除的一端称为栈顶（top），顶另一端称为栈底（bottom）。设栈s=(ai,a2,..an），ai称为栈底元素，a.称为栈顶元素。栈中元素按ai,a2,..·，an次序进栈，又按an2·：·，a2,ai次序退栈。栈底stack[0]a1因此栈的操作特点是：后进先出（LIFO）；n=O时称为空栈。计算机软件技术基础数据结构一一栈和队列
一、栈的定义 ▪ 栈是限定只能在表的一端进行插 入和删除操作的线性表。允许插 入和删除的一端称为栈顶(top)， 另一端称为栈底(bottom)。 ▪ 设栈s=(a1,a2,.,an)，a1称为 栈底元素，an称为栈顶元素。 ▪ 栈中元素按a1,a2,.,an次序进 栈，又按an,.,a2,a1次序退栈。 因此栈的操作特点是：后进先出 （LIFO）；n=0时称为空栈。 an a n-1 a1 stack[n-1] top 栈 顶 进栈 stack[0] 栈底 出栈 计算机软件技术基础 数据结构——栈和队列
一栈的运算1.初始化栈INISTACK（S）将栈S置成空栈2.判空栈ISEMPTY（S）若栈S是空栈，返回“真”，否则返回“假”3.进栈PUSH(S, X)在栈S顶部插入（压入）元素X4.出栈POP (S)若栈S不空，删除顶部元素5.取栈顶GETTOP (S)取栈顶元素，并不改变栈中内容计算机软件技术基础数据结构一一栈和队列
二、栈的运算 1.初始化栈 INISTACK(S) 将栈S置成空栈 2.判空栈 ISEMPTY(S) 若栈S是空栈，返回“真”， 否则返回“假” 3.进栈 PUSH(S,x) 在栈S顶部插入（压入）元素x 4.出栈 POP(S) 若栈S不空，删除顶部元素 5.取栈顶 GETTOP(S) 取栈顶元素，并不改变栈中内容 计算机软件技术基础 数据结构——栈和队列
三、栈的存诸结构及算法1.顺序栈1)类型定义顺序栈用向量作为栈的存储结构，可用一维数组s[1:m表示。其中m表示栈的最大容量。用一个简单变量top来指示栈顶位置，称为栈顶指示器。top=0表示栈空top=m表示栈满类型定义struct SeqStack{elemtype stack[MAXSIZE]int top;产计算机软件技术基础数据结构一一栈和队列
三、栈的存储结构及算法 1.顺序栈 1)类型定义 ▪ 顺序栈用向量作为栈的存储结构，可用一维数组s[1:m] 表示。其中m表示栈的最大容量。用一个简单变量top来 指示栈顶位置，称为栈顶指示器。top=0表示栈空， top=m表示栈满。 ▪ 类型定义 struct SeqStack{ elemtype stack[MAXSIZE]; int top; }; 计算机软件技术基础 数据结构——栈和队列