队列

一，定义

队列是一种特殊的线性表，只能在头尾两端进行操作

  • 队尾(rear) : 只能从队尾添加元素，一般叫做enQueue,入队

  • 对头(front) : 只能从对头移除元素，一般叫做deQueue,出队

  • 先进先出的原则，First In First Out，FIFO

二，内部实现

队列的内部实现是否可以直接利用以前用过的数据结构？

  • 动态数组，链表
  • 优先使用双向链表，因为队列主要网头尾操作元素

三，几种特殊队列

双端队列

双端队列是能在头尾两端添加，删除的队列

英文名Deque, 是double ended queue的简称

循环队列

其实队列底层也可以用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度

这个用数组实现并且优化之后的队列也叫做，循环队列

循环双端队列：可以进行两端添加，删除操作的循环队列。