第十四届蓝桥杯集训——Queue

第十四届蓝桥杯集训——Queue

目录

第十四届蓝桥杯集训——Queue

Queue概述

示例：

队列的特点

队列的适用场景

Queue概述

队列是一种受限的数据结构，插入操作只能从一端操作，这一端叫作队尾；而移除操作也只能从另一端操作，这一端叫作队头。针对上面购买奶茶队伍的例子，排在收银员一端的就是队头，而新来的人则要排到队尾。

我们将没有元素的队列称为空队，也就是在没人要购买奶茶时，就没人排队了。往队列中插入元素的操作叫作入队，相应地，从队列中移除元素的操作叫作出队。

一般而言，队列的实现有两种方式：数组和链表。这里又提到了链表，我们暂时先不做讲解。用数组实现队列有两种方式，一种是顺序队列，一种是循环队列。这两种队列的存储结构及特点在之后进行介绍。

用数组实现队列，若出现队列满了的情况，则这时就算有新的元素需要入队，也没有位置。此时一般的选择是要么丢掉，要么等待，等待的时间一般会有程序控制。

示例：

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

我们先看看Queue有啥函数啊：

1. add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常(不推荐)
2. remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常(不推荐)
3. element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常(不推荐)
4. offer 添加一个元素并返回true 如果队列已满，则返回false(推荐)
5. poll 移除并返问队列头部的元素 如果队列为空，则返回null(推荐)
6. peek 返回队列头部的元素 如果队列为空，则返回null(推荐)
7. put 添加一个元素 如果队列满，则阻塞
8. take 移除并返回队列头部的元素

队列的特点

队列的特点也是显而易见的，那就是先进先出。出队的一头是队头，入队的一头是队尾。当然，队列一般来说都会规定一个有限的长度，叫作队长(chang)。

package com.item.action;

import java.util.LinkedList;
import java.util.Queue;

public class Demo3 {

	public static void main(String[] args) {
		// add()和remove()方法在失败的时候会抛出异常(不推荐)
		Queue<String> queue = new LinkedList<String>();
		// 添加元素
		/**
		 * add()和offer()都是向队列中添加一个元素。<br/>
		 * 一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，<br/>
		 * 调用 add() 方法就会抛出一个 unchecked 异常，<br/>
		 * 而调用 offer() 方法会返回 false。<br/>
		 * 因此就可以在程序中进行有效的判断！
		 */
		queue.add("0");// 不推荐
		queue.offer("a");
		queue.offer("b");
		queue.offer("c");
		queue.offer("d");
		queue.offer("e");
		for (String q : queue) {
			System.out.print(q + ",");
		}
		System.out.println("\n-----------");
		/**
		 * remove() 和 poll() 方法都是从队列中删除第一个元素。<br/>
		 * 如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，<br/>
		 * 但是新的 poll() 方法在用空集合调用时只是返回 null。<br/>
		 * 因此新的方法更适合容易出现异常条件的情况。
		 */
		System.out.println("poll=" + queue.poll()); // 返回第一个元素，并在队列中删除
		for (String q : queue) {
			System.out.print(q + ",");
		}
		System.out.println("\n-----------");
		/**
		 * element() 和 peek() 用于在队列的头部查询元素。<br/>
		 * 与 remove() 方法类似，在队列为空时，<br/>
		 * element() 抛出一个异常，而 peek() 返回 null。
		 */
		System.out.println("element=" + queue.element()); // 返回第一个元素
		for (String q : queue) {
			System.out.print(q + ",");
		}
		System.out.println("\n-----------");
		System.out.println("peek=" + queue.peek()); // 返回第一个元素
		for (String q : queue) {
			System.out.print(q + ",");
		}
	}

}

队列的适用场景

队列在实际开发中是很常用的。在一般程序中会将队列作为缓冲器或者解耦使用。下面举几个例子具体说明队列的用途。 解耦，即当一个项目发展得比较大时，必不可少地要拆分各个模块。为了尽可能地让各个模块独立，则需要解耦，即我们常听说的高内聚、低耦合。如何对各模块进行解耦？其中一种方式就是通过消息队列。

1) 某品牌手机在线秒杀用到的队列

现在，某个品牌的手机推出新型号，想要购买就需要上网预约，到了开抢时间就得赶紧打开网页守着，疯狂地刷新页面，疯狂地点击抢购按钮。一般在每次秒杀中提供的手机只有几千部。假设有两百万人抢购，则从开抢的这一秒开始，两百万人都开始向服务器发送请求。如果服务器能直接处理请求，把抢购结果立刻告诉用户，同时为抢购成功的用户生成订单，让用户付款购买手机，则这对服务器的要求很高，很难实现。那么该怎么解决呢？解决方法是：在接收到每个请求之后，把这些请求按顺序放入队列的队尾中，然后提示用户“正在排队中……”，接下来用户开始排队；而在这个队列的另一端，也就是队头，会有一些服务器在处理，根据先后顺序告知用户抢购结果。

这就出现了抢购手机时，抢购界面稍后才告诉我们抢购结果的情况。我有个朋友在抢购成功之后，抢购界面提示他稍后去订单中查看结果，当下查看订单却没有发现新订单，其实是因为他的请求已经进入了服务器处理的队列，服务器处理完之后才会为他生成订单。 注：这种方式也叫作异步处理。异步与同步是相对的。同步是在一个调用执行完成之后，等待调用结束返回；而异步不会立刻返回结果，返回结果的时间是不可预料的，在另一端的服务器处理完成之后才有结果，如何通知执行的结果又是另一回事。

2) 生产者和消费者模式

有个非常有名的设计模式，叫作生产者和消费者模式。这个设计模式就像有一个传送带，生产者在传送带这头将生产的货物放上去，消费者在另一头逐个地将货物从传送带上取下来。这个设计模式的实现原理也比较简单，即存在一个队列，若干个生产者同时向队列中添加元素，然后若干个消费者从队列中获取元素。

这时参考奶茶店的例子，每个购买奶茶的人就是一个生产者，依次进入第 1 个队列中，收银员就是一个消费者（假设这个收银员称为消费者 A），负责“消费”队列中的购买者，让购买者逐个从队列中出来。通过提供给购买者带有编号的一张小票，让购买者进入了第 2 个队列。此时收银员在第 2 个队列中又作为生产者出现。

第 2 个队列的消费者是谁？是制作奶茶的店员，这里称之为消费者 B。而一般规模较大的奶茶店，制作奶茶的店员会较多，假设有两人以上，即消费者 B 比消费者 A 多。此时第 2 个队列就起到了缓冲的作用，达到了平衡的效果。排队付款一般较快，等待制作奶茶一般较慢，因此需要安排较多的制作奶茶的店员。

因此对于生产者和消费者的设计模式来说，有一点非常重要，那就是生产的速度要和消费的速度持平。如果生产得太快，而消费得太慢，那么队列会很长。而对于计算机来说，队列太长所占用的空间也会较大。