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

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

用front指針指向 隊(duì)首元素所在的單元, 使用rear指針指向隊(duì)尾元素所在單元的后一個(gè)單元；

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

如何表示隊(duì)列為空還是隊(duì)列滿 ??

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

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

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

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

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

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

}