栈和队列

栈和队列

队列都是操作受限线性表:前者先进先出,后者先进后出。

栈是什么

LIFO(后进先出) 数据结构中,将首先处理添加到队列中的最新元素。

栈是一个 LIFO(后进先出) 数据结构栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。通常,插入操作在栈中被称作入栈 push 。与队列类似,总是在堆栈的末尾添加一个新元素。但是,删除操作,退栈 pop ,将始终删除队列中相对于它的最后一个元素。

img

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构

从栈的定义可以看出,栈只支持两个基本操作:入栈 push()出栈 pop() ,也就是在栈顶插入一个数据和从栈顶删除一个数据。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)

栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈

为什么需要栈

相比数组和链表,栈只是对操作进行了限制,似乎并没有任何优势。为什么不直接使用数组或者链表?为什么还要用这个“操作受限”的“栈”呢?

特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

栈的应用场景

(1)函数调用栈

img

(2)表达式求值

img

(3)表达式匹配

可以借助栈来检查表达式中的括号是否匹配

队列

在 FIFO 数据结构中,将首先处理添加到队列中的第一个元素。

队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在队列的末尾。 删除(delete)操作也被称为出队(dequeue)。 你只能移除第一个元素。

什么是队列

队列:先进先出的线性表

队列是一种“操作受限”的线性表,只允许在一端插入数据,在另一端删除数据。

队列的最基本操作:**入队 enqueue(),放一个数据到队列尾部;出队 dequeue()**,从队列头部取一个元素。

img

队列可以用数组来实现,也可以用链表来实现。用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列

队满的判断条件是 tail == n,队空的判断条件是 head == tail

循环队列

循环队列是一种较为特殊的队列。

循环队列的要点是确定好 队空和队满的判定条件

在用数组实现的非循环队列中,队满的判断条件是 (tail+1) % n == head,队空的判断条件是 head == tail

img

为什么需要队列

为什么需要队列和为什么需要栈,是同样的道理,参考 为什么需要栈

队列的应用场景

(1)阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是:

  • 在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;
  • 如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

img

img

(2)并发队列

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。实际上,基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

参考资料