08、队列数据结构特点？如何实现一个队列？

### 考点分析
当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线 程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？ 实际上，这些问题并不复杂，其底层的数据结构就是队列（queue）。

### 典型回答
队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾， 不允许插队。先进者先出，这就是典型的“队列”。 我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

![输入图片说明](https://images.gitee.com/uploads/images/2020/1031/122353_9adfec5e_1767738.png "屏幕截图.png")

所以，队列跟栈一样，也是一种操作受限的线性表数据结构。 队列的概念很好理解，基本操作也很容易掌握。

作为一种非常基础的数据结构，队列的应用 也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。 它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

如何实现一个”队列”？

队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素， 在队头删除元素，那究竟该如何实现一个队列呢？ 跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用 链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

**使用数组实现顺序队列：**
```
package com.qf.day24;

public class ArrayQueue {
	/** 对类数据 */
	private String[] items = null;
	/** 容器大小 */
	public int n = 0;
	/*** 对列头指针 */
	public int head = 0;
	/** 队列尾指针 */
	public int tail = 0;

public ArrayQueue(int capacity) {
		items = new String[capacity];
		this.n = capacity;
	}

/**
	 * 入队
	 * @param item
	 * @return
	 */
	public boolean enQueue(String item) {
		// tail == n 证明队列已经满了
		if (tail == n) {
			return false;
		}
		// 数据添加到尾部
		items[tail] = item;
		// 改变尾部坐标
		++tail;
		return true;
	}
	/**
	 * 出队
	 * @return
	 */
	public String deQueue() {
		if (head == tail) {
			return null;
			// 头尾相等队列为 null
		}
		String ret = items[head];
		++head;
		return ret;
	}
}
```
你肯定已经发现了，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当tail移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。
这个问题 该如何解决呢？ 
你是否还记得，在数组那一节，我们也遇到过类似的问题，就是数组的删除操作会导致数组中的数据不连续。你还记得我们当时是怎么解决的吗？对，用数据搬移！但是，每次进行出队操作都相当于删除数组下标为 0 的数据，要搬移整个队列中的数据，这样出队操作的时间复杂度就会从原来的 O(1)变为 O(n)。

能不能优化 一下呢？ 实际上，我们在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再 集中触发一次数据的搬移操作。借助这个思想，出队函数 dequeue()保 持不变，我们稍加改造一下入队函数 enqueue()的实现，就可以轻松解决刚才的问题了。下面是具体的代码：
```
public boolean enqueue(String item) { // tail == n 表示队列末尾没有空间了
		if (tail == n) { // tail ==n && head==0，表示整个队列都占满了
			if (head == 0)
				return false;
			// 数据搬移
			for (int i = head; i < tail; ++i) {
				items[i - head] = items[i];
			} // 搬移完之后重新更新 head 和 tail
			tail -= head;
			head = 0;
		}

items[tail] = item;
		++tail;
		return true;
	}
```

![输入图片说明](https://images.gitee.com/uploads/images/2020/1031/123427_b44a2973_1767738.png "屏幕截图.png")

Java技术交流/Java技术提升库

内容风险标识

评论 (0)

Java技术交流/Java技术提升库 .gitee-modal { width: 500px !important; }

内容风险标识