【免费】第3章栈和队列1资源-CSDN文库

需积分: 0 195 浏览量 2022-08-04 14:30:48 上传评论收藏 191KB PDF 举报

资源详情

资源评论

资源推荐

1

第3章栈和队列

 主要内容：

 栈

 栈的基本定义

 栈的顺序存储和链式存储

 栈的应用

 栈与递归实现

 队列

 队列的基本定义

 队列的链式存储

 循环队列－队列的顺序存储

2

栈和队列概述

 栈(stack)和队列(queue)是两种重要的线

性结构

 从数据结构角度看，栈和队列也是线性表，其特

殊性在于它们的基本操作是线性表的子集，是操

作受限的线性表，可称为限定性的数据结构

 从数据类型角度看，其操作规则与线性表大不相

同，是完全不同于线性表的抽象数据类型。

 栈按“后进先出”的规则进行操作

 队列按“先进先出”的规则进行操作

栈和队列是操作受限的特殊线性表

3

§3.1 栈

 1. 栈的基本定义

 栈：限定在表尾进行插入和删除操作的线性表

 栈顶(表尾)：栈中允许插入、删除的一端

 栈底(表头)：栈中不允许插入、删除的一端

 插入也称为进栈(压栈)；删除也称为出栈(退栈)

 不含元素的空表称空栈。

( a

1

，

a

2

，

a

3

，

……

，

a

n

)

栈底栈顶

栈底

栈顶

a

1

a

2

a

3

…

a

n

注意：一般令栈顶指针指向栈

顶元素的下一位置

4

栈的操作特性

 特点：先进后出(FILO)或后进先出(LIFO)

栈底

栈顶

栈底

栈顶

入栈

a

1

栈底

栈顶

入栈

a

1

a

2

a

3

…

a

n

a

1

出栈

栈底

栈顶

三个元素按a、b、c的次序依次进栈，且每个元素

只允许进栈一次，则可能的出栈序列有多少种？

5

抽象数据类型定义

ADT Stack{

数据对象：D

数据关系：R

基本操作：Initstack(&s); Destroystack(&s);

Clearstack(&s); Stackempty(s);

Stacklength(S); Gettop(S,&e);

Push(&S,e); Pop(&S,&e);

Stacktraverse(S);

} ADT Stack

6

2. 栈的顺序存储

 顺序栈：栈的顺序存储结构简称为顺序栈，即利

用一组地址连续的存储单元依次存放从栈底到栈

顶的数据元素。

如何改造数组实现栈的顺序存储？

栈不存在如何表示？

 若base＝NULL，表示栈结构不存在。

 确定用数组的低端表示栈底，并

利用空间分配时的初始指针base

来指示栈底位置

base

top

a

1

a

2

a

3

…

a

n

 附设指针top指示栈顶元素在数组

中的位置

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

评论0

内容反馈

文润观书

粉丝: 22
资源: 318

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip