栈按照先进后出的原则存储数据#xff0c;先进入的数据被压入栈底#xff0c;最…

栈(Stack)是一种基于先进后出(FILO)或者后进先出(LIFO)的数据结构是一种只允许在一端进行插入和删除操作的特殊线性表。

栈按照先进后出的原则存储数据先进入的数据被压入栈底最后的数据在栈顶需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

我们称数据进入到栈的动作为压栈(入栈)数据从栈中出去的动作称为弹栈(出栈)。

StackEmpty(S)判断一个栈是否为空若栈S为空则返回True否则返回False。

以上可以看成是一个栈的框架上面的函数也可以直接进行相应的使用。

栈是一种操作受限的线性表类似于线性表它也有对应的两种存储方式顺序存储、链式存储。

顺序栈

顺序栈可以使用一维数组实现base指针指向栈底数组的第0个元素top指针是动态的每次都指向栈顶元素最后一个放入栈中的元素因此我们将base指针称之为栈底指针将top指针称之为栈顶指针。

在实现进栈操作的时候栈不满时栈顶指针先加1再送值到栈顶元素实现出栈操作的时候栈非空则先取栈顶元素值再将栈顶指针减1。

链栈中通常采用单链表实现并规定所有的操作都在单链表的表头进行的但是与之前所学的链表不同的是链式栈中不需要头结点数据域为空的结点。

指向链表中的第一个结点的指针就是栈顶指针指向链表最后一个结点的指针就是栈底指针。

采用链式存储便于结点的插入与删除同链表的操作类似入栈和出栈都是在表头进行。