码代码的冰果果

个人在线笔记

0%

队列

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 7.7k 阅读时长 ≈ 14 分钟

鲁迅先生曾经说过：数据结构来源于生活，又高于生活。今天要讲的这个队列，在我们的日常生活中随处可见，例如在饭堂排队打饭、在银行排队办理业务，这些就是活生生的例子。队列没有那么的复杂，但它却是一种应用很广泛的结构。搬好小板凳，听我慢慢道来！

简介

img

引用百度百科中关于队列的定义：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列是对数据的”存”和”取”操作有着严格要求的一种线性存储结构。队列的两端都有”开口”，且要求数据只能从一端进，从另一端出。记住一点即可：先入先出。

简单的说，就是你到银行去办理业务，办理业务的柜台都是叫号的，先到先取了号的就能够先办理没有人可以插队，这就是先入先出。

应用场景

在日常生活中关于队列这种数据结构的应用场景就很多，例如：医院的挂号系统、银行排队办理业务等等。在计算机或计算机之间为了提高工作效率，常常是采用队列机制，避免线程间、程序间的冲突。根据队列机制作用的不同，队列还可以分为工作队列机制、消息队列机制 。

代码实现

一般，队列有两种实现方式，数组实现与链表实现。

这里使用数组来模拟队列，具体代码实现使用的是java语言。队列还有普通队列、环形队列之分，我们直接跳过普通队列，普通队列有一些缺点在实际的应用中也不会使用。环形队列是普通队列的升级版本，针对普通队列复用性差的缺点进行了改进。

环形队列的实现方法

基本操作：队列应该包含但不限于以下操作：入队、出队、获取队列头、求队列长度、判空、判满、遍历。

头尾指针：队列的一大特点是先入先出，这就要求队列元素的添加操作在队列的一端进行，队列元素的删除操作在队列的另一端进行，需要使用两个指针（变量）来标记队列的前后端的下标。队列头指针，使用front变量；队列尾指针，使用rear变量。

队列容量：队列数据可以使用一维数组进行存储，队列的容量使用maxSize变量记录。（即数组长度=maxSize）。

实现闭环：将队列的存储区想象成一个头尾相连的圆环，当队尾指针rear到达数组的最大容量时，如果还有元素入队并且前边有剩余的空间，则队尾指针rear又指向前边，形成一个闭环（逻辑上形成一个闭环）。那怎么实现队尾指针rear又重新指向前边，形成一个闭环呢？每次执行入队操作时都判断一下rear是否达到了数组的最大容量？不不不，有一个很巧秒的方法：由于front（头指针）、rear（尾指针）始终要在数组内，即front或rear < Array.length=maxSize，可以使用模运算%实现，模运算可以简单理解为求余数。尾指针的后移使用该表达式实现rear=( rear+1 ) % maxSize结果始终在0~maxSize内（包括前者不包括后者）。传送门：什么是模运算。

实现闭环这里是不是开始挠头了？那就对了，不要忘记了标题，哈哈。跟着下边的代码敲一遍可能就理解了，仅仅靠看就想理解透有点困难，要多思索，多练习。

总结一下：

  1. 基本操作。入队、出队、获取队列头、求队列长度、判空、判满、遍历。

    • 入队操作addQueue()
    • 出队操作getQueue()
    • 获取队列头headQueue()
    • 获取队列长度getSize()
    • 判空checkEmpty()
    • 判满checkFull()
    • 遍历showQueue()

  2. 变量定义。队列头指针

    1
    		 
    front

    、队列尾指针

    1
    		 
    rear

    、队列容量

    1
    		 
    maxSize

    。

    • 队列头指针front，指向队列的第一个元素，初始值为0（可以理解为，该变量存放队列中第一个元素在数组中的下标）。
    • 队列尾指针rear，指向队列的最后一个元素的后一个位置，初始值为0。
    • 队列的容量使用maxSize变量记录，通过构造方法进行定义。
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
 
class CircleQueue{
	//表示队列的最大容量
	private int maxSize;
	//头指针
	private int front;
	//尾指针
	private int rear;
    //该数组用于存放队列的数据
	private int[] arr;
	public CircleQueue(int maxSize) {//构造方法
		this.maxSize=maxSize+1;
		this.arr=new int[this.maxSize];
		this.front=0;
		this.rear=0;
	}
	public void addQueue(int value) {//入队列操作
    ...
	}
	public int getQueue() {//出队列操作
    ...
	}
	public void checkEmpty() {//判断队列是否为空
    ...
	}
	public void checkFull() { //判断队列是否已满
    ...
	}
	public void showQueue() {//显示队列中的所有数据
    ...
	}
	public int getSize() {//计算队列中元素个数
    ...
	}
	public int headQueue() {//查看队列头的数据
    ...
	}
}

构造方法中为什么加1，看后边的判空、判满操作的解释就知道了。（我是传送门）

入队操作

入队操作，方法名记为“addQueue()”。

入队操作，思路：

  1. 队列尾指针rear，指向队列的最后一个元素的后一个位置，可直接存储数据到此处。
  2. 将尾指针往后移

rear尾指针，指向的是队列最后一个元素的后一个位置，故直接赋值。

1
2
3
4
5
 
public void addQueue(int value) {//入队列操作
		checkFull();//判断队列是否已满
		arr[rear]=value;
		rear=( rear+1 ) % maxSize;//尾指针rear后移一位
}

尾指针rear后移一位,为什么使用模运算，请回顾一下前边关于环形队列的实现闭环操作的解释。

出队操作

出队操作，方法名记为“getQueue()”。

出队操作，思路：

  1. 取出数据存放到变量value中
  2. 头指针后移
  3. 返回数据
1
2
3
4
5
6
 
public int getQueue() {//出队列操作
	checkEmpty();//判断队列是否为空
	int value = arr[front];
	front =  (front+1) % maxSize;//头指针front后移一位
	return value;
}

判空、判满操作

判断队列是空还是满，有一点点复杂。我们可以通过rear==front来判断队列是否为空。但是这里有一个问题：假设一直都是执行入队列操作，没有执行过出队列操作。根据前边对于环形队列的实现方法的描述，当队列满了的时候，front将会指向0，也就是说此时rear==front，这时候没法区分是空还是满。

解决方法还是有的，这里有两个方法：

  1. 添加一个变量，当执行入队列操作时加1，执行出队列操作时减1，通过判断该变量是否为正数再结合rear==front，就可以区分队列是空还是满。
  2. 队列空出一个元素的存储空间，规定（rear+1）==front表示队列为满。

方法一，多出来了一个变量，增加了系统开销，不推荐。这里采用第二种方法。

判空操作，方法名记为“checkEmpty()”。

判空操作，思路：

  • 通过判断rear==front
1
2
3
4
5
 
public void checkEmpty() {//判断队列是否为空
	if(rear==front) {
		throw new RuntimeException("队列为空，不能取数据");
	}
}

判满操作，方法名记为“checkFull()”。

判满操作，思路：

  • 通过判断（rear+1）==front
1
2
3
4
5
 
public void checkFull() { //判断队列是否已满
	if(((rear+1)-front)%maxSize==0) {
		throw new RuntimeException("队列已满，不能加入数据！");
	}
}

图中（f）即为满状态，已无法执行入队操作添加数据，牺牲了一个存储空间。

获取队列长度操作

遍历操作，方法名记为“getSize()”。

遍历操作，思路：

  • 队列长度，通过式子(rear - front + maxSize) % maxSize来计算
1
2
3
4
 
public int getSize() {//计算队列中元素个数
	checkEmpty();//判断队列是否为空
	return (rear - front + maxSize) % maxSize;
}

队列头指针front，指向队列的第一个元素，初始值为0。队列尾指针rear，指向队列的最后一个元素的后一个位置，初始值为0。rear-front即可得到队列中元素的个数，可以尝试代入几个数据测试一下。加maxSize可以看作是给模运算加个绝对值，防止出现负数。传送门：什么是模运算。

1
2
3
4
5
 
队列中没有数据：	rear=front=0;	队列中有rear-front=0个数据
队列中有1个数据：	rear=1;front=0;	队列中有rear-front=1个数据
队列中有2个数据：	rear=2;front=0;	队列中有rear-front=2个数据
执行出队操作，队列中剩下1个数据：rear=2;front=1;	队列中有rear-front=1个数据
...

遍历操作

遍历操作，方法名记为“showQueue()”。

遍历操作，思路：

  1. 获取队列中元素的个数（队列长度）
  2. 遍历数组
1
2
3
4
5
6
 
public void showQueue() {//显示队列中的所有数据
	checkEmpty();//判断队列是否为空
	for(int i=front+getSize()-1;i>=front;i--) {//getSize()方法，获取队列中元素个数
		System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
	}
}

遍历操作中的for循环判断条件可以改成for(int i=front; i<front+getSize(); i++)，这样子更加容易理解（我是为了实现先加入的数据打印在底下的效果）。队列头指针front，指向队列的第一个元素，从front开始打印出队列中所有的数据。队列中数据的个数由getSize()方法获得，由于front+size()有可能会大于maxSize,为了防止出现数组越界异常i不能直接使用，0<=i%maxSize<maxSize（不理解为什么使用模运算，请回顾一下前边关于环形队列的实现闭环操作的解释）。

获取队列头操作

获取队列头操作，方法名记为“headQueue()”。

获取队列头操作，思路：

  • 队列头指针front，指向队列的第一个元素。
1
2
3
4
 
public int headQueue() {//查看队列头的数据
	checkEmpty();//判断队列是否为空
	return arr[front];//头指针，指向队列的第一个元素
}

测试

准备工作

新建一个测试类Test。

初始化一个容量maxSize为3的队列，打印出一个菜单让用户选择相应的操作。

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
 
import java.util.Scanner;
public class Test {
	public static void main(String[] args) {
		//初始化一个队列
		CircleQueue queue = new CircleQueue(3);//队列最大容量为3
		char key = ' ';//接受用户输入数据
		boolean loop = true;//菜单循环判断条件
		//打印出一个菜单
		while(loop) {
			System.out.println("\n  s(show)：显示队列");
			System.out.println("  e(exit)：退出程序");
			System.out.println("   a(add)：添加数据到队列");
			System.out.println("   g(get)：从队列取出数据");
			System.out.println("  h(head)：查看队列头的数据");
			System.out.println("n(number)：获取队列长度");
			System.out.print("请选择：");
			key = new Scanner(System.in).next().charAt(0);//接受用户输入的字符
			switch(key) {
			case 's':
				try {
					queue.showQueue();
				} catch (Exception e1) {
					System.err.println("队列为空，无数据！");
				}
				break;
			case 'a':
				System.out.print("请输入一个数据：");
				try {
					queue.addQueue(new Scanner(System.in).nextInt());
				} catch (Exception e1) {
					System.err.println("队列已满！");
				}
				break;
			case 'g':
				try {
					System.out.println("取出的数据是："+queue.getQueue());
				} catch (Exception e) {
					System.err.println("队列为空，无数据！");
				}
				break;
			case 'h':
				try {
					System.out.println("队列头的数据是："+queue.headQueue());
				} catch (Exception e) {
					System.err.println("队列为空，无数据！");
				}
				break;
			case 'n':
				try {
					System.out.println("队列长度为："+queue.getSize());
				} catch (Exception e) {
					System.err.println("队列为空，无数据！");
				}
				break;
			case 'e':
				loop = false;
				break;
			default:
				break;
			}
		}
		System.err.println("程序已退出！");
	}
}

开始测试

我先偷偷的给队列添加三个数据10、20、30。打印队列，结果如下：

1
2
3
4
5
6
7
8
9
10
 
  s(show)：显示队列
  e(exit)：退出程序
   a(add)：添加数据到队列
   g(get)：从队列取出数据
  h(head)：查看队列头的数据
n(number)：获取队列长度
请选择：s
arr[2]=30
arr[1]=20
arr[0]=10

队列容量为3，继续添加数据40，显示队列已满无法继续添加：

1
2
3
4
5
6
7
8
9
 
  s(show)：显示队列
  e(exit)：退出程序
   a(add)：添加数据到队列
   g(get)：从队列取出数据
  h(head)：查看队列头的数据
n(number)：获取队列长度
请选择：a
请输入一个数据：40
队列已满！

现在取出两个数据，再重新添加数据40、50。（注意观察取出的数据是哪个，注意数组下标的变化）

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
 
  s(show)：显示队列
  e(exit)：退出程序
   a(add)：添加数据到队列
   g(get)：从队列取出数据
  h(head)：查看队列头的数据
n(number)：获取队列长度
请选择：s
arr[2]=30
arr[1]=20
arr[0]=10

请选择：g
取出的数据是：10

请选择：g
取出的数据是：20

请选择：a
请输入一个数据：40

请选择：a
请输入一个数据：50

请选择：s
arr[0]=50
arr[3]=40
arr[2]=30

先入先出，执行出队列操作后被取出的是10、20，30没有被取出来。

当队尾指针rear到达数组的最大容量时，如果还有元素入队并且前边有剩余的空间，则队尾指针rear又指向前边，形成一个闭环。所以继续添加数据50时，其在数组中的下标为0。

传送门：查看完整源码！

若图片不能正常显示，请在浏览器中打开

欢迎关注我的其它发布渠道