什么是栈

洗碗时，将洗好的碗一个叠一个地摆放在橱柜中；用碗时，再将碗逐个取下。通常来讲，摆放碗时是由下而上依次放置，而取碗时是自顶向下逐个选取。图1是一摞摆放好的碗。

图1 一摞碗

如上述这种现象，也就是先放入的东西后被取到，后放入的东西优先被取到，我们认为其遵循“后进先出”原则，在数据结构中也有一种数据结构遵循这个规则，它就是栈（stack）。

栈也是一种线性表，但它是受到限制的线性表。第2章学习的顺序表、链表，可以在两端进行插入、删除操作，而栈，类似于盛放碗的碗橱，仅允许在一端进行这些操作，其结构示意图如图2所示。

图2 栈的结构图

栈中允许执行插入和删除操作的一端称为栈顶，不允许执行插入和删除操作的一端称为栈底。向一个栈中插入新元素又称为入栈、压栈。入栈之后该元素被放在栈顶元素的上面，成为新的

栈顶元素。

从一个栈中删除元素又称为出栈、弹栈，是把栈顶元素删除，使其相邻元素成为新的栈顶元素。

执行入栈操作时，会先将元素插入到栈中，然后按照数据入栈的先后顺序，从下往上依次排列。每当插入新的元素时，栈顶指针就会向上移动，指向新插入的元素。

执行出栈操作时，栈顶的元素会被先弹出，接着按照后进先出的原则将栈中的元素弹出。弹出栈顶元素后，栈顶指针就向下移动，指向原栈顶下面的一个元素，这个元素就成为了新的栈顶元素。

当栈已满时，不能继续执行入栈操作。同理，栈为空时，也不能继续执行出栈操作。

需要注意的是，若要从栈中获取元素，只能通过栈顶指针取到栈顶元素，无法取得其它元素。例如在图3-2中，当an没有被弹出时，无法读取到下面的元素。

由于栈遵循后进先出(Last In First Out，简称LIFO)原则，因此又把栈称为后进先出表。

栈的常用操作如下：

● Create()（Init()）：创建栈（初始化栈）。

● IsEmpty()：判断栈是否为空。

● Push()：进栈。

● Pop()：出栈。

● getTop()：获取栈顶元素。只是读取栈顶元素，并不将元素弹出栈。

● getSize()：获取栈的长度。

● Destory()：销毁栈。

进栈出栈相当于上一章学习的线性表中的插入删除操作，两者不同的是：栈顶是栈读取数据的唯一入口。