了解循环队列的实现-白红宇

了解循环队列的实现

阅读量：5241 次

发布时间：2019-06-14

本文共 2355 字，大约阅读时间需要 7 分钟。

上一节中，我们发现顺序队列的多次入队和出队操作会造成有存储空间却不能进入队列的"假溢出"现象，之所以发生这种情况，是因为顺序队列的存储单元没有重复存储机制，解决方法是如果数据一直存放到了数组的末尾，那么下一个存储位置就折回到数组的开头。这样就相当于数组的末尾就和它的开头连接上了，于是虽然数组的物理结构是“直线”，但是其逻辑结构已经变成“圆环”了。

来看循环队列的代码实现

public class MyCircleQueue implements IQueue
    
      {	private int[] nums = new int[6];	/*	 * 这里有一个需要解决的问题，就是判断队满和队空的条件都成了front==rear，这显然是不行的;	 * 怎么解决？	 * 让队列少存一个，最多只能存length - 1个元素，这样一来;	 * 判断队列空的条件还是front==rear,	 * 判断队满的条件成了front=(rear+1)%length;	 */	private int front = 0;//队首指针	private int rear = 0;//队尾指针	private int length = nums.length;		@Override	public void clear() {		// TODO Auto-generated method stub		front = rear = 0;		nums = new int[6];	}		@Override	public boolean isEmpty() {		// TODO Auto-generated method stub		if(front == rear) {			return true;		}		return false;	}		@Override	/*	 * 返回队列存储的元素个数	 */	public int length() {		// TODO Auto-generated method stub		//没循环前 直接rear-front		//循环后 rear+length-front		//合并		return (rear+length-front)%length;	}		@Override	public Integer peek() throws Exception {		// TODO Auto-generated method stub		if(isEmpty()) {			throw new Exception("队为空");		}		return nums[front];	}	@Override	public void offer(Integer t) throws Exception {		// TODO Auto-generated method stub		if((rear + 1) % length == front) {			throw new Exception("队满了");		}		nums[rear] = t;		rear = (rear + 1) % length;	}	@Override	public Integer poll() throws Exception {		// TODO Auto-generated method stub		if(isEmpty()) {			throw new Exception("队为空");		}		Integer o = nums[front];		front = (front + 1) % length;		return o;	}	@Override	public void display() {		// TODO Auto-generated method stub		if(isEmpty()) {			System.out.println("队为空");		} else {			for(int i = front; i < rear; i = (i + 1)%length) {				System.out.print(nums[i] + " ");			}		}	}}

测试

public class CircleQueueTest {	public static void main(String[] args) throws Exception {		MyCircleQueue circleQueue = new MyCircleQueue();		circleQueue.offer(1);		circleQueue.offer(2);		circleQueue.offer(3);		circleQueue.offer(4);		circleQueue.offer(5);		circleQueue.display();		System.out.println();		System.out.println("----------");		System.out.println(circleQueue.length());		System.out.println(circleQueue.peek());		System.out.println(circleQueue.poll());		System.out.println(circleQueue.length());		circleQueue.display();			}}

测试结果