0%

Java算法与数据结构之队列

发表于 更新于 分类于
本文字数： 8.6k 阅读时长 ≈ 8 分钟

队列

队列是一种特殊的线性结构，它只允许在队列的首部（head/front）进行删除操作，这称为“出队”，而在队列的尾部（tail/rear）进行插入操作，这称为“入队”。当队列中没有元素时（即head == tail），称为空队列。比如买票，每个排队买票的窗口就是一个队列。在这个队列当中，新来的人总是站在队列的最后面，来得越早的人越靠前，也就是越早能买到票，我们称为“先进先出”（First In First Out, FIFO）原则。🚘

队列的特性

  • 队列是一个有序列表，可以用数组或是链表来实现
  • 在队首删除元素，在队尾插入元素
  • “先进先出”（FIFO）原则

队列的实现

用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

数组模拟队列

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

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

  • 数组模拟队列的数组使用一次便不可使用，即使数组还有空闲空间，也无法往队列里添加，这是就需要进行数据的搬移，复用性不好，可以替换为环形队列。

代码实现

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
import java.util.Scanner;
public class ArrayQueueTest {
    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.println("取出的数据是" + res);
                    }catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.headQueue();
                        System.out.println("队列头的数据是" + 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 maxSize; //表示数组的最大容量
    private int front; //队列头
    private int rear; // 队列尾
    private int[] arr; // 该数据用于存放数据，模拟队列

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

    }

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

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

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

    //获取队列的数据，出队列
    public int getQueue() {
        //判断队列是否空
        if (isEmpty()) {
            //通过抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        front++; //front 后移
        return arr[front];
    }

    //显示队列的所有数据
    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]);
        }
    }
    //显示队列的头数据，不是取出数据
    public int headQueue() {
        //判断
        if (isEmpty()) {
            throw new RuntimeException("队列空");
        }
        return arr[front + 1];
    }
 }

链表模拟队列

基于链表的实现，需要head 和 tail 两个指针。分别指向链表的第一个和最后一个结点。

入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。

图示如下：

代码如下：

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
129
130
131
132
133
import java.util.Scanner;
public class LinkedListQueueDemo {
    public static void main(String[] args) {
        //测试
        //创建一个链表
        LinkedListQueue queue = new LinkedListQueue();//设置的是有效数据
        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 {
                        Object res = queue.getQueue();
                        System.out.println("取出的数据是" + res);
                    }catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        Object res = queue.headQueue();
                        System.out.println("队列头的数据是" + res);
                    }catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出！");
    }
}

//使用链表模拟队列-编写一个LinkedListQueue类
class LinkedListQueue {

    private Node front; //链表头
    private Node rear; //链表尾
    private int size; //队列长度

    //创建队列的构造器
    public LinkedListQueue() {
        size = 0;
        front = rear = null;
    }
    //创建一个Node节点类
    private static class Node {
        private Node next; //每一个节点
        private Object data;//每个节点的数据
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //添加数据到队列,将新节点添加到表尾，然后把新节点设置成新的表尾
    public void addQueue(Object data) {
        if (isEmpty()) {
            Node newNode = new Node(data, null);
            front = newNode;
            rear = newNode;
        }else {
            rear.next = new Node(data, null);
            rear = rear.next;
        }
        size++; //队列长度加1
    }

    //获取队列的数据，出队列
    public Object getQueue() {
        if (isEmpty()) {
            //通过抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        //
        Object value = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return value;
    }

    //显示队列的所有数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空");
            return;
        }
        //遍历链表所有数据
        Node node = front;
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
        System.out.println();
    }

    //显示队列的头数据，不是取出数据
    public Object headQueue() {
        //判断
        if (isEmpty()) {
            throw new RuntimeException("队列空");
        }
        return front.data;
    }
}

数组模拟环形队列

思路如下:

  • front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
    front 的初始值 = 0
  • rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
    rear 的初始值 = 0
  • 当队列满时，条件是 (rear + 1) % maxSize == front 【满】
  • 对队列为空的条件， rear == front 空
  • 当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
  • 我们就可以在原来的队列上修改得到，一个环形队列

代码实现

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
129
130
131
132
133
134
135
136
137
138
139
140
141
import java.util.Scanner;
public class CircleArrayDemo {
    public static void main(String[] args) {

        //测试
        //创建一个环形队列
        CircleQueue queue = new CircleQueue(4);//设置的是有效数据
        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.println("取出的数据是" + res);
                    }catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.headQueue();
                        System.out.println("队列头的数据是" + res);
                    }catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出！");

    }
}

//使用数组模拟队列-编写一个CircleQueue类
class CircleQueue {
    private int maxSize; //表示数组的最大容量
    //front 变量的含义做一个调整： front 就指向队列的第一个元素, 
    //也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
    private int front; //队列头
    //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 
    //因为希望空出一个空间做为约定.rear 的初始值 = 0
    private int rear; // 队列尾
    private int[] arr; // 该数据用于存放数据，模拟队列

    //创建队列的构造器
    public CircleQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
//        front = 0;
//        rear = 0;

    }

    //判断队列是否满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

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

    //添加数据到队列
    public void addQueue(int n) {
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列满，不能加入数据");
            return;
        }
        //直接将数据加入
        arr[rear] = n;
        //将rear后移，这里必须考虑取模，也就是循环
        rear = (rear + 1) % maxSize;
    }

    //获取队列的数据，出队列
    public int getQueue() {
        //判断队列是否空
        if (isEmpty()) {
            //通过抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        //这里需要分析出front是指向队列的第一个元素
        //1.先把front对应的值保留到一个临时变量
        //2.将front后移, 考虑取模
        //3.将临时保存的变量返回
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    //显示队列的所有数据
    public void showQueue() {
        //遍历数组
        if (isEmpty()) {
            System.out.println("队列空");
            return;
        }
        //思路：从front开始遍历，遍历多少个元素
        //对i进行取模，循环
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n",i % maxSize, arr[i % maxSize]);
        }
    }

    //求出当前队列的有效数据的个数
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
    //显示队列的头数据，不是取出数据
    public int headQueue() {
        //判断
        if (isEmpty()) {
            throw new RuntimeException("队列空");
        }
        return arr[front];
    }
}

😎😎 加油！

北以晨光 wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！
------ 本文结束感谢您的阅读 ------
相关文章