北京师范大学《数据结构——C语言描述》教学课件：第三章 栈和队列

第三章栈和队列 数据结构(C描述)

第三章 栈和队列 数据结构（C描述）

目录 3.1栈 3,2队列 退出

3.1 栈 3.2 队 列 退 出 目 录

31栈( STACK) 311栈的定义 栈( stack)--是限制线性表中元素的插入和删除 只能在线性表的同一端进行的一种特殊线性表 允许插入和删除的一端,称为栈顶(Top); 另一端为固定的一端,称为栈底( Bottom)l

3.1 栈（STACK） 3.1.1 栈的定义 栈(stack)---是限制线性表中元素的插入和删除 只能在线性表的同一端进行的一种特殊线性表。 允许插入和删除的一端，称为栈顶(Top)； 另一端为固定的一端，称为栈底(Bottom)

3.11栈的定义 根据栈的定义可知,最先放入栈中元素在栈底, 最后放入的元素在栈顶,而删除元素刚好相反, 最后放入的元素最先删除,最先放入的元素最后 删除。 也就是说,栈是一种后进先出( Last In first Out) 的线性表,简称为LIFO表

3.1.1 栈的定义 根据栈的定义可知，最先放入栈中元素在栈底， 最后放入的元素在栈顶，而删除元素刚好相反， 最后放入的元素最先删除，最先放入的元素最后 删除。 也就是说，栈是一种后进先出(Last In First Out) 的线性表，简称为LIFO表

311栈的定义 栈顶top

3.1.1 栈的定义 an ... a2 a1 栈顶 top

x产31.1栈的定义 ↓举例1:家里吃饭的碗,通常在洗干净后一个 个地落在一起存放,在使用时,若一个一个 入地拿,一定最先拿走最上面的那只碗,而最后 拿出最下面的那只碗。 举例2:在建筑工地上,使用的砖块从底往上 层一层地码放,在使用时,将从最上面一层 层地拿取

3.1.1 栈的定义 举例1：家里吃饭的碗，通常在洗干净后一个 一个地落在一起存放，在使用时，若一个一个 地拿，一定最先拿走最上面的那只碗，而最后 拿出最下面的那只碗。 举例2：在建筑工地上，使用的砖块从底往上 一层一层地码放，在使用时，将从最上面一层 一层地拿取

3.12栈的基本操作 1初始化栈: INITSTACK(S) 将栈S置为一个空栈(不含任何元素)。 2进栈:PUSH(S,x) 将元素X插入到栈S中,也称为“入栈”、“插入”、“压入” 3出栈:POP(S,x) 删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”。 4取栈顶元素: GETTOP(S,x) 取栈S中栈顶元素。 5判栈空: ISEMPTY(S) 判断栈S是否为空,若为空,返回值为TRUE,否则返回值为 FALSE

3.1.2 栈的基本操作 1.初始化栈：INITSTACK(S) 将栈S置为一个空栈(不含任何元素)。 2.进栈：PUSH( S, x ) 将元素X插入到栈S中，也称为“入栈” 、 “插入” 、 “压入”。 3.出栈： POP(S,x ) 删除栈S中的栈顶元素，也称为”退栈” 、 “删除” 、 “弹出”。 4.取栈顶元素：GETTOP(S,x ) 取栈S中栈顶元素。 5.判栈空：ISEMPTY(S) 判断栈S是否为空，若为空，返回值为TRUE，否则返回值为FALSE

312栈的基本操作 6.清空栈: CLEARSTACK(S) 将栈置为空栈; 7、判栈满: ISFULL(S) X判断栈S是否满,若已满,返回值为TRUE,否则返回 值为 FALSE

3.1.2 栈的基本操作 6. 清空栈：CLEARSTACK(S) 将栈置为空栈； 7、判栈满：ISFULL(S) 判断栈S是否满，若已满，返回值为TRUE，否则返回 值为FALSE

3.1.3顺序栈 定义 是用一组连续的存储单元依次存放栈中的每个 数据元素,并用起始端作为栈底。 由于栈操作的特殊性,附设一个栈顶指针top 来动态地表示栈顶元素在顺序栈中的位置

3.1.3 顺 序 栈 是用一组连续的存储单元依次存放栈中的每个 数据元素，并用起始端作为栈底。 定义 由于栈操作的特殊性，附设一个栈顶指针top 来动态地表示栈顶元素在顺序栈中的位置

31.3顺序栈 类型定义如下所示: #define TrUE #define false o #define MaXsIze 50 typedef struct stack StackElementlype elem MAXSIZEI int top; ∥栈顶指针 iSeqstack;

3.1.3 顺 序 栈 类型定义如下所示： #define TRUE 1 #define FALSE 0 #define MAXSIZE 50 typedef struct stack{ StackElementType elem[MAXSIZE]; int top; //栈顶指针 }SeqStack;