1. 队列的介绍

1）队列是一个有序列表，可以用数组或是链表来实现。

2）遵循先进先出的原则。即：**先进队列的数据，要先取出。后进的要后取出。

3）示意图：

2. 数组模拟队列思路

  • 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
  • 因为队列的输出、输入是分别从前后端来处理的，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着队列的输出而改变，而rear则会随着数据的输入而改变。如图所示：

  • 当将数据存入队列时称为”addQueue”, addQueue 的处理需要有两个步骤：

1）将尾指针后移：rear + 1，当 front == rear 【空】

2）若尾指针 rear 小于队列的最大下标 maxSize -1,则将数据存入rear所指的数组元素中，否则无法存入数据。rear == maxSize - 1 【满】

【注意】: 队列的实现最重要的就是知道何时队列为空，何时队列为满。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package com.self.queue;

import java.util.Scanner;

public class ArraySimulateQueue {

    public static void main(String[] args) {
        //测试一把
        //创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while (loop){
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列中取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0);//这句话表示接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数：");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':  //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                     break;
            }
        }
        System.out.println("程序退出~~");
    }
}

//使用数组模拟队列 -- 编写一个ArrayQueue类
class ArrayQueue{

    private int[] arr; //该数组用于存储数据，模拟队列
    private int maxSize; //表示数组的最大容量
    private int front; //队列头
    private int rear; //队列尾

    //1.创建队列的构造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; //指向队列头，分析出front是指向队列头的前一个位置
        rear = -1;  //指向队列尾，指向队列尾的数据（即就是队列最后一个数据）
    }

    //2.判断队列是否满
    public boolean isFull(){

        return rear == maxSize -1;
    }

    //3.判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }

    //4.添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if(isFull()){
            System.out.println("队列满，不能加入数据~");
            return ;
        }
        rear++;//rear后移
        arr[rear] = n;

    }

    //5.获取队列的数据，出队列
    public int getQueue(){
        //判断队列是否空
        if(isEmpty()){
            throw new RuntimeException("队列为空，不能取数据");
        }
        front++;
        return arr[front];
    }

    //6.显示队列的所有数据
    public void showQueue(){
        //遍历
        if(isEmpty()){
            System.out.println("队列是空的，没有数据~");
            return ;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }

    //7.显示队列的头数据，注意并不是取出数据
    public int headQueue(){
        //判断
        if(isEmpty()){
            throw new RuntimeException("队列是空的,没有数据~~");
        }
        return arr[front + 1];
    }
}

4. 代码的简单解析

代码中共有七个方法：

  1. 初始化队列的方法：定义队列最大容量，队头指针，队尾指针的位置。
1
public ArrayQueue(int arrMaxSize){}
  1. 判断队列是否为满：
1
public boolean isFull(){}
  1. 判断队列是否为空:
1
public boolean isEmpty(){}
  1. 添加数据到队列:
1
public void addQueue(int n){}
  1. 从队列中获取数据 , 出队列：
1
public int getQueue(){}
  1. 显示队列的所有数据：
1
public void showQueue(){}
  1. 显示队列的头数据，注意并不是取出数据:
1
public int headQueue(){}

5. 问题分析：

上述方法是可以实现数组模拟队列的效果，但是数组只能使用一次，不能重复的使用，无法实现复用的效果。

之后会出数组模拟环形队列的实现，将会解决这个问题，感兴趣的朋友可以多关注一下…