1. 首页
  2. 文章中心
  3. Java数据结构

Java数据结构之普通队列和循环队列队列

84 阅读 0 评论
我是靠谱客的博主 英俊帆布鞋，这篇文章主要介绍Java数据结构之普通队列和循环队列队列，现在分享给大家，希望可以做个参考。

队列

  队列介绍

  图解队列

  数组实现队列

  循环队列

  图解循环队列

  数组实现循环队列

队列

队列介绍:

    队列是一种线性数据结构，可以用数组或者链表来实现。队列遵循先进先出的原则，即先存入的数据要先取出，后存入的数据要后取出。
    例如，我们在排队买东西时，先排队的人会先买完东西离队，而后排队的人会后离队，这就是一种队列。

图解队列:

请添加图片描述
    Queue即为一个队列，MaxSize为队列的最大容量。我们用两个指针来指向队列的头和尾，rear指针指向队尾，front指针指向队首，将两指针均初始化为-1，当我们向队列里添加元素时，每添加一个元素，rear指针加一，front不变；每次取出队列元素时，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
//Queue类用于实现队列及方法
class Queue{
    int[] array;
    int maxSize;//队列最大容量
    int front;//队首
    int rear;//队尾
    
    //创建构造器
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        array = new int[maxSize];
        front = -1;//front指向队列第一个元素的前一个位置
        rear = -1;//rear指向队列的最后一个元素
    }
   
    //判断队列是否已满
    public boolean isFull(){
        return rear==maxSize-1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }
    //向队列中添加元素
    public void add(int val){
        if(isFull()){
            System.out.println("队列已满，添加失败!");
            return;
        }
        ++rear;
        array[rear] = val;
        System.out.println("添加成功!");
    }
    //删除队列元素
    public boolean delete(){
        if(isEmpty()){
            throw new RuntimeException("队列为空!");
        }
        ++front;
        return true;
    }
    //打印队列所有元素
    public void show(){
        if(isEmpty()){
            System.out.println("队列为空!");
            return;
        }
        for(int i = front+1;i<=rear;++i){
            System.out.println(array[i]);
        }
    }
    //打印队列第一个元素
    public void head(){
        if(isEmpty()){//当队列为空时抛出异常
            throw new RuntimeException("队列为空!");
        }
        System.out.println("当前第一个元素为"+array[front+1]);
    }
}
public class Test1 {
    public static void main(String[] args) {
        Queue queue = new Queue(3);
        Scanner scanner = new Scanner(System.in);
        while (true){
            System.out.println("1. 添加元素");
            System.out.println("2. 删除元素");
            System.out.println("3. 打印队列");
            System.out.println("4. 显示队首元素");
            System.out.println("0. 退出系统");
            int key = scanner.nextInt();
            switch (key){
                case 1:
                    System.out.println("请输入需要添加的数字:");
                    queue.add(scanner.nextInt());
                    break;
                case 2:
                    if(queue.delete()){
                        System.out.println("删除成功!");
                    }
                    break;
                case 3:
                    queue.show();
                    break;
                case 4:
                    queue.head();
                    break;
                default:
                    System.exit(0);
            }
        }
    }
}

    在执行这个代码时，我们不难发现，这个代码存在着一定问题:

    最开始时，每添加一次元素rear指针自增一次，当rear = maxSize-1时队列为满

    此时我们再进行删除元素操作时，每删除一个元素，front指针自增一次，当front自增到与rear相等时队列即为空.

    当我们删除元素直至队列为空时，rear = front，但是，此时rear仍等于maxSize-1，也就是说这个队列同时满足了队列为空和队列为满的条件

可以看出，数组模拟队列存在一定的弊端，因此，我们引出了循环队列:

循环队列

    循环队列是将原有队列进行改动，使得队列的第一个元素从逻辑上成为最后一个元素的下一位，也就是将队列成环，需要注意的是，这里的成环指的是逻辑层面，在物理层面上这个队列不是循环的。

在实现代码之前，我们需要将队列的首、尾指针进行改动:

    1. 队首指针front不再指向队列第一个元素的前一位，而是直接指向循环队列的第一个元素
    2. 队尾指针rear不再指向队列的最后一个元素，而是指向循环队列最后一个元素的下一位
    3. front和rear指针的初始值不再为-1，而是0

为什么要进行这样的改动呢？

    首先，我们来图解循环队列:

图解循环队列

请添加图片描述
创建循环队列时队列为空，此时rear == front
请添加图片描述
每次插入元素时，rear = (rear+1)%maxSize

请添加图片描述
每次删除元素时，front = (front+1)%maxSize

请添加图片描述
当队列为空时，rear == front

请添加图片描述
当队列为满时，满足rear == front

对于循环队列，似乎队列为空和队列为满的条件均为front == rear，那么，我们该如何判断队列为空和为满呢？

方法1：
用一个计数变量来记载队列中的元素个数
初始化队列时c=0;
当入队时，计数变量＋1（ c=c+1 ）
当出队时，计数变量－1 （c=c-1）
当计数变量＝maxsize时，队满
当计数变量＝0时，队空

方法2：
牺牲一个元素空间，来区别队空或队满。
入队前，先判rear+1是否等于front，
若是则为队满。
而当front=rear时，队列为空。

    我们采用第二种方法，对于一个有效长度为maxSize循环队列，我们规定它能存储的元素个数只有maxSize-1个，也就是说当循环队列为满时队列里依然会有一个位置为空，为了方便起见，我们让rear指针始终指向空位置，也就是队列最后一个元素的下一位。

    我们已经知道，对于普通队列，队列为满的条件为rear = maxSize-1，而判断循环队列已满的条件是什么呢？

    我们将循环队列想象成一个环，队首指针指向第一个元素，队尾指针指向最后一个元素的下一个位置，最开始时，队首和队尾指针均为0，每添加一个元素，队尾指针rear自增一次，当rear和front再次相遇时，代表循环队列已经满了，但是，我们在上面提到过，循环队列中至少要有一个位置为空，也就是rear指针走完一圈后最多只能走到front的前一位，此时循环队列为满.

  判断循环队列为空的方式上面方法二已经提到过了，也就是当rear==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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Queue{
    private int[] array;
    private int maxSize;
    private int rear;//指向队列最后一个元素的下一个位置
    private int front;//指向队列的第一个元素
    //创建构造器
    public Queue(int maxSize){
        this.maxSize = maxSize;
        array = new int[maxSize];
    }
    //判断队列是否满
    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }
    //向队列中添加元素
    public boolean add(int val){
        if(isFull()){
            throw new RuntimeException("队列已满，无法添加!");
        }
        array[rear++] = val;
        return true;
    }
    //删除队列元素
    public int delete(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法删除!");
        }
        int val = array[front];
        front = (front+1)%maxSize;
        return val;
    }
    //打印队列所有元素
    public void show(){
        if(isEmpty()){
            System.out.println("队列为空!");
            return;
        }
        for(int i=front;i<=front+(maxSize+rear-front)%maxSize;++i){
            System.out.print(array[i%maxSize]+" ");
        }
    }
    //打印队列第一个元素
    public void head(){
        if(isEmpty()){
            System.out.println("队列为空!");
            return;
        }
        System.out.println("队首为"+array[front]);
    }
}
public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Queue queue = new Queue(4);
        while (true){
            System.out.println("1. 添加元素");
            System.out.println("2. 删除元素");
            System.out.println("3. 打印队列");
            System.out.println("4. 显示队首");
            System.out.println("0. 退出系统");
            switch (scanner.nextInt()){
                case 1:
                    System.out.println("请输入要添加的数:");
                    if(queue.add(scanner.nextInt())){
                        System.out.println("添加成功!");
                    }
                    break;
                case 2:
                    System.out.println("删除成功，删除的元素值为"+queue.delete());
                    break;
                case 3:
                    queue.show();
                    break;
                case 4:
                    queue.head();
                    break;
                default:
                    System.exit(0);
            }
        }
    }
}

The end

最后

以上就是英俊帆布鞋最近收集整理的关于Java数据结构之普通队列和循环队列队列的全部内容，更多相关Java数据结构之普通队列和循环队列队列内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(56)

相关文章

队列，双端队列，循环队列，循环双端队列的含义与关系
队列，双端队列，循环队列，循环双端队列的含义与关系
循环队列与数组
循环队列与数组
C++数据结构：普通队列与循环队列
C++数据结构：普通队列与循环队列
数据结构之.队列，循环队列，链式队列（一）
数据结构之.队列，循环队列，链式队列（一）
Java数据结构之普通队列和循环队列队列
Java数据结构之普通队列和循环队列队列
数据结构----------队列和循环队列
数据结构----------队列和循环队列
解决把数组中的0移到数组末尾，其他元素相对位置不变
解决把数组中的0移到数组末尾，其他元素相对位置不变
日报表第7天
日报表第7天

评论列表共有 0 条评论

立即
投稿
返回
顶部