數據結構和演算法02–隊列

• 2021 年 4 月 13 日
• 筆記

​ 隊列：先進先出、用鏈表或數組實現。

一、一般的隊列

1、思路：

​ 模擬簡單隊列——隊首走的位置不能再添加。

​ 實現方式：兩個指針，一個指向隊首front、一個指向隊尾rear。指向隊首的負責取出數據，指向隊尾的負責添加數據。

​ 難點：在於添加和取出數據時，指針應先操作該位置數據然後再移動指針，不然指針就沒了。

2、程式碼

​ 程式碼實現思路：先創建數組隊列–>添加判斷為空、已滿、放入數據、取出數據、遍歷隊列、查看頭節點的方法–>main方法寫測試程式碼。

//測試最基本的隊列
public class BasicQueue01 {
	//9、創建主方法用於測試
	public static void main(String[] args) {
		//創建一個隊列
		ArrayQueue arrQueue = new ArrayQueue(4);
		//用於接收用戶輸入資訊
		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		
		while(loop) {
			System.out.println("s(show): 顯示隊列");
			System.out.println("e(exit): 退出程式");
			System.out.println("a(add): 添加數據到隊列");
			System.out.println("g(get): 從隊列取出數據");
			System.out.println("h(head): 查看隊列頭的數據");
			key = scanner.next().charAt(0);
			switch(key) {
				case 's':
					arrQueue.showQueue();
					break;
				case 'a':
					System.out.println("請輸入一個數");
					int value = scanner.nextInt();
					arrQueue.addQueue(value);
					break;
				case 'g':
					try {
						int num = arrQueue.getQueue();
						System.out.println(num);
					}catch(RuntimeException e) {
						System.out.println(e.getMessage());
					}
					break;
				case 'h':
					try {
						int headQueue = arrQueue.headQueue();
						System.out.println("第一個數據是" + headQueue);
					}catch(RuntimeException e) {
						System.out.println(e.getMessage());
					}
					break;
				case 'e':
					scanner.close();
					loop = false;
				default:
					break;
			}
		}
		System.out.println("程式退出啦");
	}

}

class ArrayQueue{
	//1、先給出隊列的各種屬性
	private int maxSize;
	private int front;
	private int rear;
	private int[] arr;
	
	//2、給一個隊列的構造方法
	public ArrayQueue(int arrmaxSize) {
		maxSize = arrmaxSize;
		front = -1;
		rear = -1;
		arr = new int[maxSize];
	}
	
	//3、判斷隊列是否已滿
	public boolean isFull() {
		return rear == maxSize - 1;
	}
	
	//4、判斷隊列是否為空
	public boolean isEmpty() {
		return rear == front;
	}
	
	//5、添加數據到隊列
	public void addQueue(int n) {
		//(1)先判斷隊列是否已滿
		if(isFull()) {
			System.out.println("隊列已滿，不能添加~~");
			return;
		}
		//(2)如果不滿的話，那就在後面加一格，然後加數據
		rear++;
		arr[rear] = n;
	}
	
	//6、獲取隊列的數據，出隊列
	public int getQueue() {
		//(1)先判斷隊列是否為空
		if(isEmpty()) {
			throw new RuntimeException("隊列為空，不能獲取~~");
		}
		
		//(2)如果不為空的話，那就把指向第一個的前面這個指針，指向第一個，然後取出來，以此類推
		front++;
		return arr[front];
	}
	
	//7、查詢隊列
	public void showQueue() {
		if (isEmpty()) {
			System.out.println("隊列空的，沒有數據~~");
			return;
		}
		for(int i = 0;i < arr.length;i++) {
			System.out.printf("arr[%d]=%d\n",i+1,arr[i]);
		}
		System.out.println();
	}
	
	//8、顯示隊列的頭數據
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("隊列為空，無法顯示");
		}
		return arr[front+1];
	}
}

二、循環隊列

1、思路

​ 解決普通隊列不能不能在前面位置再添加的問題。

​ 改成環形隊列這樣就可以反覆添加了。

​ 但是這裡要注意到最大值後就返回到初始值了。

​ 實現方式：front、rear指針，每添加一個rear指向當前位置後一個，浪費一個元素，指到最後一個元素為滿。

​ 難點：因為滿了又跳到0，所以得注意front/rear + 1可能回到初始位置，並且得注意rear – front可能存在小減大的情況，所以判斷有幾個元素的時候不能直接用rear – front的方式。

2、程式碼

​ 程式碼實現思路：先創建數組隊列–>添加判斷為空、已滿、放入數據、取出數據、遍歷隊列、查看頭節點的方法–>main方法寫測試程式碼。

//測試環形隊列
public class CircleArrayQueue01 {
	public static void main(String[] args) {
		System.out.println("測試數組模擬環形隊列的案例~~~");
		CircleQueue circleQueue = new CircleQueue(4);
		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		while(loop) {
			System.out.println("s(show): 顯示隊列");
			System.out.println("e(exit): 退出程式");
			System.out.println("a(add): 添加數據到隊列");
			System.out.println("g(get): 從隊列取出數據");
			System.out.println("h(head): 查看隊列頭的數據");
			key = scanner.next().charAt(0);
			switch(key) {
				case 's':
					circleQueue.showQueue();
					break;
				case 'a':
					System.out.println("請輸入一個數");
					int num = scanner.nextInt();
					circleQueue.addQueue(num);
					break;
				case 'g':
					try {
						int result = circleQueue.getQueue();
						System.out.printf("查到的數據是%d\n",result);
					}catch(RuntimeException e) {
						System.out.println(e.getMessage());
					}
					break;
				case 'h':
					int result = circleQueue.headQueue();
					System.out.printf("查到的數據是%d\n",result);
					break;
				case 'e':
					scanner.close();
					loop = false;
					break;
				default:
					break;
			}
		}
		System.out.println("退出程式~~");
	}
	
}

class CircleQueue{
	//屬性
	private int maxSize;
	private int front;
	private int rear;
	private int[] arr;
	
	//構造函數
	public CircleQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
	}
	
	//判斷是否為空
	public boolean isEmpty() {
		return rear == front;
	}
	
	//判斷是否已滿
	public boolean isFull() {
		return (rear  + 1) % maxSize == front;
	}
	
	//添加數列到隊列
	public void addQueue(int num) {
		if(isFull()) {
			System.out.println("隊列已滿，無法加入");
			return;
		}
		arr[rear] = num;
		rear = (rear + 1) % maxSize;
	}
	
	//獲取隊列數據，出隊列
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("隊列為空，不能取數據");
		}
		int value = arr[front];
		front = (front + 1)% maxSize;
		return value;
	}
	
	//顯示隊列所有數據
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("隊列為空，不能顯示");
			return;
		}
		for(int i = front;i < front + size() ;i++) {
			System.out.printf("arr[%d] = %d\n",i%maxSize,arr[i%maxSize]);
		}
	}
	
	//求出當前隊列的有效數據
	public int size() {
		return (rear + maxSize - front) % maxSize;
	}
	
	//顯示隊列的頭數據
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("隊列為空，沒有數據");
		}
		return arr[front];
	}
}