第三章栈和队列 栈和队列是两种特殊的线性表，是操作受限的线性 表，称限定性DS §3.1栈(stack) ★栈的定义和特点 必定义：1 限定仅在表尾进行插入或删除操作的线性表， 表尾一栈顶，表头一栈底，不含元素的空表称空栈 必特点： 先进后出(FLO)或后进先出(LFO) 进栈 出栈 栈顶 an 栈s=(al,a2,.,an) a2 栈底 al
第三章 栈和队列 栈和队列是两种特殊的线性表，是操作受限的线性 表，称限定性DS §3.1 栈（stack） 栈的定义和特点 ❖定义：限定仅在表尾进行插入或删除操作的线性表， 表尾—栈顶，表头—栈底，不含元素的空表称空栈 ❖特点：先进后出（FILO）或后进先出（LIFO） an a1 a2. 栈底 栈顶 进栈 . 出栈 栈s=(a1,a2,.,an)
★栈的存储结构 冬顺序栈 栈满 栈空 ●实现： 一维数组s[M] top top 5 top F top 5 4 top E 4 top 4 top D top 3 3 3 2 top c top 2 top top B top 0 top=0 栈空 进栈 出栈 设数组维数为M 栈顶指针top,指向实际栈顶 top=O,栈空，此时出栈，则下溢 (underflow) 后的空位置，初值为0 top=M,栈满，此时入栈，则上溢(overflow)
栈的存储结构 ❖顺序栈 ⚫实现：一维数组s[M] top=0 1 2 3 4 5 0 栈空 栈顶指针top,指向实际栈顶 后的空位置，初值为0 top 1 2 3 4 5 0 进栈 A top 出栈 栈满 B C D E F 设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow) top top top top top 1 2 3 4 5 A 0 B C D E top F top top top top top 栈空
●入栈算法 目 Ch3_1.txt ●出栈算法 Ch3 2.txt ●在一个程序中同时使用两个栈 M-1 栈1底 栈1项 栈2顶 栈2底
⚫入栈算法 0 M-1 栈1底 栈1顶 栈2顶 栈2底 ⚫出栈算法 ⚫在一个程序中同时使用两个栈
链栈 栈顶 栈底 top data link ●结点定义 typedef struct node int data; struct node *link; JD: ●入栈算法 周 Ch3 3.txt top 栈底 p ●出栈算法 Ch3 4.txt q top 栈底 top
❖链栈 栈顶 top data link . ^ 栈底 ⚫结点定义 ⚫入栈算法 ⚫出栈算法 typedef struct node { int data; struct node *link; }JD; . ^ 栈底 top top x p top . ^ 栈底 top q
★栈的应用 冬过程的嵌套调用 子过程 主 子过程2 子过程3 r
栈的应用 ❖过程的嵌套调用 r 主 程 序 s r r r s 子 过 程 1 r s t 子 过 程 2 r s t 子 过 程 3