信息学奥赛知识点(十三)栈和队列

一、栈

栈是只能在某一端插入和删除的特殊线性表。

用桶堆积物品，先堆进行的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行。底部一般是不动的。

栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入操作一般称为PUSH。删除一般称为POP。栈也称先进后出表或后进先出表。

例如：

1.假如有以下数据依次进栈，1， 6， 8，9 。那么出栈顺序是 9，8 ，6 ，1

2.假如有以下数据 进栈顺序是 1 ，6 ，8 ， 9 。那么可能的出栈顺序有？

这个只告诉了进栈顺序，没有表明 是不是依次进栈，也就是有可能在某个数字没有进栈之前，有的数字已经出栈了，所以其中一种可能的出栈顺序分析如下：

1进栈，6进栈，6出栈，8进栈，9进栈，9出栈，8出栈，1出栈。
出栈顺序为 6 9 8 1 。

二、队列

队列是限定在一端进行插入，另一端进行删除的特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人 总是排在队伍末尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队，这种表也称为先进先出表。