数据结构-队列

1.容器
容器用于容纳元素集合,并对元素集合进行管理和维护.
传统意义上的管理和维护就是:增,删,改,查.
我们分析每种类型容器时,主要分析其增,删,改,查动作实现,及复杂度.

2.队列
2.1.结构
2.1.1.图解
队列是容器类型.
但队列不同于数组,链表这一类的容器.数组和链表这类容器规定了对容器内元素的组织方式,但队列这类容器并不限定容器内元素的组织方式.它只是限制了容器增加元素,删除元素的行为.

由于队列对容器内元素组织方式无要求,所以,结构方面依赖实现队列的底层容器.采用数组来实现的队列,结构就是数组.采用链表来实现的队列,结构就是链表.采用其他容器来实现的栈,结构为对应容器的结构.

2.2.动作
2.2.1.增
队列中插入新元素.
原则上新元素只能插入到容器最后元素之后.
新增过程可参考实现队列的容器中尾部新增新元素的情况.
2.2.2.删
队列中删除元素.
原则上只能删除首元素.
删除过程可参考实现队列的容器中移除首元素的情况.
2.2.3.查
队列一般不用支持查找,只要提供访问首元素,尾元素的方法就行了.
2.2.4.改
队列中修改元素,只能修改首元素或尾元素.
修改过程可参考实现队列的容器中修改首元素,尾元素的情况.

2.3.时间复杂度
评价容器的依据一个是其占据的线性空间,一个是操作执行的时间复杂度.
对基于数组或链表实现的队列其各个操作时间复杂度为:
(1). 增:Θ(1) (只能在尾元素之后新增)
(2). 删:Θ(1) (只能移除首元素)
(3). 查:Θ(1) (只能查询首元素,尾元素)
(4). 改:Θ(1) (只能修改首元素,尾元素)

相关推荐

  1. 数据结构-队列

    2024-02-06 21:30:04       55 阅读
  2. 数据结构队列

    2024-02-06 21:30:04       68 阅读
  3. 数据结构-队列

    2024-02-06 21:30:04       50 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-02-06 21:30:04       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-02-06 21:30:04       101 阅读
  3. 在Django里面运行非项目文件

    2024-02-06 21:30:04       82 阅读
  4. Python语言-面向对象

    2024-02-06 21:30:04       91 阅读

热门阅读

  1. 记一次面试题

    2024-02-06 21:30:04       50 阅读
  2. 观察者模式

    2024-02-06 21:30:04       53 阅读
  3. 【技术预研】StarRocks官方文档浅析(4)

    2024-02-06 21:30:04       68 阅读
  4. go常见问题

    2024-02-06 21:30:04       49 阅读
  5. 1001 A+B Format - PAT(Advance Level)Practive

    2024-02-06 21:30:04       44 阅读
  6. 原语,原子,线程安全

    2024-02-06 21:30:04       52 阅读
  7. 深度学习本科课程 实验3 网络优化

    2024-02-06 21:30:04       45 阅读
  8. docker进阶问题一

    2024-02-06 21:30:04       54 阅读