数据结构与算法基础三:栈与队列
一:栈
栈就是限定在尾部进行插入和删除的线性表.
这种后入先出的结构叫做Last in first out,LIFO结构;
线性表的特性栈基本都有,不过插入和删除需要特殊处理,入栈叫做push,出栈叫做pop.栈的应用极其广泛,凡是能够回退的场景,都可以用栈实现,比如网页.
栈的基本操作
1.顺序结构
顺序存储的栈,叫做顺序栈.
定义一个栈
入栈
出栈
显然入栈和出栈都是O(1)的.
顺序栈,有一种独特的使用方法,共用数组空间;
顺序存储的线性表需要一个数组来存储,数组的长度需要事先申请,这些空间是可以利用起来的;
有这样一种常见,当A占用空间增加时,B一定会减少,这种此涨彼伏的场景可以用两个栈共用数组来实现.
将栈A的栈底设置在数组的第一个元素,将栈B的栈底设置在数组的最后一个元素.入栈时,两边向中间靠拢.
image.png
2.链式存储
链式存储叫做链栈,这种结构就很舒服了,既然栈是后进先出,那么直接把头指针放在栈顶就ok了.
链栈和链表一样,只是插入和删除需要特殊操作.
上面是节点,下面是栈
插入,也就是入栈,把新节点的next指向top,再移动top即可.
插入
删除,就是出栈,把top往下移动一位,然后讲栈顶节点释放.
image.png
递归调用函数是一种典型的栈结构:
当调用嵌套调用函数式,函数体和参数就会入栈,当达到设置的条件时,就开始出栈
斐波那契数列是后两项等于前两项之和,1,1,2,3,5,8...
二:队列
对比栈,队列就是只准在一端插入,在另一端删除的线性表
队列是先进先出的,first in first out,简称FIFO.
只许进的(插入)叫队尾,只许出的(删除)叫队头;
1.顺序存储
顺序结构的线性表存在一个数组里.叫做顺序队列.
当删除队头元素时,后面的元素需要向前移动一位,以保证元素一直存储在数组前n个;
当然也可以不移动,这样的话就相当于队头移动了;
定义一个front指针指向队头,定义一个rear指向队尾后后面一个下标的位置;当front = rear时,这就是个空队列.
队列
但是前面会空出来,当队尾到达数组最大时,叫做假溢出.
假溢出
如果到达队尾时再从头开始,就可以解决假溢出,叫做循环队列,注意它是顺序结构的,不是链式.
如此,当数组最后一位被使用的时候,rear移动到了数组第0的位置,但是这样一来,就没法判断队列是空还是满了
rear=front
解决办法是空出一个,然后根据一定的关系来判断,就是(rear+1) % queueSize = front;当满足这个条件时,数组已满.
2.链式存储
链式存储的队列,叫做链队列,本质是个单向链表,多了一个rear指针,只能队头删除,队尾插入
链队列
空的链队列
-
入队操作
就是在队尾插入节点,然后修改rear指针
入队
-
出队操作
出队就是删除第一个节点,然后修改front指针
出栈
