Java資料結構與算法：循環隊列

目錄标題

• 1. 思路與設計
• 2. 完整代碼
• 3. LeetCode_662設計循環隊列

1. 思路與設計

對前面的數組模拟隊列的優化，充分利用數組。是以将數組看做是一個環形的。(通過取模的方式來實作即可)

思路：

• front

  變量的含義做一個調整：

  front

  就指向隊列的第一個元素，也就是說

  arr[front]

  就是隊列的第一個元素；

  front

  的初始值=0

• rear

  變量的含義做一個調整：

  rear

  指向隊列的最後一個元素，因為希望空出一個空間做為約定。

  rear

  的初始值=0
• 當隊列滿時，條件是：

  (rear+1)% maxSize = front

• 當隊列空時，條件是：

  rear==front

• 隊列中有效的資料的個數：

  (rear+maxSize-front)%maxSize

循環隊列API設計：

使用方法	詳細說明
public CircleArray(int arrMaxSize)	構造方法：初始化資料組最大值和存放隊列資料
public boolean isFull()	判斷隊列是否滿
public boolean isEmpty()	判斷隊列是否為空
public void addQueue(int n)	添加資料到隊列
public int getQueue()	擷取隊列的資料，出隊列
public void showQueue()	顯示隊列的所有資料
public int size()	求出目前隊列有效資料的個數
public int headQueue()	顯示隊列的頭資料，注意不是取出資料

2. 完整代碼

public class CircleArrayQueueDemo {
	public static void main(String[] args) {
		// 說明設定4，其隊列的有效資料最大是3
		CircleArray queue = new CircleArray(4);
		int key = 0;
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		System.out.println("\t 1: 顯示隊列");
		System.out.println("\t 2: 添加資料到隊列");
		System.out.println("\t 3: 從隊列取出資料");
		System.out.println("\t 4: 檢視隊列頭的資料");
		System.out.println("\t 5: 退出程式");
		while (loop) {
			key = scanner.nextInt();
			switch (key) {
			case 1:
				queue.showQueue();
				break;
			case 2:
				System.out.println(">>輸入一個數：");
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case 3:
				try {
					int res = queue.getQueue();
					System.out.printf("取出的資料是%d\n", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 4:
				try {
					int res = queue.headQueue();
					System.out.printf("隊列頭的資料是%d\n", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 5:
				scanner.close();
				loop = false;
				break;
			default:
				System.out.println("請輸入有效數字~");
				break;
			}
		}
		System.out.println("程式退出~");
	}
}
//核心實作代碼
class CircleArray {
	private int maxSize;// 表示數組的最大值
	// front 變量的含義做一個調整： front 就指向隊列的第一個元素,
	// 也就是說 arr[front] 就是隊列的第一個元素
	// front 的初始值 = 0
	private int front; // 隊列頭
	// rear 變量的含義做一個調整：rear 指向隊列的最後一個元素的後一個位置.
	// 因為希望空出一個空間做為約定
	// rear 的初始值 = 0
	private int rear; // 隊列尾
	private int[] arr; // 該資料用于存放資料, 模拟隊列

	public CircleArray(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
	}

	// 判斷隊列是否滿
	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}

	// 判斷隊列是否為空
	public boolean isEmpty() {
		return rear == front;
	}

	// 添加資料到隊列
	public void addQueue(int n) {
		if (isFull()) {
			System.out.println("隊列滿，不能加入資料~");
			return;
		}
		// 直接插入資料
		arr[rear] = n;
		// 将rear 後移，這裡必須考慮取模
		rear = (rear + 1) % maxSize;
		System.out.println(">>輸出成功！");
	}

	// 擷取隊列的資料，出隊列
	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];
	}

}
           

3. LeetCode_662設計循環隊列

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/design-circular-queue

MyCircularQueue(k)

: 構造器，設定隊列長度為 k 。

Front

: 從隊首擷取元素。如果隊列為空，傳回 -1 。

Rear

: 擷取隊尾元素。如果隊列為空，傳回 -1 。

enQueue(value)

: 向循環隊列插入一個元素。如果成功插入則傳回真。

deQueue()

: 從循環隊列中删除一個元素。如果成功删除則傳回真。

isEmpty()

: 檢查循環隊列是否為空。

isFull()

: 檢查循環隊列是否已滿。

實作代碼：

class MyCircularQueue {
    /**此方法并沒有犧牲一個額外空間，整個數組的記憶體配置設定均可使用 */
    private int front;   //隊列頭
    private int rear;    //隊列尾
    private int maxSize; //隊列最大數
    private int[] data;  //隊列存放的資料

    public MyCircularQueue(int k) {
        maxSize=k;
        data=new int[maxSize];
        front=-1;
        rear=-1;
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        if(isEmpty()){
            front=0;
        }
        rear=(rear+1)%maxSize;
        data[rear]=value;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        if(front==rear){
            front=-1;
            rear=-1;
        }else{
            front=(front+1)%maxSize;
        }
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return data[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return data[rear];
    }
    
    public boolean isEmpty() {
        return front==-1;
    }
    
    public boolean isFull() {
        return (rear+1)%maxSize==front;
    }
}