【线性表】队列

ゝ一纸荒年。 2022-04-05 12:14 212阅读 0赞

**目录**

一、队列的定义

二、常见的三种队列及其实现

1、顺序队列

2、循环队列

3、动态顺序队列

4、链式队列

三、阻塞队列和并发队列

四、队列的应用场景

--------------------

## 一、队列的定义 ##

队列：同栈一样，队列也是一种“操作受限”的线性表，只不过栈的插入、删除操作被受限在表的一端，而队列的插入、删除操作则分别被受限于表的两端。

队列有两个最基本操作：入队enqueue()——将数据插入到队列尾部；出队dequeue()——将队列头部的第一个数据从队列中删除并返回。

## 二、常见的三种队列及其实现 ##

### 1、顺序队列 ###

**顺序队列采用数组实现，其实现涉及的内容如下所示：**

（1）操作要素：数组arr、位置head、位置tail、队列元素个数count

（2）队列的状态：队空、队满

（3）队列的主要操作：入队、出队

可以看到，顺序队列和顺序栈在操作要素的区别是队列需要两个标记位置的变量，而栈只需要一个top。这是因为前者的两个主要操作在不同端进行，而后者插入、删除都在同一端。

**顺序队列出队操作的逻辑为：**

首先判断队列是否为空（tail == head时为空），若为空，则提示“队列为空，无法取出数据”；否则，执行取数据操作，返回该数据，并让count减1、head增1。

**顺序队列入队操作的逻辑为：**

首先判断队列是否为满（tail == 数组的长度），若为满，则提示“队列已满，无法插入数据”；否则，插入数据，并让count加1、tail增1。

class ArrayQueue {
    	// 数组：items  数组大小：n（默认为5）
    	private String[] items;
    	private int n = 5;
    	// head：队头下标  tail：队尾下标
    	private int head = 0;
    	private int tail = 0; //初始状态下的队列（空队列），head、tail都为0
    	// count：队列元素个数
    	private int count = 0; // count = tail - head  所以不要count这个变量也可以
    	
    	// 申请一个默认大小为5的队列
    	public ArrayQueue() {
    		items = new String[n];
    	}  
    	// 申请一个指定大小为n的队列
    	public ArrayQueue(int n) {
    		this.n = n;
    		items = new String[n];
    	}
    	
    	// 入队操作
    	public boolean enqueue(String item) {
    		// 如果tail == n 表示队列已经满了
    		if (tail == n) {
    			System.out.println("队列已满，入队失败！");
    			return false;
    		}
    		items[tail] = item;
    		++tail;
    		++count;
    		return true;
    	}
    	
    	// 出队操作
    	public String dequeue() {
    		// 如果head == tail 表示队列为空
    		if (head == tail) {
    			System.out.println("队列为空，出队失败！");
    			return null;
    		}
    		String ret = items[head];
    		++head;
    		--count;
    		return ret;
    	}
    	
    	// 查看队列的最大容量 和 队列现在的元素个数
    	public void count() {
    		System.out.println("队列的最大容量为："+this.n+"  队列现在的元素个数为："+this.count);
    	}
    	
    	// 查看队列的所有元素
    	public void printAll() {
    		for (int i=head; i<tail; i++) {
    			System.out.print(items[i] + "  ");
    		}
    		System.out.println();
    	}
    	
    	public void retCount() {
    		System.out.println(count +"   "+ (tail-head)); // count和tail-head是一样的
    	}
    }
    
    public class ArrayQueueTest {
    	public static void main(String[] args) {
    		ArrayQueue queue1 = new ArrayQueue();
    		ArrayQueue queue2 = new ArrayQueue(3);
    		
    		//1、测试队列为空时的出队操作
    		System.out.println("=============================");
    		for (int i=0; i<5; i++) {
    			queue1.enqueue("hello");
    		}
    		queue1.printAll();
    		queue2.printAll();
    		queue1.dequeue();
    		queue2.dequeue();
    		
    		//2、测试队列满、假满时的入队操作
    		System.out.println("=============================");
    		for (int i=0; i<3; i++) {
    			queue2.enqueue("world!");
    		}
    		queue1.printAll();
    		queue2.printAll();
    		queue1.count();
    		queue2.count();
    		queue1.enqueue("Java");
    		queue2.enqueue("Java");
    		queue1.printAll();
    		queue2.printAll();
    	}
    }

运行结果如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70][]

可以看到，queue1在第二次测试之前，队列前面有一个空位（前面第一次测试出队），但是却无法入队，依然报队列已满的错误。而由于队列的使用经常要在队列前端执行出队操作，这就会导致数组前面出现很多空位，而当tail下标跑到数组尾部不能再入队了，这无疑会造成空间的浪费。事实上，这是数组实现队列的最大缺点。

### 2、循环队列 ###

前面的顺序队列会出现一种“假满”状态：队列的数组前面有很多空位，但当tail下标指到队尾时，却无法再进行入队操作。这个问题有两种解决方法。

其一，只要tail一到达数组尾部，就判断数组前面是否有空位（count < n），如果是，就做一次搬移操作，将所有元素往前移动(n-count)步；如果不是则是真的满了，无法再入队，或者动态申请一个更大的队列，将原队列的数据都搬过去。

其二，就是采用循环队列的方式。其中第一种方法搬移数据会比较耗时间，我先采用第二种方式来解决“假满”问题。

循环队列的出队、入队操作的逻辑跟前面基本一样，只不过是细微之处有所区别。

循环队列的判空条件为：head == tail    判满条件为：(tail+1)%n == head

class CircularArrayQueue {
    	// 数组：items  数组大小：n（默认为6）
    	private String[] items;
    	//private int n = 5;
    	private int n = 6;
    	// head：队头下标  tail：队尾下标
    	private int head = 0;
    	private int tail = 0; //初始状态下的队列（空队列），head、tail都为0
    	// count：队列元素个数
    	private int count = 0; 
    	
    	// 申请一个默认大小为5的队列
    	public CircularArrayQueue() {
    		items = new String[n];
    	}  
    	// 申请一个指定大小为n的队列
    	public CircularArrayQueue(int n) {
    		//this.n = n;
    		this.n = n + 1;  // 用户指定生成大小为5的队列，则内部创建一个大小为6的数组，留一个空位来判满
    		items = new String[n];
    	}
    	
    	// 入队操作
    	public boolean enqueue(String item) {
    		// 如果(tail+1)%n == head表示队列已经满了
    		//if (tail == n) {
    		if ( (tail+1)%n == head ) {
    			System.out.println("队列已满，入队失败！");
    			return false;
    		}
    		items[tail] = item;
    		//++tail;
    		tail = (tail+1) % n;
    		++count;
    		return true;
    	}
    	
    	// 出队操作
    	public String dequeue() {
    		// 如果head == tail 表示队列为空
    		if (head == tail) {
    			System.out.println("队列为空，出队失败！");
    			return null;
    		}
    		String ret = items[head];
    		//++head;
    		head = (head+1) % n;
    		--count;
    		return ret;
    	}
    	
    	// 查看队列的最大容量 和 队列现在的元素个数
    	public void count() {
    		System.out.println("队列的最大容量为："+(this.n-1)+"  队列现在的元素个数为："+this.count);
    	}
    	
    	// 查看队列的所有元素
    	public void printAll() {
    		//for (int i=head; i<tail; i++) {
    		for (int i=head; i%n != tail; i++) {
    			System.out.print(items[i] + "  ");
    		}
    		System.out.println();
    	}
    	
    	public void retCount() {
    		//System.out.println(count +"   "+ (tail-head));
    		int sum = 0;
    		if ( tail >= head) {
    			sum = tail - head;
    		} else {
    			sum = tail - head + n;
    		}
    		System.out.println(count +"   "+ sum);
    	}
    }
    
    public class CircularArrayQueueTest {
    	public static void main(String[] args) {
    		CircularArrayQueue queue1 = new CircularArrayQueue();
    		CircularArrayQueue queue2 = new CircularArrayQueue(3);
    		
    		//1、测试队列为空时的出队操作
    		System.out.println("=============================");
    		for (int i=0; i<5; i++) {
    			queue1.enqueue("hello");
    		}
    		queue1.printAll();
    		queue2.printAll();
    		queue1.dequeue();
    		queue2.dequeue();
    		
    		//2、测试队列满、假满时的入队操作
    		System.out.println("=============================");
    		for (int i=0; i<3; i++) {
    			queue2.enqueue("world!");
    		}
    		queue1.printAll();
    		queue2.printAll();
    		queue1.count();
    		queue2.count();
    		queue1.enqueue("Java");
    		queue2.enqueue("Java");
    		queue1.printAll();
    		queue2.printAll();
    	}
    }

注意这里我采用预留一个空间的方式来判满，所以在队列的带参数构造函数中，我们让this.n = n + 1，也就是说**用户申请一个大小为5的队列**时，我们在内部申请**一个大小为6的数组**，多出的一个空间用来判满。

当然，也可以利用count来判满，这样就不用多预留一个空间，此时的判满条件为：count==n。

关于循环队列的判空、判满条件可以参考《大话数据结构》，或者看下面的链接：

[循环队列的队空与队满的条件][Link 1]

运行结果如下图所示，此时就不会出现“假满”的现象了。

![20181212164623896.png][]

### 3、动态顺序队列 ###

下面我采用第一种方式来解决“假满”问题。

class DynamicArrayQueue {
    	// 数组：items  数组大小：n（默认为5）
    	private String[] items;
    	private int n = 5;
    	// head：队头下标  tail：队尾下标
    	private int head = 0;
    	private int tail = 0; //初始状态下的队列（空队列），head、tail都为0
    	// count：队列元素个数
    	private int count = 0; // count = tail - head  所以不要count这个变量也可以
    	
    	// 申请一个默认大小为5的队列
    	public DynamicArrayQueue() {
    		items = new String[n];
    	}  
    	// 申请一个指定大小为n的队列
    	public DynamicArrayQueue(int n) {
    		this.n = n;
    		items = new String[n];
    	}
    
    	// 入队操作
    	public boolean enqueue(String item) {
    		// 如果tail == n 表示队列末尾没有空间了
    		if (tail == n) {
    			// 如果tail == n && head == 0  表示整个队列都占满了
    			if (head == 0) {
    				System.out.println("队列已满，入队失败！");
    				return false;
    			} else {
    				// 否则，说明队列头部还有空间
    				// 数据搬移
    				for (int i=head; i<tail; i++) {
    					items[i-head] = items[i];
    				}
    				// 搬移完之后。更新head、tail
    				tail -= head;
    				head = 0;
    			}
    		}
    		// 如果队列末尾还有空间，就直接插入末尾
    		items[tail] = item;
    		++tail;
    		++count;
    		return true;
    	}
    	
    	// 出队操作
    	public String dequeue() {
    		// 如果head == tail 表示队列为空
    		if (head == tail) {
    			System.out.println("队列为空，出队失败！");
    			return null;
    		}
    		String ret = items[head];
    		++head;
    		--count;
    		return ret;
    	}
    	
    	// 查看队列的最大容量 和 队列现在的元素个数
    	public void count() {
    		System.out.println("队列的最大容量为："+this.n+"  队列现在的元素个数为："+this.count);
    	}
    	
    	// 查看队列的所有元素
    	public void printAll() {
    		for (int i=head; i<tail; i++) {
    			System.out.print(items[i] + "  ");
    		}
    		System.out.println();
    	}
    	
    	public void retCount() {
    		System.out.println(count +"   "+ (tail-head));
    	}
    }
    
    public class DynamicArrayQueueTest {
    	public static void main(String[] args) {
    		DynamicArrayQueue queue1 = new DynamicArrayQueue();
    		DynamicArrayQueue queue2 = new DynamicArrayQueue(3);
    		
    		//1、测试队列为空时的出队操作
    		System.out.println("=============================");
    		for (int i=0; i<5; i++) {
    			queue1.enqueue("hello");
    		}
    		queue1.printAll();
    		queue2.printAll();
    		queue1.dequeue();
    		queue2.dequeue();
    		
    		//2、测试队列满、假满时的入队操作
    		System.out.println("=============================");
    		for (int i=0; i<3; i++) {
    			queue2.enqueue("world!");
    		}
    		queue1.printAll();
    		queue2.printAll();
    		queue1.count();
    		queue2.count();
    		queue1.enqueue("Java");
    		queue2.enqueue("Java");
    		queue1.printAll();
    		queue2.printAll();
    	}
    }

注意出队操作与顺序队列完全相同，区别在于入队队列：在顺序队列中，我们认为tail == n就说明队列已经满了；而这里还要进一步判断是否满足head == 0，如果是说明真的满了，否则说明是假满状态，因此要把所有数据往前搬移，这样空位就跑到后面去了，因此也就可以继续插入数据。

运行结果如下所示，同样不会出现假溢出的现象了

![2018121217494897.png][]

### 4、链式队列 ###

链式队列我们采用内部类作为结点类，实现代码如下

class LinkedListQueue {
    	// 队列的队首、队尾引用
    	private Node head = null;
    	private Node tail = null;
    	
    	// 入队
    	public void enqueue(String value) {
    		Node newNode = new Node(value, null);
    		// 如果队列为空，一个元素都没有
    		if (tail == null) {  // 或者head==null && tail==null
    			head = newNode;
    			tail = newNode;
    		} else {
    			tail.next = newNode;    // 尾插法
    			tail = tail.next;
    		}
    	}
    	
    	// 出队
    	public String dequeue() {
    		String data = null;
    		if (tail==null && head==null) {  // 队列有0个元素
    			System.out.println("队列为空，出队失败！");
    			return null;
    		} else if (tail == head) {       // 队列有1个元素
    			data = head.data;
    			tail = null;
    			head = null;
    			return data;
    		} else {
    			data = head.data;
    			head = head.next;
    			return data;
    		}
    	}
    	
    	// 打印整个队列
    	public void printAll() {
    		Node temp = head;
    		while (temp != null) {
    			System.out.print(temp.data+"  ");
    			temp = temp.next;
    		}
    		System.out.println();
    	}
    	
    	// 查看队首元素
    	public String head() {
    		if (head==null && tail==null) { //如果为空
    			System.out.println("队列为空，没有队首元素");
    			return null;
    		}
    		return head.data;
    	}
    	
    	// 内部类
    	private static class Node {
    		private String data;
    		private Node next;
    		
    		public Node() {}
    		public Node(String data) {
    			this.data = data;
    			this.next = next;
    		}
    		public Node(String data, Node next) {
    			this.data = data;
    			this.next = next;
    		}
    		
    		public String getData() {
    			return data;
    		}
    	}
    }
    
    
    public class LinkedListQueueTest {
    	public static void main(String[] args) {
    		LinkedListQueue queue = new LinkedListQueue();
    		//1、
    		queue.printAll();
    		queue.dequeue();
    		
    		//2、
    		System.out.println("===========================");
    		queue.enqueue("hello");
    		queue.enqueue("world");
    		queue.enqueue("Java");
    		queue.printAll();
    		System.out.println(queue.head());
    		queue.dequeue();
    		queue.printAll();		
    	}
    }

运行结果如下图所示：

![20181213111905412.png][]

## 三、阻塞队列和并发队列 ##

这里我只是简单讲下两者的概念

**阻塞队列：**在队列的基础上，加上阻塞操作

当队列为空时，从队头取数据会被阻塞（直到有了数据才返回）；

当队列为满时，插入数据到队列的操作会被阻塞（直到有闲置空间再插入）。

我们可以看到，这其实就是一个**“生产者——消费者”**模型，如下图所示。这个模型的作用是协调生产和消费的速度：当生产者（生产线程）生产数据的速度过快，消费者（消费线程）**来不及**取数据，这时存储数据的队列（缓存）很快就满了。这时，生产线程就会被阻塞，直到消费线程消费了一些数据之后，生产线程才会被重新唤醒继续生产。

![20181213113735312.png][]

**并发队列：**并发队列即线程安全的队列。

在多线程情况下，多个线程同时操作一个队列，这时就会存在线程安全问题。如何实现一个线程安全的队列呢？最简单直接的方式是直接在enqueue()、dequeue()方法上**加锁**。但是锁粒度大，并发度会比较低，同一时刻只允许一个线程进行存或取操作，这样也比较不公平。不过，如果是基于数组的循环队列，**加上CAS原子操作**，就可以实现非常高效的并发队列了（这也是循环队列比链式队列应用更广的原因）。

## 四、队列的应用场景 ##

关于队列在高并发环境下的应用可以看下面这篇文章

[聊聊高并发系统之队列术][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70]: /images/20220405/e092633ed29c4369b344a31734d4624a.png
[Link 1]: https://blog.csdn.net/huangkq1989/article/details/5719529
[20181212164623896.png]: /images/20220405/f0a193f5824746918de8ac58a3951235.png
[2018121217494897.png]: /images/20220405/e25abfffe3a74173a20bb09a2644f43e.png
[20181213111905412.png]: /images/20220405/97760144a7964862bfda10c3c27614ac.png
[20181213113735312.png]: /images/20220405/cb726583f8ae4129bb48039ad26d727c.png
[Link 2]: https://blog.csdn.net/yzh_2017/article/details/53791428