java实现循环队列—基于顺序存储结构

首先让我们先简单地来认识一下队列：

队列介绍

队列一种受限线性表，只允许在一段进行插入，在另一端进行删除。它还有个好搭档叫“栈”，经常被一起提起，栈是一种先进后出的数据结构，而队列则是一种先进先出的数据结构，在英文中被称作First in,First out。故队列又经常被叫作FIFO表。

队列分类

顺序队列、循环队列。

队列的实现原理

先看顺序队列，一个头指针，一个尾指针。进队尾指针后移，出队时头指针后移。并且出队之后，所有元素可以前移（也可以不前移）。

队列实现原理

元素不前移机制的操作示意图：

队列操作示意图

假溢出现象：

当我们采用顺序队列的时候，如果采用“元素不前移”的机制，当尾指针到达上边界时，就会认为队列已满，但此时低端空间由于出队可能还有空闲空间。如图所示：

假溢出现象

假溢出的解决办法：

这便是循环队列。即当尾指针到达上边界时，可以回到下边界的位置，从而继续进行入队操作。

循环队列解决假溢出

队列的判空、判满

那么问题来了，我们使用了循环队列之后，又该如何判断队列是空，还是满呢？使用以下的方法：
①判空：front=rear
②问题：想想，出队时头指针后移，遇尾指针相遇时队空。入队时，尾指针后移，与头指针相遇时队满，也是front=read呀！但这个公式判空已经用了，那么判满就不能使用front=rear了。
③判满：使用公式：(rear+1)%size=front。判满时，队列实际上并真正的满，我们实际上是浪费了一个数组空间。还差一个满时就认为已经它满了。如图（已满队列）：

满队列示意图

java代码实现

public class CirQueue {
    private Object[] objs;
    private int front = 0;// 头指针
    private int rear = 0;// 尾指针
    private int size;// 空间大小
    private int length = 0;

    // 初始化
    public CirQueue(int size) {
        this.size = size;
        objs = new Object[size];
    }

    // 计算长度（即队列元素个数）
    public int getLength() {
        return length;
    }

    // 判空
    public boolean isEmpty() {
        if (front == rear) {
            return true;
        }
        return false;
    }

    // 判满
    public boolean isFull() {
        if ((rear + 1) % size == front) {
            return true;
        }
        return false;
    }

    // 入队
    public boolean enQueue(Object n) {
        if (isFull()) {
            return false;
        }
        rear = (rear + 1) % size;// 体现循环
        objs[rear] = n;
        length++;
        return true;
    }

    // 出队
    public Object deQueue() {
        Object n = null;
        if (!isEmpty()) {
            front = (front + 1) % size;// 体现循环
            n = objs[front];
            objs[front] = null;
            length--;
        }
        return n;
    }

    // 输出
    public void show() {
        for (Object obj : objs) {
            if (obj == null) {
                System.out.print("空   ");
            } else {
                System.out.print(obj.toString() + "  ");
            }
        }
        System.out.println("");
    }
}

//java入口
public class Main {
    public static void main(String[]args){
        CirQueue queue=new CirQueue(5);
        queue.show();
        System.out.println("是否为空:"+queue.isEmpty());
        System.out.println("初始长度:"+queue.getLength());
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.show();
        System.out.println("是否已满:"+queue.isFull());
        System.out.println("现有长度:"+queue.getLength());
        queue.enQueue(6);
        queue.deQueue();
        queue.deQueue();
        queue.enQueue(5);
        queue.enQueue(6);
        queue.show();
        System.out.println("是否已满:"+queue.isFull());
        System.out.println("现有长度:"+queue.getLength());
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        queue.show();
        System.out.println("是否为空:"+queue.isEmpty());
        System.out.println("现有长度:"+queue.getLength());
    }
}

运行结果：

运行结果

最后编辑于：2017.12.11 13:43:31