栈和队列简介

栈和队列是两种常用的数据结构，它们的数据是按线性结构存储的，因此，栈和队列也属于线性表。

栈和队列的数据可以存储在一个顺序表里，也可以存储在一个链表里，只要满足线性存储结构就行。只对数据的线性结构有要求，对存储数据的具体结构并不做要求。

栈和队列最关键的特征是存取数据有严格的顺序。栈遵循“后进先出”(LIFO, Last In First Out)的原则，队列遵循“先进先出”(FIFO, First In First Out)的原则。

接下来就简单介绍一下栈和队列。

一、栈简介 

栈(stack)，又称为堆栈，是一种数据结构，一种存储数据的容器。

作为一种线性的数据结构，栈的一端是封闭的，称为栈底，另一端是开口的，称为栈顶。

将数据存到栈中，称为入栈(或进栈、压栈)，将数据从栈中取出，称为出栈(或弹栈)。

从栈中存取数据，都只能从开口的一端操作，先入栈的数据会被后入栈的数据“压”住，只有将后入栈的数据取出后，才取得到先入栈的数据，所以，栈的数据是“后进先出”的。

栈的常见应用如：大部分软件都有的“回退”功能Ctrl+Z，浏览器的“后退”功能等。

栈的数据存储结构可以使用顺序表，也可以使用链表。使用顺序表存储数据的栈称为顺序栈，使用链表存储数据的栈称为链栈。

根据顺序表和链表的区别，顺序表物理有序，链表逻辑有序，顺序栈和链栈的区别为，数据在实际物理空间上存放的相对位置不同，顺序栈的数据按物理有序存储，链栈的数据按逻辑有序存储。

二、队列简介

队列(queue)，是另一种有存取顺序要求的数据结构。

队列的两端都是打开的，两端都是“单行”的，一端只进不出，称为队尾，另一端只出不进，称为队头。

将数据从队尾存到队列中，称为入队，将数据从队列中取出，称为出队。

队列的一端只能存入数据，另一端只能取出数据，从队列中取数据时，先入队的数据“挡”住了后入队的数据，只有将先入队的数据取出来，才取得到后入队的数据，所以，队列的数据是“先进先出”的。

队列的常见应用如：春运抢票功能，网购预约功能等。

与栈相同，队列的数据存储结构也可以使用顺序表或者链表。使用顺序表存储数据的队列称为顺序队列，使用链表存储数据的队列称为链队列。

顺序队列和链队列的区别为，数据在实际物理空间上存放的相对位置不同，顺序队列的数据按物理有序存储，链队列的数据按逻辑有序存储。

三、双端队列简介

双端队列(deque，全名double-ended queue)，是一种特殊的线性数据结构。

与队列不同，双端队列的两端都可以入队和出队。也就是说，双端队列没有严格意义上的“队头”和“队尾”，只是为了描述方便，分别称为“前端”和“后端”，两端能进行的操作一样，都可以插入和删除数据。

双端队列同时具有栈和队列的性质。单独从其中一端存取数据时，数据是“后进先出”的，具有栈的性质。从其中一端存数据再从另一端取出，数据是“先进先出”的，具有队列的性质。

双端队列就是一种可以(也只能)从两端插入和删除数据的线性数据结构，使用起来比栈和队列更加灵活。