数据结构-栈和队列

张俊红
张俊红
张俊红
39
文章
0
评论
2020-04-1809:05:00 评论 92 1817字
摘要

前言本章节开始数据结构第二篇,栈和队列——栈:栈的存储结构、栈的基本操作队列:队列的存储结构、队列的基本操作

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈,栈又称后进后出的线性表,简称LIFO结构。

栈首先是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系,只不过它是一种特殊的线性表而已。

栈的特殊之处在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。

栈的插入操作,叫做进栈;栈的删除操作叫做出栈。

1.栈的存储结构

用来存放栈的数据元素对应的数据存储结构称为栈的存储结构。

1.1栈的顺序存储结构

栈是线性表的特例,所以栈的顺序存储结构其实就是线性表顺序存储结构的简称,我们简称为顺序栈。线性表是用数组来实现的,对于栈这种只能一头插入删除的线性表来说,用数组下标为0(栈底不变,只需要跟踪栈顶的变化即可)的一端作为栈底比较合适。

数据结构-栈和队列

顺序栈定义如下:

数据结构-栈和队列

1.2栈的链式存储结构

把栈顶放在单链表的头部,用链表来存储栈的的数据结构称为链栈。

数据结构-栈和队列

链栈结点定义如下:

数据结构-栈和队列

2.栈的操作

2.1顺序栈的操作

对于顺序栈,一共有4个要素,包括两个特殊状态和两个操作。

特殊状态: 1)栈空状态:st.top == -1,也有的用st.top = 0表示栈空,这个时候栈顶位置为0。 2)栈满状态:st.top == maxsize-1表示栈满。maxsize为栈中最大元素个数,maxsize-1为栈满时栈顶元素在数组中的位置,因数组位置是从0开始的。

操作: 顺序栈的进栈和出栈操作都是在栈顶进行的,所以只需要更改栈顶位置即可达到进栈和出栈的目的。

数据结构-栈和队列

1)初始化栈:

数据结构-栈和队列

2)进栈操作:

数据结构-栈和队列

3)出栈操作: 出栈与进栈是相对应的操作

数据结构-栈和队列

4)简化版的操作:

数据结构-栈和队列

2.2链栈的操作

与顺序栈对应,链栈也有4个元素,包括两个状态和两个操作。

状态: 1)栈空:lst -> next == NULL,即栈没有后继结点时,栈为空。 2)栈满:如果存储空间无限大的话,不会存在栈满的情况。

操作: 链栈的进栈就是头插法建立链表的插入操作;出栈就是单链表的删除操作。

数据结构-栈和队列

1)链栈初始化:

数据结构-栈和队列

2)进栈:

数据结构-栈和队列

3)出栈:

数据结构-栈和队列

4)简化版操作:

数据结构-栈和队列

队列:

队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表,队列是一种先进先出的线性表,简称FIFO,允许插入的一端称为队尾(Rear),允许删除的一端称为队头(Front)。向队中插入元素称为进队,新元素进队后成为新的队尾元素;向队中删除元素称为出队,元素出队后,其后继元素就成为新的队头元素。

1.队列的存储结构

用来存储队列数据元素的数据结构。

1.1队列的顺序存储结构:

使用顺序表存储队列时,队列元素的出队是在队头,即下标为0的地方,当有元素出队时,出队元素后面的所有元素都需要向前移动,保证队列的队头始终处在下标为0的位置,此时会大大增加时间复杂度。

数据结构-栈和队列

用顺序表来存储队列元素的数据结构称为队列的顺序存储结构,定义如下:

数据结构-栈和队列

1.2队列的链式存储结构:

用链表来存储队列元素的数据结构称为队列的链式存储结构,定义如下:

数据结构-栈和队列

队列结点类型定义:

数据结构-栈和队列

链队类型定义:

数据结构-栈和队列

2.队列操作

2.1循环队列

因为顺序队列出队时时间复杂度较高,有问题总是要解决的,为什么一定要让队头出现在下标为0的位置呢?所以有人提出了不去限制队列元素必须存储在数组的前n个单元这一条件,这样队头元素就不需要一定在下标为0的位置。但是随着队列元素的出队,队头指针在向后移动,假设队尾指针已经在maxsize-1的位置,这个时候虽然队列还有存储空间,但是队尾已经无法进队了,比如下图这样:

数据结构-栈和队列

虽然下标为0和1的位置处还有空间,但是队尾已经无法再有新元素进队,我们把这种情况称为"假溢出",为了解决这种假溢出的问题,就提出了循环队列的概念,让队列的头尾进行相连,这种头尾相连的顺序存储结构称为循环队列。

数据结构-栈和队列

循环队列需要损失一定的空白,这样只有在队空的时候才会出现front=rear。

循环队列的要素:

两个状态: 队空状态:

数据结构-栈和队列

数据结构-栈和队列

队满状态:

数据结构-栈和队列

数据结构-栈和队列

两个操作: 元素x进队操作(移动队尾指针)

数据结构-栈和队列

元素x出队操作(移动队头指针)

数据结构-栈和队列

初始化队列算法:

数据结构-栈和队列

进队算法:

数据结构-栈和队列

出队算法:

数据结构-栈和队列

2.2链队:

链队就是采用链式存储结构存储队列。链队的四个要素:队空和队满,元素进队和出队操作。

数据结构-栈和队列

队空状态:

数据结构-栈和队列

队满状态: 一般来说不存在队满的情况,只要内存足够大。

元素进队操作(指针p指向进队元素)

数据结构-栈和队列

元素出队操作(x存储出队元素)

数据结构-栈和队列

初始化链队算法

数据结构-栈和队列

判断队空算法

数据结构-栈和队列

入队算法

数据结构-栈和队列

出队算法

数据结构-栈和队列

End.

作者:张俊红

  • 我的微信公众号
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: