线性结构-队列

发表于 | 更新于: | 分类于 |
字数统计: 1.4k | 阅读时长 ≈ 6

线性结构-队列

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

遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

使用数组模拟队列示意图

image.png

数组模拟队列

​ 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

​ 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front**及** rear**分别记录队列前后端**的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变

image.png

模拟队列思路：

当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思**路分析**

1)将尾指针往后移：rear+1 , 当front == rear 【空】

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

1
2
3
4
5
6
7
class ArrayQueue(arrMaxSize: Int) { val maxSize: Int = arrMaxSize
  val array = new Array[Int](arrMaxSize)
  var front: Int = -1
  var rear: Int = -1
}
rear 是队列最后[含]
front 是队列最前元素[不含]

Ø出队列操作popQueue

入队列操作addQueue

Ø显示队列的情况showQueue

Ø查看队列头元素headQueue

代码实现数组模拟队列：(初始代码)

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
class Queue{
    //队头
    private int front;
    //队尾
    private int rear;
    //初始化一个6个size的数组
    private int[] arr;
    private int maxSize;

    public Queue(int size){
        if (size<1){
            throw new RuntimeException("数组大小不能小于1");
        }
        maxSize = size;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }

    /**
     * 队尾添加数字,如果rear<size-1就可以继续添加，不然
     * @param num
     */
    public void addQueue(int num){
        if (isFull()){
            System.out.println("队列已满，不能添加");
            return;
        }
        arr[rear+1] = num;
        rear++;
    }

    /**
     * 弹出队头
     * @return
     */
    public int popQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，不能弹出队列");
        }
        int headNum = arr[front+1];
        front++;
        System.out.println("弹出元素: "+headNum);
        return headNum;
    }

    /**
     * 显示队列
     */
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        for (int i = front+1 ; i <= rear; i++) {
            System.out.printf("%d\t",arr[i]);
        }
        System.out.println();
    }

    /**
     * 显示队头
     */
    public void headQueue(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        System.out.println("队头元素:"+arr[front+1]);
    }

    /**
     * 显示队尾
     */
    public void rearQueue(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        System.out.println("队尾元素:"+arr[rear]);
    }

    /**
     * 队列是否满 队尾=maxsize-1
     * @return
     */
    public boolean isFull(){
        if (rear==maxSize-1){
            return true;
        }
        return false;
    }

    /**
     * 队列是否时空的 队尾=队头=-1则为空
     * @return
     */
    public boolean isEmpty(){
        if(front==rear){
            return true;
        }
        return false;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ArrayQueue {
    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.addQueue(1);
        queue.addQueue(2);
        queue.addQueue(3);
        queue.addQueue(4);
        queue.addQueue(5);
        queue.showQueue();
        queue.headQueue();
        queue.rearQueue();
        queue.popQueue();
        queue.showQueue();
        queue.headQueue();
        queue.rearQueue();
        queue.popQueue();
        queue.popQueue();
        queue.popQueue();
        queue.popQueue();
        queue.popQueue();
    }

}

结果为：

1
2
3
4
5
6
7
8
9
10
11
12
1	2	3	4	5	
队头元素:1
队尾元素:5
弹出元素: 1
2	3	4	5	
队头元素:2
队尾元素:5
弹出元素: 2
弹出元素: 3
弹出元素: 4
弹出元素: 5
Exception in thread "main" java.lang.RuntimeException: 队列为空，不能弹出队列

可以看到，基本能完成队列的功能，但是有问题，数组不能复用，空间满了就不能继续添加了，现在进行优化，使用数组模拟环形队列，解决数组不能复用的问题。

数组模拟环形队列

使用数组模拟环形队列思路：

image.png

代码：

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
/**
 * 使用数组实现环形队列 ：用以实现数组复用
 * 这里做了2个调整：front指向第一个元素所在位置  rear指向最后一个元素所在位置
 * 数组中有效个数为：(rear + maxsize - front) % maxsize
 */
class CircleQueue{
    //第一个元素所在位置
    private int front;
    //最后一个元素所在位置
    private int rear;
    //最大容量
    private int maxsize;
    //数组
    private int[] arr;


    /**
     * 初始化环形队列
     * @param size 最大容量
     */
    public CircleQueue(int size){
        front = 0; //第一个位置
        rear = 0; //最开始也为0
        maxsize = size;
        arr = new int[maxsize];
    }

    /**
     * 添加队列元素
     * @param num
     */
    public void addQueue(int num){
        if (isFull()) {
            System.out.println("队列已满，不能添加数据");
            return;
        }
        arr[rear] = num;
        rear = (rear+1)%maxsize;
    }

    /**
     * 取出数据
     * @return
     */
    public int popQueue(){
        if (isEmpty()) {
            throw new RuntimeException("队列为空...");
        }
        int num = arr[front];
        front = (front+1)%maxsize;
        return num;
    }


    /**
     * 显示队列,front是会不断累加的会有溢出，需要取模
     */
    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列为空");
            return;
        }
        for (int i = front; i < front+getSize(); i++) {
            System.out.printf("arr[%d] = %d \t",i%maxsize,arr[i%maxsize]);
        }
    }

    /**
     * 队列是否为空： 判断条件 front  = rear
     * @return
     */
    public boolean isEmpty(){
        return rear == front;
    }

    /**
     * 队列是否满：条件 （rear + 1）%maxsize = front;eg:rear=9,maxsize=10,front=0,数组下标最大就为9，9+1%10 =0 = front
     * @return
     */
    public boolean isFull(){
         return (rear+1)%maxsize==front;
    }

    /**
     * 获取队列有效个数
     * @return
     */
    public int getSize(){
        return (maxsize + rear - front)%maxsize;
    }

}
-------------本文结束感谢您的阅读-------------