同济大学：《数据结构》课程PPT教学课件（C++描述）第3章 栈和队列

第3章栈和队列 数据结构(C++描述

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

目录 3。1栈 队列 退出

3。1 栈 3。2 队列 退出 目录

31栈 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栈的运算 初始化栈: INISTACK(&S) 将栈S置为一个空栈(不含任何元素) 2进栈:PUSH(&S,X) 将元素Ⅹ插入到栈S中,也称为“入栈”、“插入”、“压 入 出栈:POP(&S) 删除栈S中的栈顶元素,也称为”退栈”、“删除” 出 4取栈顶元素: GETTOP(S) 栈S中栈顶元素 判栈空: 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

过31.3栈的抽象数据类型描述 4 ADt Stack is Data 含有n个元素a1a2a2…an,按LFO规则存放,每个元素的 类型都为 teletype Operation Void inistack(&s)/将栈S置为一个空栈(不含任何元素) 入 Void pushe&sx)/将元素x插入到栈S中,也称为“入 栈”、“插入”、“压入” Void Pop(&s)/删除栈S中的栈顶元素,也称为”退 栈”、“删除”、“弹出” Elemtype gettop(s)/取栈S中栈顶元素 Int empty(s)∥判断栈S是否为空,若为空,返回值为1, 否则返回值为0 End stack

3.1.3栈的抽象数据类型描述 ADT Stack is 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 End stack

3.1.4顺序栈 1顺序栈的数据类型 CONST int maxsize= maxlen;∥定义栈的最大容量为 maxlen Struct segstack elemtype stack[ maxsize];∥.栈中元素定义 为 elemtype类型 Int top ∥:指向栈顶位置的指针

3.1.4顺序栈 1.顺序栈的数据类型 CONST int maxsize=maxlen; //定义栈的最大容量为 maxlen Struct seqstack { elemtype stack[maxsize]; //将栈中元素定义 为elemtype类型 int top; //:指向栈顶位置的指针 }

2.栈的五种运算 y(1)初始化栈 void inistack (seqstack &s s top=0

2．栈的五种运算 （1）初始化栈 void inistack(seqstack &s) { s.top=0; }

(2)进栈 void push(seqstack &s, elemtype x) if (s top=-maxsize-1) cout<<overflow else S top++ Sstack[s topI=X

（２） 进栈 void push(seqstack &s, elemtype x) { if (s.top==maxsize-1} cout<<”overflow”; else { s.top++; s.stack[s.top]=x; } }

(3)退栈 void pop(segstack &s) if (S top==0) cout<<underflow else S.top--

（３） 退栈 void pop(seqstack &s) { if (s.top= =0) cout<<”underflow”; else s.top--; }

(4)取栈顶元素 elemtype gettop(seqstack if (s top==0)(cout<<underflow?; return 0 else return s stack[s top

（４） 取栈顶元素 elemtype gettop(seqstack s) { if (s.top= =0) {cout<<”underflow”;return 0;} else return s.stack[s.top]; }