java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):順序隊(duì)列和循環(huán)隊(duì)列

更新時(shí)間：2021年08月01日 10:34:16 作者：去吧貓頭夜鷹

下面小編就為大家分享一篇java隊(duì)列實(shí)現(xiàn)方法(順序隊(duì)列,循環(huán)隊(duì)列)，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧

隊(duì)列：

隊(duì)列是一種受限制的線性表

只允許在表的一端進(jìn)行插入，另一端進(jìn)行刪除

插入的一端稱作隊(duì)尾，刪除的一端稱作隊(duì)頭

具有先進(jìn)先出的特性

順序隊(duì)列：

隊(duì)列底層數(shù)據(jù)采用數(shù)組存儲

設(shè)置隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)位置，初始值為-1

設(shè)置隊(duì)尾指針rear指向隊(duì)尾元素，初始值為-1

判滿：rear == maxSize - 1

判空：rear == front

代碼實(shí)現(xiàn)：

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

順序隊(duì)列存在假溢出現(xiàn)象，故使用循環(huán)隊(duì)列替代順序隊(duì)列

循環(huán)隊(duì)列：

隊(duì)列底層數(shù)據(jù)仍然采用數(shù)組存儲

為了便于判空和判滿，在數(shù)組中預(yù)留一個(gè)空間，認(rèn)為只留下一個(gè)空間的時(shí)候隊(duì)列為滿

設(shè)置隊(duì)頭指針front指向隊(duì)頭元素，初始值為0

設(shè)置隊(duì)尾指針rear指向隊(duì)尾元素的后一個(gè)位置，初始值為0

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

判空：rear == front

取得當(dāng)前隊(duì)列有效數(shù)據(jù)個(gè)數(shù)：(rear + maxSize - front) % maxSize

代碼實(shí)現(xiàn)：

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