数组实现循环队列(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());
    }
}

** _ 运行结果 _ **

首-2 尾3 队列元素总数2
队列已满,入队失败
首-4 尾7 队列元素总数3


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!