java數據結構基礎:順序隊列和循環隊列

Posted on by

隊列：

隊列是一種受限制的線性表

隻允許在表的一端進行插入，另一端進行刪除

插入的一端稱作隊尾，刪除的一端稱作隊頭

具有先進先出的特性

順序隊列：

隊列底層數據采用數組存儲

設置隊頭指針front指向隊頭元素前一個位置，初始值為-1

設置隊尾指針rear指向隊尾元素，初始值為-1

判滿：rear == maxSize – 1

判空：rear == front

代碼實現：

//順序隊列
public class ArrayQueue {
	private int maxSize;    //數組的最大容量
	private int front;        //隊頭指針
	private int rear;        //隊尾指針
	private int[] array;    //存放數據
	public ArrayQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		array = new int[maxSize];
		front = -1;        //指向隊頭的前一個位置
		rear = -1;        //指向隊尾
	}
	//判斷隊列是否滿
	public boolean isFull() {
		return rear == maxSize - 1;
	}
	//判斷隊列是否空
	public boolean isEmpty() {
		return rear == front;
	}
	//入隊
	public void addQueue(int n) {
		//判斷隊列是否滿
		if (isFull()) {
			System.out.println("隊列滿");
			return;
		}
		rear++;    //rear後移
		array[rear] = n;
	}
	//出隊
	public int getQueue() {
		//判斷隊列是否空
		if (isEmpty()) {
			throw new RuntimeException("隊列為空");
		}
		front++;    //front後移
		return array[front];
	}
	//取隊頭數據
	public int headQueue() {
		if (isEmpty()) {
			throw new RuntimeException("隊列為空");
		}
		return array[front + 1];
	}
	//輸出隊列所有數據
	public void showQueue() {
		//遍歷輸出
		if (isEmpty()) {
			System.out.println("隊列為空");
            return;
		}
		for (int i = 0; i < array.length; i++) {
			System.out.printf("array[%d] = %d\n", i, array[i]);
		}
	}
}

順序隊列存在假溢出現象，故使用循環隊列替代順序隊列

循環隊列：

隊列底層數據仍然采用數組存儲

為瞭便於判空和判滿，在數組中預留一個空間，認為隻留下一個空間的時候隊列為滿

設置隊頭指針front指向隊頭元素，初始值為0

設置隊尾指針rear指向隊尾元素的後一個位置，初始值為0

判滿：(rear + 1) % maxSize == front

判空：rear == front

取得當前隊列有效數據個數：(rear + maxSize – front) % maxSize

代碼實現：

//循環隊列
public class CircleQueue {
	private int maxSize;    //數組的最大容量
	private int front;        //隊頭指針
	private int rear;        //隊尾指針
	private int[] array;    //存放數據
	public CircleQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		array = new int[maxSize];
		front = 0;        //指向隊頭的前一個位置
		rear = 0;        //指向隊尾
	}
	//判斷隊列是否滿
	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;
		}
		array[rear] = n;
		rear = (rear + 1) % maxSize;
	}
	//出隊
	public int getQueue() {
		//判斷隊列是否空
		if (isEmpty()) {
			throw new RuntimeException("隊列為空");
		}
		//保存front對應的值
		int value = array[front];
		front = (front + 1) % maxSize;
		return value;
	}
	//取隊頭數據
	public int headQueue() {
		if (isEmpty()) {
			throw new RuntimeException("隊列為空");
		}
		return array[front];
	}
	//獲取當前隊列有效數據個數
	public int size() {
		return (rear + maxSize - front) % maxSize;
	}
	//輸出隊列所有數據
	public void showQueue() {
		//遍歷輸出
		if (isEmpty()) {
			System.out.println("隊列為空");
            return;
		}
		//從front開始遍歷
		for (int i = front; i < front + size(); i++) {
			System.out.printf("array[%d] = %d\n", i % maxSize, array[i % maxSize]);
		}
	}
}

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：