2.1 栈和队列的基本概念

　　本质上是一种线性表，是只能在表的一端进行插入和删除操作的线性表。称表中允许插入和删除的一端为栈顶（top），不允许插入和删除的一端称为栈底（bottom）。如图2-1所示为一个顺序栈的示意图，其中栈底一直不变，而栈顶随着栈内元素的变化而变化，在顺序栈中永远指向下一个要写入的结点。
　　入栈操作是指在栈顶插入元素的操作，出栈操作是指在栈顶删除元素的操作。栈是一种后进先出（LIFO）的数据结构，即后入栈的元素要比先入栈的元素先出栈。一串数据依次进入栈后，再依次出栈，那么出栈数据的次序将倒置。例如，线性表（2008，2009，2010，2011）中的元素依次全部入栈后，再全部出栈，那么出栈的次序为（2011，2010，2009，2008），如图2-2所示。
　　队列本质上也是一种线性表，标准队列只能在一端插入数据元素，在另一端删除数据元素，只能删除元素的一端称为队列头或队头（front），只能插入元素的一端称为队列尾或队尾（rear）。向队列尾插入元素的操作称为入队列，从队列头删除元素的操作称为出队列。先入队列的数据也要先出队列，即队列是一种先进先出（FIFO）的数据结构，因此，队列并不能更改数据串的次序。如图2-3所示，数据串（1，2，3，…，n）依次进入一个队列，最后以相同的次序离开队列。