正文

Java 单向队列及环形队列的实现原理

︶ㄣ米米素材网 メ
米米素材网V管理员 / 阅读
0705

本文主要介绍了Java 单向队列及环形队列的实现原理，文中通过示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

队列的特点

1.可以使用数组和链表两种方式来实现。

2.遵循先入先出(FIFO)的规则，即先进入的数据先出。

3.属于有序列表。

图解实现过程：

Java 单向队列及环形队列的实现原理

​1.定义一个固定长度的数组，长度为maxSize。

​2.设置两个指针first = -1（指向队列第一个数据的前一位，这样保证在添加第一个数据以后头指针为0，和数组的下标一样，且用于操作出队）和last = -1(指向队尾，用于操作入队)。

​3.即first会因为出队操作而增加，last会因为入队操作而增加

代码实现：

?
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
package 队列;
 
public class ArrayQueueTest {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
        arrayQueue.addQueue("琼");
        arrayQueue.addQueue("赟");
        arrayQueue.addQueue("珑");
        arrayQueue.showAllQueueData();
        System.out.println(arrayQueue.getQueue());  
    }
}
class ArrayQueue{
    private int maxSize;//定义队列的最大长度
    private int first ;//指向队列头的前一个位置！！前一个位置！！出队方向
    private int last ;//指向队列尾部!!即最后一个数据！！！入队方向
    private String[] arr; //先建一个空的数组，具体长度未知，需要maxSize来确定。
    
    //构造器初始化队列信息
    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        this.first = -1;
        this.last = -1;
        arr = new String[maxSize];
    }
    
    //判断是否为空
    public boolean isEmpty(){
        if (first == last) {
            System.out.println("队列为空~~");
            return true;
        }else {
            System.out.println("队列不为空~~");
            return false;
        }
    }
    
    //判断队列是否满
    public boolean isFull(){
        if (last == maxSize-1) {
            System.out.println("队列已满~~");
            return true;
        }else {
            System.out.println("队列未满~~");
            return false;
        }
    }
    
    //入队
    public void addQueue(String data){
        if (last == maxSize-1){
            System.out.println("队列已满，不能再添加！！");
            return;
        }else {
            last++; //添加数据只和末尾下标有关
            arr[last] = data;
            return;
        }
    }
    
    //出队
    public String getQueue(){
        if (isEmpty()) {
            //因为getQueue方法是int型，需要返回数据，如果无数据，也需要返回
            //如果返回-1或者其他数据，会让人误解获取到的数就是-1或者其他
            //所以用抛出异常来处理
            throw new RuntimeException("队列为空，无数据~~");
        }
        else {
            first++;
            return arr[first];
        }
    }
    
    //遍历队列所有信息
    public void showAllQueueData(){
        if (first == last){
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr["+i+"]"+"="+arr[i]);
        }
    }
    
    //获取队列头数据
    public String headQueueData(){
        if (isEmpty()){
            throw new RuntimeException("无数据~~~");
        }
        return arr[++first];
    }
}

队列缺点：

由于出队操作，使得first指针上移变大，导致数组前面空出来的位置就不能再继续添加数据，即不能再被重复使用，这样一个队列只能使用一次，内存效率太低，所以需要使用环形队列来优化解决。

优化解决——环形队列实现思路

1.first指针初始默认设置为0，指向队列头部，则arr[first] 就是第一个数据。

2.last指针初始默认也为0，但是会随着增加数据而后移。

3.队列满的条件：

(last + 1) % maxSize == first

​last+1是为了让指针后移，而且如果不设置为 last+1 那么一开始的时候last为0 ， last % maxSize == 0，且first也为0，还没加数据就满了。

4.队列为空的条件：

first == last

5.由于判断是否满的时候： last+1 ，导致实际上可以装的数据比数组长度少 1

环形队列各步骤及各方法实现讲解

1.队列初始化 ：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class CircleArryQueue{
    private int maxSize ; //数组长度，即队列最大容量
    private int first;    //头指针，控制出队操作
    private int last;     //尾指针，控制入队操作
    private int[] arr;    //数组类型，可以换其他的。
 
    //构造器初始化信息
    public CircleArryQueue(int maxSize){
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        this.first = 0;     //这两个可以不加，不叫也是默认为0
        this.last = 0;
    }
}

2.判断队列是否为空：

?
1
2
3
4
public boolean isEmpty(){
       //头指针和尾指针一样 则说明为空
       return last == first;
   }

3.判断队列是否满：

?
1
2
3
4
5
6
7
/*
*这里的 last+1 主要是为了让指针后移，特别是在队列尾部添加数据的时候，本来用last也可以判断，但
*是一开始还没加数据的时候，如果直接用last % maxSize == first，结果是true，所以为了解决指针后*移和判断是否满，用来last+1。其次，因为last+1可能会导致数组指针越界，所以用取模来控制它的范  * 围，同时保证他会在一个固定的范围循环变换，也利于环形队列的实现。
*/
public boolean isFull(){
    return (last + 1) % maxSize == first;
}

4.添加数据到队列尾部：入队

?
1
2
3
4
5
6
7
8
9
10
public void pushData(int data){
    //先判断是否满了
    if(isFull()){
        System.out.println("队列已经满啦~~");
        return;
    }
    arr[last] = data;
    //last+1是为了后移，取模是为了避免指针越界，同时可以让指针循环
    last = (last + 1) % maxSize;
}

5.取出队首数据：出队

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int popData(){
        if (isEmpty()) {
            //抛异常就可以不用返回数据了
            new RuntimeException("队列为空，没有获取到数据~~");
        }
    
        //要先把first对应的数组数据保存——>first后移——>返回数据
        int value = arr[first];
        //first+1的操作和last+1是一样的，取模也是
        first = (first+1) % maxSize;
        System.out.println(value);
        return value;
        //如果不保存first指针 那么返回的数据就不对了
        //如果直接返回数据，那first指针还没后移 也不对，所以需要使用第三方变量
    }

6.展示队列中所有数据：

?
1
2
3
4
5
6
7
8
9
10
public void showAllData(){
        if (isEmpty()) {
            System.out.println("队列为空，没有数据~~");
            return;
        }
        //此处i不为0，是因为有可能之前有过popData()操作，使得firs不为0，所以最好使用
        //first给i动态赋值，
        for (int i = first; i < first+size() ; i++) {
            System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]);
        }

7.获取队列中数据的总个数：

?
1
2
3
4
public int dataNum(){
    //韩顺平老师的教程上是这样写，但是我理解不了..........。
    return (last+maxSize-first) % maxSize;  
}

8.查看队首数据但不弹出：

?
1
2
3
public void seeFirstData(){
    return arr[first];
}

全部代码整合：

?
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
package 练习;
 
import java.util.Scanner;
 
public class CircleArryQueue {
    public static void main(String[] args){
        CircleQueue circleQueue = new CircleQueue(4);
        System.out.println("--------测试环形队列--------");
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
 
        boolean flag = true;
        while (flag){
            System.out.println("s(showAllData):查看队列数据");
            System.out.println("p(pushData):队尾添加数据");
            System.out.println("g(popData):弹出队头数据");
            System.out.println("h(seefirstData)：获取队头数据");
            System.out.println("e(exit):退出程序");
            key = scanner.next().charAt(0);
 
            switch (key){
                case 's':
                    circleQueue.showAllData();
                    break;
                case 'p':
                    System.out.println("输入一个数据：");
                    int obj = scanner.nextInt();
                    circleQueue.pushData(obj);
                    break;
                case 'g':
                    circleQueue.popData();
                    break;
                case 'h':
                    circleQueue.seeFirstData();
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
 
        }
 
        System.out.println("程序结束~~~");
 
    }
 
}
 
class CircleQueue {
    private int maxSize ; //数组长度，即队列最大容量
    private int first;    //头指针，控制出队操作
    private int last;     //尾指针，控制入队操作
    private int[] arr;    //数组类型，可以换其他的。
 
    //构造器初始化信息
    public CircleQueue(int maxSize){
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        this.first = 0;     //这两个可以不加，不叫也是默认为0
        this.last = 0;
    }
 
    public boolean isEmpty(){
        //头指针和尾指针一样 则说明为空
        return last == first;
    }
 
/*
*这里的 last+1 主要是为了让指针后移，特别是在队列尾部添加数据的时候，本来用last也可以判断但
*是一开始还没加数据的时候，如果直接用last % maxSize == first，结果是true，所以为了解决指针
*后移和判断是否满，用来last+1。其次，因为last+1可能会导致数组指针越界，所以用取模来控制它
*的范围，同时保证他会在一个固定的范围循环变换，也利于环形队列的实现。
*/
    public boolean isFull(){
        return (last + 1) % maxSize == first;
    }
 
    public void pushData(int data){
        //先判断是否满了
        if(isFull()){
            System.out.println("队列已经满啦~~");
            return;
        }
        arr[last] = data;
        //last+1是为了后移，取模是为了避免指针越界，同时可以让指针循环
        last = (last + 1) % maxSize;
    }
 
    public int popData(){
        if (isEmpty()) {
            //抛异常就可以不用返回数据了
            throw new RuntimeException("队列为空，没有获取到数据~~");
        }
 
        //要先把first对应的数组数据保存——>first后移——>返回数据
        int value = arr[first];
        //first+1的操作和last+1是一样的，取模也是
        first = (first+1) % maxSize;
        System.out.println(value);
        return value;
        //如果不保存first指针 那么返回的数据就不对了
        //如果直接返回数据，那first指针还没后移 也不对，所以需要使用第三方变量
    }
    
    //查看所有数据
    public void showAllData(){
        if (isEmpty()) {
            System.out.println("队列为空，没有数据~~");
        }
        //此处i不为0，是因为有可能之前有过popData()操作，使得firs不为0，所以最好使用
        //first给i动态赋值，
        for (int i = first; i < first+dataNum() ; i++) {
            System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]);
        }
    }
    //查看有效数据个数
    public int dataNum(){
        //韩顺平老师的教程上是这样写，但是我理解不了..........。
        return (last+maxSize-first) % maxSize;
    }
    //查看队列第一个数据
    public int seeFirstData(){   
        System.out.println(arr[first]);
        return arr[first];
        
    }
}

最后：

部分内容参考自B站韩顺平老师java数据结构课程

到此这篇关于Java 单向队列及环形队列的实现原理的文章就介绍到这了,更多相关Java 单向队列及环形队列内容请搜索米米素材网以前的文章或继续浏览下面的相关文章希望大家以后多多支持米米素材网！

原文链接：https://www.cnblogs.com/coding-996/p/12246672.html