《数据结构》课程教学课件（讲稿，C语言描述）第3章 栈和队列

第3章栈和队列数据结构（C描述)

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

目录3.1栈队列3.2退出

3.1 栈 3.2 队列 退出 目录

3.1栈3.1.1栈的定义栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后册删除。也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为 LIFO 表

3.1 栈 3.1.1 栈的定义 栈(stack)是限制线性表中元素的插入和删除只能 在线性表的同一端进行的一种特殊线性表。允 许插入和删除的一端，为变化的一端，称为栈 顶 (Top) ，另 一 端为固 定 的一端 ， 称为栈 底 (Bottom)。 根据栈的定义可知，最先放入栈中元素在栈底，最 后放入的元素在栈顶，而删除元素刚好相反，最后 放入的元素最先删除，最先放入的元素最后删除。 也就是说，栈是一种后进先出(Last In First Out)的 线性表，简称为 LIFO 表

3.1.2栈的运算1.初始化栈：INISTACK(&S)将栈S置为一个空栈（不含任何元素）。2.进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3.出栈：POP(&S)删除栈S中的栈顶元素，也称为”退栈”、“删除”“猫山”4.取栈顶元素：GETTOPS)取山楼顶元麦5.判栈空：EMPTY(S)共平六同向适平1不返同估平新日不平穴

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

3.1.3#栈的抽象数据类型描述ADT Stack Data：含有n个元素a,a2,a3..,an,按LIFO规则存放，每个元素的类型都为elemtype。Operation:Void inistack(&s）//将栈S置为一个空栈(不含任何元素）Void Push(&s,x）//将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”Void Pop(&s）//删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”Elemtypegettop(s）//取栈S中栈顶元素，/判断栈S是否为空，若为空，返回值为1Int empty(s)否则返回值为0ADT Stack

3.1.3 栈的抽象数据类型描述 ADT Stack { Data： 含有n个元素a1 ,a2 ,a3 ,.,an ,按LIFO规则存放，每个 元素的类型都为elemtype。 Operation： Void inistack(&s) //将栈S置为一个空栈(不含任何元素) Void Push(&s,x) //将元素X插入到栈S中，也称为 “入 栈” 、 “插入” 、 “压入” Void Pop(&s) //删除栈S中的栈顶元素，也称为”退 栈” 、 “删除” 、 “弹出” Elemtype gettop(s) //取栈S中栈顶元素 Int empty(s) //判断栈S是否为空，若为空，返回值为1， 否则返回值为0 }ADT Stack

3.1.4顺序栈1.顺序栈的数据类型#define STACKINITSIZE1OO：//存储空间初始分配量#defineSTACKINCREMENT1O：/存储空间分配增量typedef struct seqstack(elemtype*base；//构造之前和销毁之后，base的值为NULLelemtype*top；//指向栈顶位置的指针int stacksize://当前已分配的存储空间，以元素为单位fseqstack;

3.1.4 顺序栈 1.顺序栈的数据类型 #define STACK_INIT_SIZE 100; //存储空间初始分配量 #define STACKINCREMENT 10; //存储空间分配增量 typedef struct seqstack {elemtype *base; //构造之前和销毁之后，base的值为NULL elemtype *top; //指向栈顶位置的指针 int stacksize;//当前已分配的存储空间，以元素为单位 }seqstack;

2．栈的五种运算（1）初始化栈void inistack(seqstack &s)( s.base=(elemtype *)malloc(maxsize*sizeof(elemtype))if (!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK INIT SIZEreturn OK;

2．栈的五种运算 （1）初始化栈 void inistack(seqstack &s) { s.base=(elemtype *)malloc(maxsize*sizeof(elemtype)); if (!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return OK; }

进栈(2））void push(seqstack &s, elemtype x)if (s.top-s.base>=s.stacksize)(s.base-(elemtype*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(elemtype)if (ls.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top++=e,return OK,7

（２） 进栈 void push(seqstack &s, elemtype x) { if (s.top-s.base>=s.stacksize) {s.base=(elemtype*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(elemtype)); if (!s.base) exit(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; } *s.top++=e; return OK; }

（3）退栈void pop(seqstack &s, elemtype &e)if (s.top= =s.base) return ERROR;e=*--s.top,return OK;

（３） 退栈 void pop(seqstack &s, elemtype &e) { if (s.top= =s.base) return ERROR; e=*-s.top; return OK; }

(4）取栈顶元素elemtype gettop(seqstack s, elemtype &e)1if (s.top= =s.base) return ERROR;e=*(s.top-1);return OK;

（４） 取栈顶元素 elemtype gettop(seqstack s, elemtype &e) { if (s.top= =s.base) return ERROR; e=*(s.top-1); return OK; }