本章的基本内容是： ⑴栈和队列的定义及操作特性； 第3章 特殊线性表—栈、队列和串 ⑵栈和队列的两种存储方法和基本运算的实现；

Presentation on theme: "本章的基本内容是： ⑴栈和队列的定义及操作特性； 第3章 特殊线性表—栈、队列和串 ⑵栈和队列的两种存储方法和基本运算的实现；"— Presentation transcript:

1 本章的基本内容是： ⑴栈和队列的定义及操作特性； 第3章 特殊线性表—栈、队列和串 ⑵栈和队列的两种存储方法和基本运算的实现；
第3章 特殊线性表—栈、队列和串 本章的基本内容是： ⑴栈和队列的定义及操作特性； 　⑵栈和队列的两种存储方法和基本运算的实现； 　⑶串的基本概念和操作； 　⑷串的常用存储方法； 　⑸串的模式匹配算法。

2 第3章 特殊线性表——栈 3.1.1 栈的逻辑结构 1. 栈的定义 栈是限定仅在表尾进行插入和删除操作的线性表。
第3章 特殊线性表——栈 3.1.1 栈的逻辑结构 1. 栈的定义 栈是限定仅在表尾进行插入和删除操作的线性表。 允许插入和删除的一端称为栈顶，另一端称为栈底； 处于栈顶位置的数据元素称为栈顶元素； 不含任何数据元素的栈称为空栈。

3 a3 a2 a1 第3章 特殊线性表——栈 栈的示意图 栈的特性：后进先出 1.举一些生活中的例子。
第3章 特殊线性表——栈 栈的示意图 1.举一些生活中的例子。 出栈 2.假定有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 入栈 栈顶 a3 注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。 a2 a1 栈底 栈的特性：后进先出

4 第3章 特殊线性表——栈 2. 栈的抽象数据类型定义 栈的基本操作： ⑴ Initial ( S )：构造一个空栈S。
第3章 特殊线性表——栈 2. 栈的抽象数据类型定义 栈的基本操作： ⑴ Initial ( S )：构造一个空栈S。 ⑵ Empty ( S )：判断栈S是否为空栈。 ⑶ Push (S, x)：在栈S的顶部插入一个新元素x。 ⑷ Pop ( S )：将栈S的顶部元素从栈中删除。 ⑸ GetTop ( S )：取出栈顶元素。

5 第3章 特殊线性表——栈 3.1.2 栈的顺序存储结构及实现 a1 a2 top 出栈：top减1 top top 1. 顺序栈
第3章 特殊线性表——栈 3.1.2 栈的顺序存储结构及实现 1. 顺序栈 栈的顺序存储结构称为顺序栈 。 如何改造数组实现栈的顺序存储？ a1 a2 top 出栈：top减1 栈空：top= -1 top top 进栈：top加1 确定是用数组的哪一端表示栈底，同时附设指针top指示栈顶元素在数组中的位置即可。

6 第3章 特殊线性表——栈 2. 顺序栈的实现 顺序栈类的声明 const int MAX_SIZE=100;
第3章 特殊线性表——栈 2. 顺序栈的实现 const int MAX_SIZE=100; template <class T> class seqStack { public: seqStack ( ) ; ~seqStack ( ); void Push ( T x ); T Pop ( ); T GetTop ( ); bool Empty ( ); private: T data[MAX_SIZE]; int top; } 顺序栈类的声明

7 第3章 特殊线性表——栈 顺序栈的基本运算的实现——入栈 template <class T>
第3章 特殊线性表——栈 顺序栈的基本运算的实现——入栈 template <class T> void seqStack::Push ( T x) { if (top==MAX_SIZE-1) throw “溢出”; top++; data[top]=x; } 时间复杂度？

8 第3章 特殊线性表——栈 顺序栈的基本运算的实现——出栈 template <class T>
第3章 特殊线性表——栈 顺序栈的基本运算的实现——出栈 template <class T> T seqStack:: Pop ( ) { if (top==-1) throw “溢出”; x=data[top--]; return x; } 时间复杂度？

9 第3章 特殊线性表——栈 3. 两栈共享空间 提出问题：在一个程序中需要同时使用具有相同数据类型的两个栈。 解决方案①
第3章 特殊线性表——栈 3. 两栈共享空间 提出问题：在一个程序中需要同时使用具有相同数据类型的两个栈。 解决方案① 直接解决：为每个栈开辟一个数组空间。 分析会出现什么问题？如何解决？ 解决方案② 利用顺序栈单向延伸的特性，使用一个数组来存储两个栈。 分析会出现什么问题？如何解决？

10 第3章 特殊线性表——栈 存储空间的浪费。 解决方案二:
第3章 特殊线性表——栈 使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸。 解决方案一:为每个栈开辟一个数组空间。 存储空间的浪费。 解决方案二:

11 第3章 特殊线性表——栈 两栈共享空间示意图 其中：top1和top2分别为栈1和栈2的栈顶指针；
第3章 特殊线性表——栈 两栈共享空间示意图 a1 a2 …… ai bj …… b2 b1 栈1底 top top 栈2底 Stake_Size-1 其中：top1和top2分别为栈1和栈2的栈顶指针； Stack_Size为整个数组空间的大小； 栈1的底固定在下标为0的一端； 栈2的底固定在下标为StackSize-1的一端。

12 第3章 特殊线性表——栈 两栈共享空间类的声明 const int StackSize=100;
第3章 特殊线性表——栈 const int StackSize=100; template <class T> class BothStack { public: BothStack( ) {top1= -1; top2=StackSize;} ~BothStack( ) { } void Push(int i, T x); T Pop(int i); T GetTop(int i); bool Empty(int i); private: T data[StackSize]; int top1, top2; }; 两栈共享空间类的声明

13 第3章 特殊线性表——栈 问题一:什么时候栈1空? 问题二:什么时候栈2空? top1=top2-1 问题三:什么时候栈满?
第3章 特殊线性表——栈 top1=-1 问题一:什么时候栈1空? top2=StackSize 问题二:什么时候栈2空? top1=top2-1 问题三:什么时候栈满? 设i表示整型数值，它只取1和2，当i=1时，表示对栈1操作，当i=2时表示对栈2操作； 当新元素压入栈2时，栈顶指针top2减1；当从栈2删除元素时，top2加1。

14 第3章 特殊线性表——栈 在栈i中插入元素x的算法用伪代码描述为： 1. 如果栈满，则抛出上溢异常； 2. 判断是插在栈1还是栈2；
第3章 特殊线性表——栈 在栈i中插入元素x的算法用伪代码描述为： 1. 如果栈满，则抛出上溢异常； 2. 判断是插在栈1还是栈2； 2.1 若是在栈1插入，则栈顶指针top1加1，在top1处填入x； 2.2 若是在栈2插入，则栈顶指针top2减1，在top2处填入x；

15 第3章 特殊线性表——栈 在栈i中删除栈顶元素的算法用伪代码描述为： 1. 判断是在栈1删除还是在栈2删除。 2. 若是在栈1删除，则
第3章 特殊线性表——栈 在栈i中删除栈顶元素的算法用伪代码描述为： 1. 判断是在栈1删除还是在栈2删除。 2. 若是在栈1删除，则 2.1 若栈1为空栈，抛出下溢异常； 2.2 删除并返回栈1的栈顶元素； 3. 若是在栈2删除，则 3.1 若栈2为空栈，抛出下溢异常； 3.2 删除并返回栈2的栈顶元素；

16 第3章 特殊线性表——栈 3.1.3 栈的链接存储结构及实现 an an-1 a1 ∧ 1.链栈定义 栈的链接存储结构称为链栈 。 栈顶
第3章 特殊线性表——栈 3.1.3 栈的链接存储结构及实现 1.链栈定义 栈的链接存储结构称为链栈 。 an-1 an a ∧ 栈顶 栈底 top 链栈示意图 链栈是否也需要加一个头结点？

17 第3章 特殊线性表——栈 2. 链栈的实现 链栈的类的声明 template <class T> class LinkStack
第3章 特殊线性表——栈 2. 链栈的实现 template <class T> class LinkStack { public: LinkStack( ) {top=NULL;} ~LinkStack( ); void Push(T x); T Pop( ); T GetTop( ) {if (top!=NULL) return top->data;} bool Empty( ) {top==NULL? return 1: return 0;} private: Node<T> *top; } 链栈的类的声明

18 第3章 特殊线性表——栈 链栈的插入操作 链栈插入算法 s x template <class T>
第3章 特殊线性表——栈 链栈的插入操作 template <class T> void LinkStack::Push(T x) { s=new Node<T>; s->data=x; s->next=top; top=s; } 链栈插入算法 ② top x s ① ai a ∧ top

19 第3章 特殊线性表——栈 p top ai top ai-1 a1 ∧ 链栈的删除操作 链栈的删除算法
第3章 特殊线性表——栈 链栈的删除操作 template <class T> T LinkStack::Pop( ) { if (top==NULL) throw "下溢"; x=top->data; p=top; top=top->next; delete p; return x; } 链栈的删除算法 p ai-1 ai a ∧ top top

20 第3章 特殊线性表——栈 3.1.4 顺序栈和链栈的比较 时间性能相同。都是常数时间。
第3章 特殊线性表——栈 顺序栈和链栈的比较 时间性能相同。都是常数时间。 空间性能方面。初始时顺序栈必须确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。所以当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈