学习数据结构第6天(栈的基本概念)

栈的定义

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

栈按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。我们称数据进入到栈的动作为压栈(入栈)，数据从栈中出去的动作称为弹栈(出栈)。

栈顶(TOP)：线性表允许进行插入删除的那一端。
栈底(Bottom)：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈的基本操作

InitStack(&S)：初始化一个空栈S。
StackEmpty(&S)：判断一个栈是否为空，若栈S为空则返回True，否则返回False。
Push(&S)：进栈，若栈S未满，则将x加入是之成为新栈顶。
Pop(&S)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(&S)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：销毁栈，并释放S占用的存储空间

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

栈的存储结构

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

• 顺序栈
  采用顺序存储的栈称为顺序栈，使用数组进行实现。

在实现顺序栈之前，我们先来看一看对于顺序栈的操作：

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

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

• 链栈
  采用链式存储的栈称为链栈，使用链表进行相应的实现。

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

指向链表中的第一个结点的指针就是栈顶指针，指向链表最后一个结点的指针就是栈底指针。采用链式存储，便于结点的插入与删除，同链表的操作类似，入栈和出栈都是在表头进行。