第3章栈与队列
第3章 栈与队列
目录 栈 2,栈的应用举例 3.栈与递归 k4,队列 5应用实例
目录 1.栈 2. 栈的应用举例 3. 栈与递归 4. 队列 5. 应用实例
3.1 栈 311栈的定义及其运算 栈(Stak)是限定插入和删除运算只能在表尾 进行的线性表。 通常称允许插入、删除的这一端为栈顶,另一端 称为栈底。 当表中没有元素时称为空栈。 其中数据元素的个数n定义为表的长度
3.1 栈 3.1.1 栈的定义及其运算 栈（Stack）是限定插入和删除运算只能在表尾 进行的线性表。 通常称允许插入、删除的这一端为栈顶，另一端 称为栈底。 当表中没有元素时称为空栈。 其中数据元素的个数n定义为表的长度
图3.1是一个栈的示意图,通常用指针top指示栈顶的位 置,用指针 bottom指向栈底。栈顶指针top动态反映栈 的当前位置。 进栈 出栈 图3.1所示的栈中,元素是以a1, a ,an的顺序进栈,而出栈 栈顶 的次序却是an,an1,…,a1 也就是说,栈的修改是按后进先 a2 ai 出的原则进行的。因此,栈又称为 图3.1栈栈底 后进先出( Last in first out)的线性表,简称为 LIFO表
图3.1是一个栈的示意图，通常用指针top指示栈顶的位 置，用指针bottom指向栈底。栈顶指针top动态反映栈 的当前位置。 图3.1所示的栈中，元素是以a1， a2，…，an的顺序进栈，而出栈 的次序却是an，an-1，…，a1。 也就是说，栈的修改是按后进先 出的原则进行的。因此，栈又称为 后进先出（Last In First Out）的线性表，简称为 LIFO表
栈的ADT声明如下: ADTS七ack i Typedef struct Stack s; Initstack(s, maxSize)i 说明:构造空栈S,即栈的初始化 Stacks主ze(S); 说明:求栈中元素的数目 isEmpty(s) 说明:判栈s是否为空栈 isFull(s) 说明:判栈s是否已“满
ADT Stack { Typedef struct Stack S; InitStack(S,maxSize); 说明：构造空栈S，即栈的初始化 StackSize(S); 说明：求栈中元素的数目 isEmpty(S); 说明：判栈S是否为空栈 isFull(S); 说明：判栈S是否已“满” 栈的ADT声明如下：