队列_队列出队

---

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人员都占线的情况下，客户会被要求等待，直到有某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。

---

队列的特点

线性结构

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了队列，链表、栈、数组等也是线性表结构。

先进先出

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,…,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

---

队列的种类

阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

并发队列

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

---

队列的实现方式

顺序队列

为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置。

数组实现的队列：顺序队列

链式队列

链表实现的队列：链式队列

---

队列的基本操作

入队

入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

出队

出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。

如果像这样不断出队，对头左边的空间失去作用，队列的容量将会越来越小

为了解决这一问题，需要用数组实现的循环队列方式来维持队列的容量

什么是循环队列？

举个例子解释一下：假设一个队列经过反复的入队和出队操作，还剩下2个元素，在“物理”上分布于数组的末尾位置。这时又有一个新元素将要入队。

在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。

这样一来，整个队列的元素就“循环”起来了。在物理存储上，队尾的位置也可以在队
头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。

一直到（队尾下标+1）%数组长度 = 队头下标时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。

---

队列的具体实现

数组实现循环队列

package 队列;

import java.awt.Font;

/**
 * 数组实现的循环队列
 * @author 15447
 *
 */

public class CircleQueue {
	
	private int[] arrays;
//	队头下标
	private int front;
//	队尾下标
	private int rear;
	
//	构造函数初始化队列
	public CircleQueue(int capacity) {
		this.arrays = new int[capacity];
	}
	
	/**
	 * 入队
	 * @param element 入对的元素
	 */
	public void enQueue(int element) throws Exception {
//		判断队列是否已满
		if ((rear+1)%arrays.length == front) {
			throw new Exception("队列已满");
		}
//		将元素放入队尾下标位置
		arrays[rear] = element;
//		将队尾下标往后移一位
		rear = (rear+1)%arrays.length;
	}
	
	/**
	 * 出队
	 */
	public int deQueue() throws Exception {
		if (rear == front) {
			throw new Exception("队列已空");
		}
		int deQueueElement = arrays[front];
		front = (front+1)%arrays.length;
		return deQueueElement;
	}
	
	/**
	 * 输出队列
	 */
	private void output() {
		for(int i=front; i!=rear; i=(i+1)%arrays.length) {
			System.out.println(arrays[i]);
		}
	}
	
	public static void main(String[] args) throws Exception {
		CircleQueue myQueue = new CircleQueue(6);
		myQueue.enQueue(3);
		myQueue.enQueue(5);
		myQueue.enQueue(6);
		myQueue.enQueue(8);
		myQueue.enQueue(1);
		myQueue.deQueue();
		myQueue.deQueue();
		myQueue.deQueue();
		myQueue.enQueue(2);
		myQueue.enQueue(4);
		myQueue.enQueue(9);
		myQueue.output();
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

链表实现队列

package 队列;

/**
 * 队列的列表实现
 * @author 15447
 *
 */

public class LinkedQueue {
	
	Node head;
	Node tail;
	int size;
	
	/**
	 * 入队
	 * @param element
	 */
	public void enQueue(int element) {
		Node new_node = new Node(element);
		if (size==0) {
			head = new_node;
			tail = new_node;
		} else {
			tail.next = new_node;
			tail = tail.next;
		}
		size++;
	}
	
	/**
	 * 出队
	 */
	public void deQueue() throws Exception {
		if (size==0) {
			throw new Exception("队列已空");
		}
		head = head.next;
		size--;
	}
	
	/**
	 * 节点类
	 * 用于初始化节点
	 *
	 */
	public static class Node {
		int item;
		Node next;
		public Node(int item) {
			this.item = item;
		}
	}
	
	/**
	 * 输出队列
	 */
	public void output() {
		Node item = head;
		while(item!=null) {
			System.out.println(item.item);
			item = item.next;
		}
	}
	
	public static void main(String[] args) throws Exception {
		LinkedQueue linkedQueue = new LinkedQueue();
		linkedQueue.enQueue(1);
		linkedQueue.enQueue(2);
		linkedQueue.enQueue(3);
		linkedQueue.enQueue(4);
		linkedQueue.deQueue();
		linkedQueue.deQueue();
		linkedQueue.output();
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

---

队列的应用

1：应用在任何有限资源池中，用于排队请求，比如数据库连接池等。
2：分布式应用中的消息队列。