順序存儲實(shí)現(xiàn)循環(huán)隊列

在隊列的實(shí)現(xiàn)中, 可以把數(shù)據(jù)設(shè)想為一個圓環(huán), 這種數(shù)組稱為循環(huán)數(shù)組, 用循環(huán)數(shù)組實(shí)現(xiàn)的隊列稱為循環(huán)隊列；

用front指針指向 隊首元素所在的單元, 使用rear指針指向隊尾元素所在單元的后一個單元；

在元素入隊時, 將新入隊的元素保存到rear指向的單元 ,然后rear指向后移; 在出隊時, 將隊首指針 front指向的元素返回, 然后front后移。

如何表示隊列為空還是隊列滿 ??

一般情況下,采用以下兩種方式表示隊列已滿：

1、少用一個存儲單元, 當(dāng)隊尾指針rear的下個單元是隊首指針front時, 停止入隊, ( rear + 1 ) % capacity == front時表示隊列滿, 當(dāng)front == rear時表示隊列為空。

2、增設(shè)一個標(biāo)志表示隊列為空還是滿 , 通常用size變量表示元素的個數(shù), 當(dāng)size==0時隊列為空, 當(dāng)size==capacity時表示隊列已滿。

package com.wkcto.chapter02.queue;
/**
 * 隊列的順序存儲實(shí)現(xiàn)
 * @author 蛙課網(wǎng)
 *
 */
public class MyArrayQueue {
	private  Object[] elements ; 		//定義數(shù)組存儲隊列中的元素
	private static final int DEFAULT_CAPACITY = 8;
	private int front ; 		//隊首
	private int rear; 			//隊尾
	private int size;			//元素的個數(shù)
	
	//構(gòu)造方法
	public MyArrayQueue() {
		elements = new Object[DEFAULT_CAPACITY];
	}
	public MyArrayQueue(int initialCapacity) {
		elements = new Object[initialCapacity];
	}
	
	//返回元素的個數(shù)
	public int  getSize() {
		return size;
	}
	//判斷隊列是否為空
	public boolean isEmpty() {
		return size == 0 ;
	}
	
	//入隊
	public void enQueue(Object e) {
		//如果隊列已滿 ,可以對數(shù)組擴(kuò)容
		if ( size >= elements.length ) {
			expandQueue();
		}
		
		elements[rear] = e; 		//把元素存儲到rear指針指向的單元
		rear = (rear+1) % elements.length;		//rear指針后移
		size++;						//元素的個數(shù)加1
	}
	//隊列的數(shù)組進(jìn)行擴(kuò)容
	private void expandQueue() {
		//定義一個更大的數(shù)組
		Object[] newElements = new Object[elements.length * 2]; 		//默認(rèn)按2倍大小擴(kuò)容
				
		//把原來數(shù)組的內(nèi)容復(fù)制到新的數(shù)組中, 從隊首開始的元素依次復(fù)制到新數(shù)組索引值0開始的位置
		for( int i = 0 ;  i < size ; i++) {
			newElements[i] = elements[front];
			front = (front + 1) % elements.length;
		}
		
		//讓原來的數(shù)組名指向新的數(shù)組
		elements = newElements;
		//調(diào)整新的隊首也隊尾指針
		front = 0 ; 
		rear = size;
	}
	
	//出隊
	public Object  deQueue() {
		//如果隊列為空
		if ( size <= 0 ) {
			//拋出一個隊列為空的異常
			throw  new QueueEmptyException("隊列為空");
		}
		//隊列不為空, 把front指向的元素返回, 
		Object old = elements[front];
		front = (front + 1 ) % elements.length;		//front指針后移
		size--;							//元素個數(shù)減1
		return old;
	}
	//返回隊首元素
	public Object peek() {
		//隊列為空,拋出異常
		if (size <= 0 ) {
			throw  new QueueEmptyException("隊列為空");
		}
		
		return elements[front];
	}
}

package com.wkcto.chapter02.queue;
/**
 * 自定義隊列為空的異常
 * 	該異常是一個運(yùn)行時異常, 不需要開發(fā)人員進(jìn)行預(yù)處理
 * 	RuntimeException的子類就是運(yùn)行時異常
 * @author 蛙課網(wǎng)
 *
 */
public class QueueEmptyException extends RuntimeException {

	public QueueEmptyException() {
		super();
	}
	//String參數(shù),傳遞的是異常的信息
	public QueueEmptyException(String message) {
		super(message);
	}

}