今天继续来给大家上一盘硬菜,保证喂个半饱——嗝。和栈一样,队列(queue)也是一个非常有用的数据结构。同时又非常特殊,它只允许在队尾(rear)插入元素,在队首(front)删除元素,也就是一端进,一端出。
在网上购票普及之前,我们大多数人需要到车站的购票大厅买票,经常是排队排到水泄不通,queue 就和现实中的排队是一模一样的,排在队首的先买到票,然后离开,紧跟着的人移动到队首,直到队列消失。
队列遵循的是 First In First Out,缩写为 FIFO,也就是先进先出,第一个进入队列的第一个先出来。
在上面这幅图中,1 比 2 先进入队列,也比 2 先出队列,规规矩矩的。
对于队列这样一个数据结构来说,它有两个常见的动作:
明白了队列的基本操作后,我们来深入地思考一下,队列是如何工作的。
1) 建立顺序的队列结构需要为其静态分配或者动态申请一串连续的存储空间。
2)然后设置两个指针进行管理:一个队首指针 FRONT,指向队首的元素,一个队尾指针 REAR,指向队尾的元素。初始化的时候,FRONT 和 REAR 都设置为 -1。
3)入队时
检查队列是否已经满了,需要一个 isFull() 的方法来判断;
对于第一个元素,设置 FRONT 的值为 0;
每次在队尾插入一个元素时,REAR 加 1,然后把队尾的元素指向 REAR。
4)出队时
检查队列是否为空,需要一个 isEmpty() 的方法来判断;
用一个临时变量来保存队首的元素,以便出队后返回;
每次在队首删除一个元素时,FRONT 加 1;
如果是最后一个元素,重置 FRONT 和 REAR 为 -1。
队列为空的时候,FRONT 和 REAR 等于 -1;把元素 1 入队的时候,FRONT 变为 1,REAR 加 1 变为 0,queue[FRONT]=queue[REAR] 为 1;把元素 2 入队的时候,REAR 加 1 变为 1,queue[REAR] 为 2,queue[FRONT] 仍然为 1;接着,元素 3 入队;元素 4 入队;元素 5 入队,REAR 变为 4,queue[REAR] 为 5,queue[FRONT] 仍然为 1。
元素 1 出队的时候,FRONT 为 0,queue[FRONT] 为 1,然后 FRONT 加 1 变为 1;元素 2 出队的时候,queue[FRONT] 为 2,然后 FRONT 加 1 变为 2;接着,元素 3 出队;元素 4 出队;元素 5 出队的时候,queue[FRONT] 为 5,FRONT 为 4,REAR 为 4,出队后,FRONT 和 REAR 重设为 -1。
假设队列中的元素为 int 类型,队列的大小为 5,我们可以用 Java 语言来自定义一个最简单的 queue。它需要 3 个字段:
- class Queue {
- int SIZE = 5;
- int items[] = new int[SIZE];
- int front, rear;
- }
初始化队列:
- Queue() {
- front = -1;
- rear = -1;
- }
入队:
- void enQueue(int element) {
- if (isFull()) {
- System.out.println("队列已经满了");
- } else {
- if (front == -1)
- front = 0;
- rear++;
- items[rear] = element;
- System.out.println("插入 " + element);
- }
- }
出队:
- int deQueue() {
- int element;
- if (isEmpty()) {
- System.out.println("队列空了");
- return (-1);
- } else {
- element = items[front];
- if (front >= rear) {
- front = -1;
- rear = -1;
- }
- else {
- front++;
- }
- System.out.println("删除 -> " + element);
- return (element);
- }
- }
检查队列是否已经满了:
- boolean isFull() {
- if (front == 0 && rear == SIZE - 1) {
- return true;
- }
- return false;
- }
检查队列是否为空:
- boolean isEmpty() {
- if (front == -1)
- return true;
- else
- return false;
- }
来个 main() 方法测试下:
- void display() {
- int i;
- if (isEmpty()) {
- System.out.println("队列为空");
- } else {
- System.out.println("\n队首的下标-> " + front);
- System.out.println("元素 -> ");
- for (i = front; i <= rear; i++)
- System.out.print(items[i] + " ");
- System.out.println("\n队尾的下标-> " + rear);
- }
- }
- public static void main(String[] args) {
- Queue q = new Queue();
- // 队列为空的时候不允许出队
- q.deQueue();
- // enQueue 5 elements
- q.enQueue(1);
- q.enQueue(2);
- q.enQueue(3);
- q.enQueue(4);
- q.enQueue(5);
- // 队列满了的时候不允许入队
- q.enQueue(6);
- q.display();
- // 出队
- q.deQueue();
- // 打印
- q.display();
- }
打印结果如下所示:
- 队列空了
- 插入 1
- 插入 2
- 插入 3
- 插入 4
- 插入 5
- 队列已经满了
- 队首的下标-> 0
- 元素 ->
- 1 2 3 4 5
- 队尾的下标-> 4
- 删除 -> 1
- 队首的下标-> 1
- 元素 ->
- 2 3 4 5
- 队尾的下标-> 4
队列空了插入 1插入 2插入 3插入 4插入 5队列已经满了队首的下标-> 0元素 -> 1 2 3 4 5 队尾的下标-> 4删除 -> 1队首的下标-> 1元素 -> 2 3 4 5 队尾的下标-> 4
好了,这种基本的队列已经可以正常工作了,但它有一个问题:当已经出队了 N 个元素后,按理说,应该可以再入队 N 个元素,对吧?因为省出来了 N 个空间嘛。
- Queue q = new Queue();
- // enQueue 5 elements
- q.enQueue(1);
- q.enQueue(2);
- q.enQueue(3);
- q.enQueue(4);
- q.enQueue(5);
- // 出队
- q.deQueue();
- q.deQueue();
- q.enQueue(6);
- q.enQueue(7);
但事实上,这段代码在运行的时候报错了:
- 插入 1
- 插入 2
- 插入 3
- 插入 4
- 插入 5
- 删除 -> 1
- 删除 -> 2
- Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
- at com.itwanger.queue.Queue.enQueue(Queue.java:23)
- at com.itwanger.queue.Queue.main(Queue.java:89)
看见 ArrayIndexOutOfBoundsException 我们就知道,数组越界了。这是因为我们是用数组实现的队列,在出队的时候 REAR 并没有减小,导致入队的时候 items[rear++]超出了数组的边界。
可以把问题归咎于我们实现队列的方式上,也可以浅显地认为基本类型的队列存在有局限性。随着入队和出队的连续操作,队列中的元素在不停地变化,队列所占的存储空间也在分配的连续空间中不停的移动。
当 REAR 增加到超出数组大小的范围之后,队列就无法添加新的元素了,事实上还有很多空间可以利用,但它们仍然被已出队的元素占用着——正所谓“附身”啊。除非所有的元素均被移除后, FRONT 和 REAR 被重置,队列才能重新使用。
由于基本类型的队列存在这种局限性,我们就迫切的需要一种新型队列的出现——环形队列(Circular queue) 就闪亮登场了。
那环形队列是如何工作的呢?它是怎么解决这个问题的呢?
1)同样需要一串连续的存储空间。
2)初始化的时候和基本类型的队列 完全一样;
3)入队时
- boolean isFull() {
- if (front == 0 && rear == SIZE - 1) {
- return true;
- }
- if (front == rear + 1) {
- return true;
- }
- return false;
- }
- void enQueue(int element) {
- if (isFull()) {
- System.out.println("队列已经满了");
- } else {
- if (front == -1)
- front = 0;
- rear = (rear + 1) % SIZE;
- items[rear] = element;
- System.out.println("插入 " + element);
- }
- }
4)出队时
- int deQueue() {
- int element;
- if (isEmpty()) {
- System.out.println("队列空了");
- return (-1);
- } else {
- element = items[front];
- if (front >= rear) {
- front = -1;
- rear = -1;
- }
- else {
- front = (front + 1) % SIZE;
- }
- System.out.println("删除 -> " + element);
- return (element);
- }
- }
main() 方法的测试代码就不再贴了,和基本类型的队列时差别不大。一图胜千言,我们来画一幅图表示下环形队列的工作方式。
当队列第一次被填满了以后,出队了两个元素,此时下标为 0 和 1 的两个位置空了出来,然后入队元素 6,意味着 6 变成了队尾,也就是 REAR 等于 0 了;再入队元素 7,7 变成了队尾,也就是 REAR 等于 1 了。
现在,来思考一个问题,假如此时执行 deQueue() 方法出队一个元素时,哪一个元素会被移除呢?答案是元素 3,因为此时它在队首,之后是元素 4,元素 5,元素 6,元素 7,虽然直观上看起来不是那么回事,但如果把它想象成一个环形的而不是直线型的就很好理解了。
对比来说,环形队列比普通类型的队列在容量的利用上更充分一点。
除了基本类型和环形队列之外,队列还有优先级队列和双端队列,虽然它们都归到了队列这一类,但其实并不遵循 FIFO 的规则,所以我就打算把它们拎出来单独来讲。
本文转载自微信公众号「 沉默王二」,可以通过以下二维码关注。转载本文请联系 沉默王二公众号。
??提到慕尼黑,大家第一个想到总是啤酒节,其实慕尼黑的文化同样闻名世界。慕尼...
3月24日,腾讯发布2020年Q4及全年财报,其中金融科技及企业服务第四季收入385亿...
注册了 域名 不备案可以吗?可以的。 注册域名 并不是一定要备案的,只有搭 建网...
案例背景 高校健康打卡项目发起于北京大学软件与微电子学院,是该学院张齐勋老师...
客户简介 全民直播是一家涵盖游戏、娱乐、户外等多领域泛娱乐的直播平台。2015年...
客户简介 趣医网(quyiyuan.com)创立于2014年,为京颐集团重要成员企业之一,是...
API风格说明 当前ECS服务对外开放两类风格的API: ECS服务自定义规范的API(以下...
公司介绍 我们公司是全球法律服务整合平台,已有的4万多名律师遍布全国359个城市...
排查思路 无法通过远程桌面连接裸金属服务器时,我们推荐您按照以下思路排查问题...
云虚拟主机 可以干什么?云 虚拟主机 可以是搭 建网站 的重要产品,可用来存放网...