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

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

Queue概述

示例：

队列的特点

队列的适用场景

Queue概述

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

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

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

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

示例：

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

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

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

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

队列的特点

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

代码语言：javascript复制

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 个队列就起到了缓冲的作用，达到了平衡的效果。排队付款一般较快，等待制作奶茶一般较慢，因此需要安排较多的制作奶茶的店员。

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

linkedlist null queue 队列设计模式

0 人点赞