java數據結構中順序隊列和循環隊列的區別是什么

這篇文章主要介紹“java數據結構中順序隊列和循環隊列的區別是什么”，在日常操作中，相信很多人在java數據結構中順序隊列和循環隊列的區別是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java數據結構中順序隊列和循環隊列的區別是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

目錄

• 隊列：

• 順序隊列：

• 代碼實現：

• 循環隊列：

• 代碼實現：

• 總結

隊列：

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

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

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

具有先進先出的特性

順序隊列：

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

設置隊頭指針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]);
		}
	}
}

到此，關于“java數據結構中順序隊列和循環隊列的區別是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！