数组实现循环队列(Java)

45 阅读 0 评论 30 点赞

我是靠谱客的博主彩色小伙，最近开发中收集的这篇文章主要介绍数组实现循环队列(Java)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

库函数用的多了，一下自己动手写，还真有些手生。脑中有思路，不如笔下出代码，趁着不瞌睡，改改懒病。
队列这东西没什么可说的，线性表的一种，表头为出口，表尾为入口，先进先出。
普通队列当表头数据弹出后，空间无法再次利用，造成空间的浪费，所以就有了循环队列。

循环队列的实现一般有两种方式，链表实现和数组实现。
链表实现就是通过next指针将入口与出口连起来，实现循环。
而数组可以通过对索引进行取余的操作变相实现循环。

代码实现

public class Queue {

    private int[] d = null;// 队列空间
    private int head = 0;// 队列头索引
    private int tail = 0;// 队列尾索引
    private int len = 0;// 队列最大长度

    public Queue(int len) {
        this.len = len;
        d = new int[len];
    }

    //入队函数
    public void push(int x) {
        if (isFull()) {
            System.out.println("队列已满，入队失败");
        } else {
            d[tail] = x;
            tail = (tail + 1) % len;
        }
    }

    //出队函数
    public void pop() {
        if (isEmpty()) {
            System.out.println("队列为空，出对失败");
        } else {
            head = (head + 1) % len;
        }
    }

    //查看队首元素
    public int front() {
        return d[head];
    }

    //查看队尾元素
    public int back() {
        return d[(tail + len - 1) % len];
    }

    //查看队列元素总数
    public int size() {
        return (tail + len - head) % len-1;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        //头尾索引相等表示队列满
        if (tail == head)
            return true;
        return false;
    }

    //判断队列是否为满
    public boolean isFull() {
        //尾索引的下一个为为索引时表示队列满，即将队列容量空出一个作为约定
        if ((tail + 1) % len == head)
            return true;
        return false;
    }

    public static void main(String[] argc)
    {
        Queue q = new Queue(5);
        q.push(1);
        q.push(2);
        q.push(3);
        q.pop();
        System.out.println("首-"+q.front()+" 尾"+q.back()+" 队列元素总数"+q.size());
        q.push(4);
        q.push(5);
        q.push(6);
        q.pop();
        q.pop();
        q.push(7);
        System.out.println("首-"+q.front()+" 尾"+q.back()+" 队列元素总数"+q.size());
    }
}