队列

发表于 | 分类于 |

队列

队列是一个有序列表，可以用数组或是链表来实现；遵循先入先出的原则。

数组模拟队列：

  1. maxSize 为队列的最大容量；2. 队列的输入、输出从前后端处理的，因此需要两个变量front和rear。

存入队列的思路分析：

  1. 将尾指针往后移：rear+1，当front == rear 空

  2. 当尾指针real小于队列的最大值maxSize-1，可将数据存入rear所指的数组元素中，否则无法存入数据 rear == maxSize -1 队列满。

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
package queue;

public class ArrayQueue
{
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;

    public ArrayQueue(int maxSize)
    {
        //队列构造器
        this.maxSize = maxSize;
        arr = new int[this.maxSize];
        this.front = -1;
        this.rear = -1;
    }

    //判断队列满
    public boolean isFull()
    {
        return this.rear == this.maxSize - 1;
    }

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

    //添加数据到队列
    public void addQueue(int num)
    {
        //判断队列是否满？
        if (isFull())
        {
            System.out.println("队列已满！");
            return;
        }
        rear++;
        arr[rear] = num;
    }

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

    //显示队列所有数据
    public void show()
    {
        if (isEmpty())
        {
            throw new RuntimeException("队列为空，不能取数据！");
        }else {
            System.out.print("[\t");
            for (int r:this.arr)
            {
                System.out.printf("%d\t",r);
            }
            System.out.print("]");
            System.out.println();
        }
    }

    //显示队列的头数据
    public void showHeadQueue()
    {
        if (isEmpty())
        {
            throw new RuntimeException("队列为空，不能取数据！");
        }else {
            System.out.println("头数据为：" + arr[front + 1]);
        }
    }


}
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
package queue;

import java.util.Scanner;

public class ArrayQueueTest
{
    public static void main(String[] args)
    {
        ArrayQueue queue1 = new ArrayQueue(3);
        char key = ' ';
        Scanner sc = 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 = sc.next().charAt(0);
            switch (key)
            {
                case 's':
                    try {
                        queue1.show();
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a':
                    System.out.println("请输入一个数字：");
                    int value = sc.nextInt();
                    queue1.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = queue1.getQueue();
                        System.out.println("取出的数据为:" + res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        queue1.showHeadQueue();
                    }catch (Exception e)
                    {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    System.out.println("成功退出！");
                    sc.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}

问题分析优化：目前数组使用一次就不能用了，没有达到复用的效果；将这个数组使用算法，改进成一个环形的数组。

数组模拟环形队列

思路分析：

1.front变量的含义做个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素；front的初始值=0；

2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置。(希望空出一个空间做为约定。)rear初始值=0；

3.当队列满时，条件是：（rear +1）% maxSize = front

4.队列为空的条件是 rear==front

5.当我们这样分析，队列中有效的数据个数：(rear + maxSize -front) % maxSize

6.我们可以在原来的队列上修改得到，一个环形队列。

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
package queue;

public class ArrayQueueCircle
{
    private int[] arr ;
    private int front;
    private int rear;
    private int maxSize;

    public ArrayQueueCircle(int maxSize)
    {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    public boolean isFull()
    {
        return (rear + 1) % maxSize == front;
    }

    public boolean isEmpty()
    {
        return front == rear;
    }

    public void addQueue(int num)
    {
        if (isFull())
        {
            throw new RuntimeException("队列已满！");
        }
        arr[rear] = num;
        rear = (rear + 1) % maxSize;
    }

    public int getQueue()
    {
        if (isEmpty())
        {
            throw new RuntimeException("队列为空！");
        }else {
            int result = arr[front];
            front = (front + 1) % maxSize;
            return result;
        }
    }

    public void showQueue()
    {
        if (isEmpty())
        {
            throw new RuntimeException("队列为空！");
        }else {
            for (int i = front; i < front+((maxSize - front + rear) % maxSize); i++)
            {
                System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
            }
        }
    }

    public void showHeadQueue()
    {
        if (isEmpty())
        {
            throw new RuntimeException("队列为空！");
        }else {
            System.out.println("头元素为：" + arr[front]);
        }
    }

}
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
package queue;

import java.util.Scanner;

public class ArrayQueueTest
{
    public static void main(String[] args)
    {
        ArrayQueueCircle queue1 = new ArrayQueueCircle(4);
        char key = ' ';
        Scanner sc = 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 = sc.next().charAt(0);
            switch (key)
            {
                case 's':
                    try {
                        queue1.showQueue();
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a':
                    System.out.println("请输入一个数字：");
                    int value = sc.nextInt();
                    try {
                        queue1.addQueue(value);
                    }catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try {
                        int res = queue1.getQueue();
                        System.out.println("取出的数据为:" + res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        queue1.showHeadQueue();
                    }catch (Exception e)
                    {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    System.out.println("成功退出！");
                    sc.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}
Donate comment here