05-環形隊列

實現思路

1，調整front指向隊列的第一個元素，front初始值=0

2，調整rear指向隊列的最后一個元素的后一個位置，希望空出一個空間作為約定，rear的初始值=0

3，隊滿，條件： (rear+1) % maxSize = front ，則隊滿，隊列最多可存?maxSize-1個數

4，隊空，條件：rear == front空

5，隊列中有效的數據的個數 (rear-front+maxSize) % maxSize

代碼實現

package?com.datastack.datastack.queue;

import?java.util.Scanner;

/*
?*?環形隊列（數組實現）
?*/
public?class?CircleQueue?{
	private?int?maxSize;//隊列最大值
	private?int?front;//隊首，指向隊列首的前一個位置
	private?int?rear;//隊尾，指向隊列尾的序號
	private?int[]?arr;//存放隊列數據的數組
	
	/**
	?*?創建隊列
	?*?@param?maxSize
	?*/
	public?CircleQueue(int?maxSize){
		this.maxSize?=?maxSize;
		this.arr?=?new?int[maxSize];
		this.front?=?0;
		this.rear?=?0;
	}
	
	/**
	?*?判斷隊列是否已滿
	?*?@return
	?*/
	public?boolean?isFull(){
		return?(rear+1)?%?maxSize?==?front;
	}
	
	/**
	?*?判斷隊列是否為空
	?*?@param?args
	?*/
	public?boolean?isEmpty(){
		return?rear?==?front;
	}
	
	/**
	?*?添加數據到隊列
	?*?@param?args
	?*/
	public?void?addQueue(int?n){
		//判斷隊列是否滿
		if(isFull()){
			System.out.println("隊列已滿，不能加入數據。");
			return;
		}
		//直接將數據加入
		arr[rear]?=?n;
		//將rear后移，需考慮取模
		rear?=?(rear+1)?%?maxSize;
	}
	
	/**
	?*?出隊列
	?*?@param?args
	?*/
	public?int?getQueue(){
		//判斷隊列是否為空
		if(isEmpty()){
			//通過拋出異常
			throw?new?RuntimeException("隊列空，不能取數據");
		}
		//需要分析front是指向隊列的第一個元素
		//1，先把front的值保存到變量
		//2，將front后移，去摸
		int?res?=?this.arr[front];
		front?=?(front+1)?%?maxSize;
		return?res;
	}
	
	/**
	?*?顯示隊列數據
	?*?@param?args
	?*/
	public?void?showQueque(){
		if(isEmpty()){
			System.out.println("隊列為空。");
			return;
		}
		//從front開始遍歷
		for(int?i=front;i<front+size();i++){
			System.out.printf("arr[%d]=%d\t",i?%?maxSize,arr[i?%?maxSize]);
		}
	}
	
	/**
	?*?求出當前隊列有效個數
	?*/
	public?int?size(){
		return?(rear-front+maxSize)?%?maxSize;
	}
	
	/**
	?*?顯示隊頭
	?*?@param?args
	?*/
	public?int?headQueue(){
		if(isEmpty()){
			throw?new?RuntimeException("隊列為空。");
		}
		return?this.arr[front];
	}
	
	public?static?void?main(String[]?args)?{
		//創建一個隊列
		CircleQueue?arrQueue?=?new?CircleQueue(3);
		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.showQueque();
				break;
			case?'a'://入隊
				System.out.println("請輸入一個數");
				int?value?=?scanner.nextInt();
				arrQueue.addQueue(value);
				break;
			case?'g'://出隊
				try?{
					int?res?=?arrQueue.getQueue();
					System.out.println(res);
				}?catch?(Exception?e)?{
					System.out.println(e.getMessage());
				}
				break;
			case?'h'://打印對首
				try?{
					int?res?=?arrQueue.headQueue();
					System.out.println(res);
				}?catch?(Exception?e)?{
					System.out.println(e.getMessage());
				}
				break;
			case?'e'://退出程序
				scanner.close();
				loop?=?false;
				break;

			default:
				break;
			}
		}
		System.out.println("程序退出");
		
	}
}