Java 循环队列的实现

谁践踏了优雅 2021-06-11 15:14 416阅读 0赞

## 队列概念 ##

队列（Queue）是限定只能在一端插入、另一端删除的线性表。允许删除的一端叫做队头（front),允许插入的一端叫做队尾（rear），没有元素的队列称为“空队列”。

队列具有先进先出（FIFO）的特性。

### 　　普通顺序队列存在的问题 ###

在普通顺序队列中,入队的操作就是先将尾指针rear右移一个单位，然后将元素值赋值给rear单位。出队时，则是头指针front后移一个单位。像这样进行了一定数量的入队和出队操作后，可能会出现这样的情况：

尾指针rear已指到数组的最后有一个元素，即rear==MaxLen-1，此时若再数组的前面部分可能还有很多闲置空间，即这种溢出并非是真的没有可用的存储空间，故称这种溢出现象为“假溢出”。显然，必须要解决这一块假溢出的问题，否则顺序队列就没有太多使用价值。

### 　　循环队列 ###

循环队列的存储结构，头、尾指针都和普通顺序队列相同。不同的只是将队列视为“环状结构”，即data\[0\]为紧接着data\[MaxLen-1\]的单元，为相邻的元素，首位成为一个环。结构如下：![1125876-20170514162342785-997558567.jpg][]（来自：百科）

# #

## 代码实现 ##

全局变量：定义队列长度

static int MaxLen;

循环队列基本数据结构的实现：

![复制代码][copycode.gif]

static class myQueue{
                int front;
                int rear;
                int queueList[];
                public myQueue() {
                    // TODO Auto-generated constructor stub    
                    queueList=new int[MaxLen];
                    front=0;
                    rear=0;
                }
    }

![复制代码][copycode.gif]

判空函数

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

判满函数

![复制代码][copycode.gif]

public boolean isFull(){
                    if(((rear+1)%MaxLen)==front){
                        return true;
                    }
                    else{
                        return false;
                    }
                }

![复制代码][copycode.gif]

取队头元素

![复制代码][copycode.gif]

public void queueFront(int getFront){
                    if(isEmpty()==false){
                        getFront=queueList[(front+1)%MaxLen];
                    }
                    else {
                        System.out.println("ERROR:Queue is Empty");
                        return;
                    }
                }

![复制代码][copycode.gif]

入队

![复制代码][copycode.gif]

public void enQueue(int enData) {
                    if(isFull()==false){
                        rear=(rear+1)%MaxLen;
                        this.queueList[rear]=enData;
                    }
                    else{
                        System.out.println("ERROR:Queue is Full");
                        return;
                    }
                    
                }

![复制代码][copycode.gif]

出队

![复制代码][copycode.gif]

public void outQueue() {
                    if(isEmpty()==false){
                        front=(front+1)%MaxLen;
                    }
                    else {
                        System.out.println("ERROR:Queue is Empty");
                        return;
                    }
                    
                }

![复制代码][copycode.gif]

作者：[Rekent][]   
出处：[http://www.cnblogs.com/rekent/][Rekent]

[1125876-20170514162342785-997558567.jpg]: /images/20210527/0335ef730182491aa3ae657a09e55671.png
[copycode.gif]: /images/20210527/f3b28037638244e29d95816e22ada98f.png
[Rekent]: http://www.cnblogs.com/rekent/