Java 队列以及循环队列

导读:本篇文章讲解 Java 队列以及循环队列,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

队列以及循环队列

队列

队列的一个场景

比如我们在食堂打饭就是一个典型的队列使用场景,排在前面的同学先打着饭,然后先离开,后来的同学只能排在队尾,直到前面的同学打完饭才能轮到自己。
在这里插入图片描述

队列介绍

1)队列是一个有序列表,可以用数组或是链表来实现。
2)遵循先入先出的原则。即:先存入队列的数据,要先取出;后存入的数据要后取出。
3)队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

队列图示

队列可以用数组和链表来实现,在这里我们用数组来实现。
1 2 3 4 5 6依次进队,出队的顺序也是1 2 3 4 5 6
在这里插入图片描述

循环队列

循环队列介绍

循环队列其实就是对数组模拟队列的优化(在这里循环队列用数组模拟),充分利用数组,因此将数组看做是一个环形的。(通过取模的方式实现)

循环队列图示

在这里插入图片描述
循环队列只是在逻辑上的循环,在内存中并不是真正的循环(即图示中1 和 6 在内存中并不是连续的)。

循环队列操作

1)定义一个整型变量 head 指向队头。
2)定义一个整型变量 rear指向队头。
3)每添加一个元素, rear往后移动一个位置, rear+ 1;考虑在移动的过程中rear往后+1,但是不能超过队列最大下标,所以需要进行取模操作,rear = (rear + 1) % element.length。
4)每取出一个元素, head 往后移动一个位置, head +1,同样为了防止下标越界也要进行取模操作。
5)每取出一个元素 head 往后移动一个位置,每添加一个元素, rear往后移动一个位置,循环操作,当 head == rear时,队列已满,可是一开始队列为空, head rear也是指向同一个位置的,那么 head rear相等就不能作为判满操作了。在这里为解决这个问题,我们选择浪费一个空间, rear指向的位置不存数据。当( rear+1 ) % element.length == head 时队列已满。

动画演示

在这里插入图片描述

代码如下

public class CircleQueue {
    private int[] element;
    private int head;
    private int rear;
    private int max = 6;

    //构造函数
    public CircleQueue() {
        element = new int[max];
    }

    //判空
    private boolean isEmpty() {
        return head == rear;
    }

    //判满
    private boolean isFull() {
        return (rear + 1) % element.length == head;
    }

    //入队
    public boolean push(T value) {
        if (isFull()) {
            System.out.println("队列已满");
            return false;
        }
        element[rear] = value;
        rear = ++rear % element.length;
        return true;
    }

    //出队
    public boolean pop() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
            return false;
        }

        head = ++head % element.length;
        return true;
    }

    //获得队头元素
    public int peek() {
        if (isEmpty()) {
			throw new EmptyStackException();
        }
        return element[head];
    }
    
    //打印队列
    public int show() {
    	while (!isEmpty()) {
            System.out.print(element[head] + " ");
            head++;
        }
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/95549.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!