线性数据结构之队列(Queue)_dequeue的平均时间复杂度为o(1)

感兴趣的话大家可以关注一下公众号 : 猿人刘先生 , 欢迎大家一起学习 , 一起进步 , 一起来交流吧!

一.队列(Queue)

队列是一种用来存储数据的数据结构 , 与链表和栈类似 , 数据到达的次序是队列的关键 , 类似于生活中我们在排队购买东西时 , 第一个人是队首 , 最后一个人是队尾 , 第一个人先买到东西后离开 , 这个时候第二个人便成了队首 , 以此类推…

队列中第一个插入的元素也是第一个被删除的元素 , 所以队列是一种先进先出(First In First Out 简称 FIFO)或者后进后出(Last In Last Out 简称 LILO)的线性表

队列是一种只能在一端(队尾)插入 , 另一端(队首)删除的有序线性表 , 在队列中插入一个元素被称为入队(EnQueqe) , 在队列删除一个元素被称为出队(DeQueuq) , 试图对一个空队列执行出栈操作 , 被称为下溢(underflow) , 试图对一个满队列执行入队操作 , 被称为溢出(overflow)

1.队列的实现方式

• 基于简单循环数组实现

• 基于动态循环数组实现

• 基于链表的方式实现

1.1 基于简单循环数组实现

通常将尾指针rear指向当前队尾元素的真正位置 , 而头指针front指向当前队头元素的前一个位置(不让队头指针 , 队尾指针指向真正的元素是为了运算的时候方便 , 并不是唯一的方法) , 刚开始时 , 队列的头 , 尾指针都为-1 , 后面在出队或者入队时 , 头指针和尾指针值递增变化 , 如上图所示

如果队列为空的时候进行出队操作 , 那么此时将产生下溢现象 , 相反 , 如果队列满时做入队操作将会出现上溢现象

出栈和出队并不是真正的删除元素 , 只是不起作用

时间复杂度

• 入栈操作EnQueue时间复杂度为O(1)

• 出栈操作DeQueue时间复杂度为O(1)

局限性

用于实现队列的数组的最大空间必须预先声明且不能改变。试图对一个满队列执行入队操作会产生一个针对简单数组这种特定实现队列方式的异常。

1.2 基于动态循环数组实现

基于动态循环数组实现就是在每次队满的时候进行动态的扩容即可 , 原理同栈一样

栈数据结构飞机票 : 线性数据结构之栈(Stack)

时间复杂度

• 入队操作EnQueue时间复杂度考虑扩容的情况下为O(N) , 否则为O(1)

• 出队操作DeQueue时间复杂度为O(1)

1.3 基于链表的实现方式

实现队列的另一种方法是使用链表。通过在链表末端插入元素的方法实现入队(EnQueue)操作。通过删除链表表头元素的方法实现出队操作(DeQueue)。

时间复杂度

• 入队操作EnQueue时间复杂度平均为O(1)

• 出队操作DeQueue时间复杂度为O(1)