队列

作者: Sun东辉 | 来源:发表于2022-07-04 10:56 被阅读0次

队列,又称为伫列(queue),计算机科学中的一种抽象资料类型,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。 队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

特点

  1. 先进先出(FIFO, First-In-First-Out);
  2. 除头尾节点之外,每个元素有一个前驱,一个后继。

存储结构

  1. 数组队列:利用一组地址连续的存储单元依次存放从队列头到队列尾的元素,同时附设两个整型变量 front 和 rear 分别指示队列头元素及队列尾元素的位置。
  1. 单链队列:使用链表作为基本数据结构,所以不存在伪溢出的问题,队列长度也没有限制,但插入和读取的时间代价较高。
  1. 循环队列:可以更简单防止伪溢出的发生,但队列大小是固定的。

操作

我们以数组队列为例,在下面的入队和出队程序中,省略了对上溢和下溢的检查。

入队(ENQUEUE)

ENQUEUE(Q,x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else Q.tail = Q.tail + 1

出队(DEQUEUE)

DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head = Q.length
        Q.head = 1
    else Q.head = Q.head + 1
    return x

可以看出,ENQUEUE 和 DEQUEUE 操作的时间复杂度都为 O(1)。

参考资料

  • 《算法导论》第三版 殷建平 等译
  • 《数据结构》(C 语言第二版)严蔚敏 等编著
  • 维基百科

相关文章

  • 队列

    队列特性 对比队列和栈 基于数组的队列 对比队列学习循环队列 循环队列难点 阻塞队列 并发队列 应用:线程池中拒绝...

  • 队列

    文章结构 什么是队列 实现队列顺序队列链式队列循环队列 Java中的队列 1. 什么是队列 队列也是一种操作受限的...

  • iOS底层-- GCD源码分析(1)-- dispatch_qu

    手动目录认识队列队列的结构队列的产生主队列全局队列创建的队列管理队列 代码版本dispatch version :...

  • 队列,异步,同步,线程通俗理解

    一、队列 串行队列 并行队列 主队列(只在主线程执行的串行队列) 全局队列(系统的并行队列) 二、 任务(是否具有...

  • GCD基础总结一

    上代码~ 同步串行队列 同步并行队列 异步串行队列 异步并行队列 主队列同步 会卡住 主队列异步

  • OC多线程

    队列创建 线程与队列 队列线程间通信 队列组

  • GCD

    获得主队列 获得全局队列 串行队列 异步队列 同步队列 阻隔队列 (像栅栏一样 ) 例如 A -->栅栏 --...

  • 数据结构第三篇 队列

    队列的特性 前进先出。 我们来大致描述下进出队列的情况。 进队列 1 进队列现在队列是 12 进队列现在队列是 1...

  • 利用链表实现队列

    队列成员变量: 队列长度 队列头节点 队列尾节点队列方法: 队列包含元素个数 队列是否为空 进队操作 出队操作 d...

  • Git 常用操作命令(持续更新)

    当前更新到stash队列 查看stash队列 清空队列 删除某个队列

网友评论

      本文标题:队列

      本文链接:https://www.haomeiwen.com/subject/ofddbrtx.html