栈和队列简介
栈和队列是两种常用的数据结构,它们的数据是按线性结构存储的,因此,栈和队列也属于线性表。
栈和队列的数据可以存储在一个顺序表里,也可以存储在一个链表里,只要满足线性存储结构就行。只对数据的线性结构有要求,对存储数据的具体结构并不做要求。
栈和队列最关键的特征是存取数据有严格的顺序。栈遵循“后进先出”(LIFO, Last In First Out)的原则,队列遵循“先进先出”(FIFO, First In First Out)的原则。
接下来就简单介绍一下栈和队列。
一、栈简介
栈(stack),又称为堆栈,是一种数据结构,一种存储数据的容器。
作为一种线性的数据结构,栈的一端是封闭的,称为栈底,另一端是开口的,称为栈顶。
将数据存到栈中,称为入栈(或进栈、压栈),将数据从栈中取出,称为出栈(或弹栈)。
从栈中存取数据,都只能从开口的一端操作,先入栈的数据会被后入栈的数据“压”住,只有将后入栈的数据取出后,才取得到先入栈的数据,所以,栈的数据是“后进先出”的。
栈的常见应用如:大部分软件都有的“回退”功能Ctrl+Z,浏览器的“后退”功能等。
栈的数据存储结构可以使用顺序表,也可以使用链表。使用顺序表存储数据的栈称为顺序栈,使用链表存储数据的栈称为链栈。
根据顺序表和链表的区别,顺序表物理有序,链表逻辑有序,顺序栈和链栈的区别为,数据在实际物理空间上存放的相对位置不同,顺序栈的数据按物理有序存储,链栈的数据按逻辑有序存储。
二、队列简介
队列(queue),是另一种有存取顺序要求的数据结构。
队列的两端都是打开的,两端都是“单行”的,一端只进不出,称为队尾,另一端只出不进,称为队头。
将数据从队尾存到队列中,称为入队,将数据从队列中取出,称为出队。
队列的一端只能存入数据,另一端只能取出数据,从队列中取数据时,先入队的数据“挡”住了后入队的数据,只有将先入队的数据取出来,才取得到后入队的数据,所以,队列的数据是“先进先出”的。
队列的常见应用如:春运抢票功能,网购预约功能等。
与栈相同,队列的数据存储结构也可以使用顺序表或者链表。使用顺序表存储数据的队列称为顺序队列,使用链表存储数据的队列称为链队列。
顺序队列和链队列的区别为,数据在实际物理空间上存放的相对位置不同,顺序队列的数据按物理有序存储,链队列的数据按逻辑有序存储。
三、双端队列简介
双端队列(deque,全名double-ended queue),是一种特殊的线性数据结构。
与队列不同,双端队列的两端都可以入队和出队。也就是说,双端队列没有严格意义上的“队头”和“队尾”,只是为了描述方便,分别称为“前端”和“后端”,两端能进行的操作一样,都可以插入和删除数据。
双端队列同时具有栈和队列的性质。单独从其中一端存取数据时,数据是“后进先出”的,具有栈的性质。从其中一端存数据再从另一端取出,数据是“先进先出”的,具有队列的性质。
双端队列就是一种可以(也只能)从两端插入和删除数据的线性数据结构,使用起来比栈和队列更加灵活。