队列

学习数据结构与算法
2021-05-17 14:29 · 阅读时长10分钟
小课

队列是一种线性存储结构,但是只能从队列前端front添加或入队,从队列尾端rear移除或出队数据。队列具有先进先出FIFO的特点。

队列是一种抽象的数据结构,可以用数组或者链表来实现队列。例如,[1,2,3,4,5,6,7,8,9] 使用队列来存储的示意图。

加载中...
队列的应用

当某共享资源使用(或者处理)数量大于限制数量的时侯,这些请求(或者任务)需要先等待,待资源可用时按照先到先得原则处理,这种情况,这些请求(或者任务)经常会使用队列来保存。

  • CPU调度的任务队列
  • Web服务器请求队列
  • 键盘按键事件队列
  • 多个系统(应用)之间的通信的消息队列

另外,在广度优先搜索算法中我们也经常会用到队列。

常见的队列有以下这些

  • 双端队列,两端都可以入队和出队的队列。
  • 循环队列,在使用数组实现队列时,多次入队出队之后,前端和后端都指向数组末尾,而数组实际上使用率很低,所以引入循环队列,在数组还有空间的时候,继续在数组开始入队元素。
  • 优先队列,每个队列元素都有一个优先级,根据优先级来确定出队的顺序。优先队列内部一般是使用堆来实现。

查看二叉堆课程

注释
加载中...
面试题 17.14. 最小K个数

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例:

输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4]

提示:

  • 0 <= len(arr) <= 100000
  • 0 <= k <= min(100000, len(arr))

这道题最容易想到的就是先排序,然后返回最小的k个数。但是实际面试中,面试官可能还会问,如果数据特别大,大到无法直接对整个数组进行排序,该怎么办?

我们可以将数组中前k个数加入到优先队列中,然后遍历数组中剩下的元素,如果元素小于队列中最大的数,则将最大的数出队,然后将元素入队,如果大于则跳过,直到遍历完成。

加载中...
用栈实现队列

用栈来实现队列先进先出队列。栈的特点先进后出,怎么才能实现先进先出?

加载中...
Queue队列双端队列循环队列