栈
栈概述
栈(stack)可以认为是一种特殊的线性表,因为他仍然满足线性表的特点:
- 存在一个唯一的没有前驱的(头)数据元素.(注意与具体实现中的"头结点"有别)
- 存在一个唯一的没有后继的(尾)数据元素.
- 除此之外,其他每一个数据元素均有一个直接前驱和一个直接后继数据元素.
下面这是2种线性表,即顺序表和链表:
这两种表允许在表中的任何位置操作,栈则不同,栈只允许在表的一端(称为栈顶)操作,而且一般只允许插入和删除这2种操作.
我们可以建立这样的栈的逻辑结构:
顺序栈
所有的插入,删除操作均只能在top一端进行,基于这种操作限制,栈属于FILO原则,即First In Last Out.
我们可以将栈想象一个箱子,我们每次都只能放一个物品进去,并逐渐堆叠,最先放入的物品会被压在最下面,最新放入的物品将会在最上面.(所谓的压箱底)
想要拿出之前放入的物品,则必须先将后放入的所有的物品拿出来.另一方面,最新(即最后)放入的物品在最上面,取出时也是最先拿出;最早放入的物品在最下面,取出时则要最后拿出.
这样的特性则是FILO.
另外有FIFO原则,队列—两头操作.
栈的状态
作为一个栈ADT:
栈有3种状态:栈空,栈非空,栈满.
我们需要使用一些方法来判断当前栈的状态.
假设我们的栈有如下信息:----属性
- top指针: 指示栈顶位置
- bottom指针: 指示栈底
- size值: 栈当前的元素个数
- max_size值: 栈的最大容量—
顺序栈需要—使用数组(realloc),而链栈(一般)则不需要
栈非空
如前所述,栈顶指针top永远指向当前栈中的第一个元素,bottom指示栈底.
我们可以让bottom指针不指向任何有效元素,那么如果栈非空,则top指向某个有效元素,bottom不指向任何元素,例如将其置为NULL(或者0).
那么栈非空,等价于top!=bottom
栈空
与栈非空相反,栈空时,top显然无法指向任何有效元素,当然此时bottom仍然可以让它指向NULL.
容易想到,top等于bottom时,可以认为栈空.
那么栈空,等价于top==bottom//都指向NULL/0
栈满
该状态仅适用于顺序栈,即基于顺序表实现的栈,此时栈一般存储于栈区(与现在讨论的栈不同),它有空间限制,因此需要保证栈当前元素个数不超过最大容量.
那么栈满,等价于size==max_size
栈的操作
压栈-push
就是所谓的向栈中插入元素.
向栈顶插入元素的操作,通常被形象地称为压栈/入栈.因为原来的元素被堆叠(压)在新元素的下面.
在一切操作之前,必须检查当前栈的状态—如果栈满,则不应该执行压栈.
由于栈顶永远指向当前栈顶的有效元素,并且当栈空时top指向NULL.
所以,我们应该先让top指针指向一个有效的内存空间,用于存储新元素,这个操作类似于++top.
然后,就可以把新元素的值赋值进去.
最后,将当前元素个数+1,即++size.
出栈-pop
从栈顶弹出元素的操作,被称作出栈.
在一切操作之前,必须检查当前栈的状态—如果栈空,则不应该执行出栈.
检查无误后,则可以出栈,同样,top指向当前栈顶元素,将该元素从栈中移除,不过一般会将元素值返回,用于处理.
一般,先备份该值,然后将元素空间销毁(用于链栈),例如使用free()进行空间释放.
然后将top指针下移,下一个元素成为新的栈顶,或者弹出最后一个元素后,top指向NULL.
同样,需要--size.
最后,将元素值返回.
销毁栈-destroy/free
很简单,不断地出栈,直到栈空即可.
更新:由于是顺序栈,直接free掉数组即可(当然如果本来就是一次性分配整个结构体,而不是再次分配另一段内存,则这步也不需要).
最后,将栈的实例销毁.
获取状态信息
这些方法都只需要返回对应的状态信息即可,例如栈当前的元素个数get_size(),当前栈顶元素值get_top().
堆栈
计算机的堆栈,就是栈,每一个元素的大小不同,因为每个元素都是一个函数栈帧.
递归—压栈.
计算机的堆区和栈区.
堆区和数据结构的堆 没有任何关系!没有任何鸡毛的关系. heap
wechat
alipay