java实现循环队列

一、队列

队列(queue),是一种线性表,它的特性是先进先出,插入在一端,删除在另一端。就像排队一样,刚来的人入队(enqueue)要排在队尾(rear),每次出队(dequeue)的都是队首(front)的人。

二、顺序队列

先来看看顺序队列

1、假设现在顺序队列分配了六个空间,初始时Q.front = Q.rear = 0,队列为空;

2、a1入队,Q.front = 0, Q.rear  = 1;

3、a2入队,Q.front = 0,Q.rear = 2;

4、a3、a4、a5依次入队,Q.front = 0,Q.rear = 5;

5、a1出队,Q.front = 1,Q.rear = 5;

6、a3出队,Q.front = 2,Q.rear  = 5;

7、若此时a6再入队,那么rear就会超过数组下标范围,造成越界

但此时数组中明明还有两个空间未使用,却白白地浪费掉了,这种现象就叫做“假溢出”。那要怎样解决这个问题?能不能继续使用前面两个空间?现在就轮到循环队列出场了。

三、循环队列

1、上面第(7)步元素a6入队后,尾指针Q.rear要后移一个位置,此时已经超过了数组的下标,即Q.rear+1 = maxLen(最大空间数6),那么如果前面有空闲,Q.rear可以转向前面0的位置:

2、a7入队,Q.front = 2,Q.rear = 1;

3、a8入队,Q.front = 2,Q.rear = 2,队满;

这样队列空间得到了充分的利用,但队满时Q.front = Q.rear,与队空时一样,要怎样判断队满还是队空?

解决办法有两个:

  1. 添加一个标志位记录队满和队空;
  2. 浪费rear所指向的空间,如图3-2,当(rear + 1) % maxLen = front时,即为队满,不再插入元素。由此可以和队空时的front = rear区分开来。

四、java实现循环队列

import java.util.Arrays;

/**
 * 循环队列
 * @author miner
 *
 */
public class CircularQueue<T> {
	int front;
	int rear;
	Object[] queueList;
	int maxLen;
	public CircularQueue(int len) {
		maxLen = len;
		queueList = new Object[maxLen];
		front = 0;
		rear = 0;
	}
	
	//判空函数
	public boolean isEmpty() {
		if(front == rear) {
			return true;
		}
		return false;
	}
	
	//判满函数
	public boolean isFull() {
		if(front == (rear + 1) % maxLen) {
			return true;
		}
		return false;
	}
	
	//取队头
	@SuppressWarnings("unchecked")
	public T getHead() {
		if(isEmpty()) {
			System.out.println("队列为空!");
			return null;
		}
		return (T)queueList[front];
	}
	
	//入队
	public void enqueue(T data) {
		if(isFull()) {
			System.out.println("队列已满!");
			return;
		}
		queueList[rear] = data;
		rear = (rear + 1) % maxLen;
	}
	
	//出队
	public T dequeue() {
		if(isEmpty()) {
			System.out.println("队列为空!");
			return null;
		}
		@SuppressWarnings("unchecked")
		T res = (T)queueList[front];
		front = (front + 1) % maxLen;
		return res;
	}
	
	//获取队列长度
	public int getLength() {
		if(isEmpty()) {
			return 0;
		}
		return rear > front ? rear - front: maxLen - (front - rear);
	}
	
	//清空循环队列
	public void clear(){
		Arrays.fill(queueList, null);
		front=0;
		rear=0;
	}
}

测试类:

public class CircularQueueTest {
	
	public static void main(String[] args) {
		CircularQueue<Integer> queue = new CircularQueue<Integer>(10);
		//入队0~8
		for(int i = 0; i < 9; i++) {
			queue.enqueue(i);
		}
		System.out.println("队列长度:" + queue.getLength());
		//出队0~8
		for(int i = 0; i < 9; i++) {
			System.out.println(queue.dequeue());
		}
		System.out.println("队列长度:" + queue.getLength());
		queue.enqueue(11);
		System.out.println("队列长度:" + queue.getLength());
		queue.dequeue();
		System.out.println("队列长度:" + queue.getLength());
		queue.isFull();
	}
}

 

说明:

图片引用自http://baijiahao.baidu.com/s?id=1597253471156873230&wfr=spider&for=pc

 

 

 

文章已创建 65

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部