Java 循环队列/环形队列的实现流程

Java 循环队列/环形队列的实现流程

之前，我们使用链表实现了基础队列，链接放在这里可以去康康哟

java栈和基础队列的实现详解

之所以没有选择数组来实现，是因为每有一个元素出队，数组中所有剩下的元素都需要向前移动一次，因此没有链表高效。

此时，我们就引出了循环队列的概念。

循环队列，又称环形队列，逻辑上是一个环，物理上依然是线性表。

head-指向队列的第一个元素

tail-指向队列最后一个元素的下一个位置

当tail走到数组末尾时，下一步再次返回数组头部（从0开始）

出队之后的元素就访问不到了，此时逻辑上已经将它删除了，tail向后走到该位置时覆盖它即可。此时就解决了数组队列需要一直搬运元素的问题。

了解循环队列的概念之后，我们就能明白它的几个基础知识:

当head == tail 时，表示队列为空

根据上面 head 和 tail 的定义，队列已满时，tail 指向最后一个元素的下一个位置，也就是head ，此时我们就无法区分环形队列到底是已满还是为空。所以我们在环形队列的数组中浪费一个空间，在区分数组是否已满，如下图，就是一个已满的队列

那么如何移动 tail 指针使他返回数组头部呢？我们运用取模操作：

tail = ( tail + 1 ) % 数组.length;

根据上式我们就能判断队列是否已满的方法：

( tail + 1 ) % 数组.length == head;

此时 head 和 tail 引用向后移动时，不能简单的 +1，要 ++ 之后对数组长度取模，这样就可以返回数组头部继续向后移动:

head = ( head +1 ) % 数组.EtDpoIobxlength;

tail = ( tail +1 ) % 数组.length;

那么如何获取当前队列最后一个元素的索引呢?

图①中最后一个元素的索引就是 tail -1

图②的tail恰好在数组第一个位置，这时最后一个元素下标就是 数组.length -1

综上：数组最后一个元素的索引lastIndex

lastIndex = tail == 0 ? 数组.length -1 : tail -1;

代码实现：

public interface Queue {

void offer(E val);//入队

E poll();//出队，返回出队的值

E peek();//返回队首元素

boolean isEmpty();//判断是否为空

}

import java.util.NoSuchElementException;

//基于整型的循环队列

public class LoopQueue implements Queue{

private Integer[] data;

private int head;//队首元素

private int tail;//队尾元素的下一个位置

private int size;//当前元素个数

public LoopQueue(int n){

//n为希望保存的元素个数

//在循环队列中要浪费一个元素空间，来判断是否已满，所以 +1

data = new Integer[n + 1];

}

@Override

//添加元素

public voihttp://d offer(Integer val) {

if(isFull()){

throw new ArrayIndexOutOfBoundsException("queue is full, cannot offer new val");

}

data[tail] = val;

//tail向后移

tail = (tail + 1) % data.length;

size++;

}

@Override

//出队

public Integer poll() {

if (isEmpty()){

throw new NoSuchElementException("queues empty!cannot poll");

}

Integer val = data[head];

//head向后移动

head = (head + 1) % data.length;

size--;

return val;

}

@Override

public Integer peek() {

if (isEmpty()){

throw new NoSuchElementException("queues empty!cannot poll");

}

return data[head];

}

@Override

//判断是否为空

public boolean isEmpty() {

return tail == head;

}

public String toString(){

StringBuilder sb = new StringBuilder();

sb.append("front[");

//取得最后一个元素的下标

int lastIndex = tail == 0 ? data.length-1 : tail-1;

for (int i = head; i != tail; ) {

sb.append(data[i]);

if (i != lastIndex){

sb.append(",");

}

i = (i+1) % data.length;

}

sb.append("]tail");

return sb.toString();

}

//判断队列是否已满

public boolean isFull(){

return (tail + 1) % data.length == head;

}

}

//代码测试

public class LoopQueueTest {

public static void main(String[] args) {

Queue loopQueue = new LoopQueue(5);

for (int i = 0; i < 5; i++) {

loopQueue.offer(i+1);

}

System.out.println(loopQueue);

// loopQueue.offer(1);

System.out.println(loopQueue.poll());

System.out.println(loopQueue);

}

}

运行结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。