順序存儲實現循環隊列

在隊列的實現中, 可以把數據設想為一個圓環, 這種數組稱為循環數組, 用循環數組實現的隊列稱為循環隊列；

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

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

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

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

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

2、增設一個標志表示隊列為空還是滿 , 通常用size變量表示元素的個數, 當size==0時隊列為空, 當size==capacity時表示隊列已滿。

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

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

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

}