隊(duì)列

• 先看隊(duì)列接口和結(jié)點(diǎn)類
• 1. 順序隊(duì)列
• 2. 循環(huán)隊(duì)列
• 3. 鏈隊(duì)列

先看隊(duì)列接口和結(jié)點(diǎn)類

package com.lovely.queue;/** * 2020年4月26日下午2:42:44* * @author echo lovely**/ public interface IQueue {public void clear(); // 將隊(duì)列置空public boolean isEmpty(); // 判斷隊(duì)列是否為空public int length(); // 返回隊(duì)列的數(shù)據(jù)元素個(gè)數(shù)public Object peek(); // 返回隊(duì)首元素 public void offer(Object x) throws Exception; // x插入隊(duì)列，隊(duì)尾入隊(duì)public Object poll(); // 返回隊(duì)首元素，并刪除 隊(duì)首出隊(duì)public void display(); // 輸出隊(duì)列中所有數(shù)據(jù)元素}package com.lovely.linearList;/** * 2020年4月1日下午8:25:10* * @author echo lovely** @category 節(jié)點(diǎn)類 用于存數(shù)據(jù) 和 后繼節(jié)點(diǎn)*/public class Node {public Object data; // 存放節(jié)點(diǎn)數(shù)據(jù)值public Node next; // 存放后繼節(jié)點(diǎn)public Node() {this(null, null);}// 只有節(jié)點(diǎn)值的構(gòu)造函數(shù)public Node(Object data) {this(data, null);}// 帶有節(jié)點(diǎn)值和后繼節(jié)點(diǎn)的構(gòu)造函數(shù)public Node(Object data, Node next) {this.data = data;this.next = next;} }

1. 順序隊(duì)列

package com.lovely.queue;/*** @author echo lovely** 2020年4月26日下午3:03:05* * 隊(duì)列的順序儲存結(jié)構(gòu)* 隊(duì)首出隊(duì)（刪除），隊(duì)尾入隊(duì)（插入）。*/ public class SeqQueue implements IQueue {private Object[] queueElem; // 隊(duì)列的儲存空間private int maxSize; // 隊(duì)列的最大儲存單元個(gè)數(shù)private int front; // 指向隊(duì)首元素private int rear; // 指向隊(duì)尾元素的下一個(gè)元素 // 構(gòu)造最大儲存單元為maxSize的空隊(duì)列public SeqQueue(int maxSize) {this.maxSize = maxSize;front = rear = 0;queueElem = new Object[maxSize];}@Overridepublic void clear() {// 隊(duì)列置空front = rear = 0; }@Overridepublic boolean isEmpty() {// 隊(duì)列是否為空 return front == rear;}@Overridepublic int length() {// 隊(duì)列長度return rear - front;}@Overridepublic Object peek() {// 返回隊(duì)首元素if (isEmpty())return null;return queueElem[front];}@Overridepublic void offer(Object x) throws Exception {// 隊(duì)尾入隊(duì)if (rear == maxSize)throw new Exception("隊(duì)列已滿");queueElem[rear] = x;rear ++; // 指向隊(duì)尾的下一個(gè)元素}@Overridepublic Object poll() {// 出隊(duì) 只不過是不顯示罷了if (isEmpty())return null;front ++; // 指向原來隊(duì)首元素的下一個(gè)元素return queueElem[front];}@Overridepublic void display() {if (!isEmpty()) {for (int i = front; i < rear; i++) {System.out.print(queueElem[i] + "\t");}} elseSystem.out.println("隊(duì)列為空！");}}

• 測試

package com.lovely.queue;public class TestSeqQueue {public static void main(String[] args) {// 順序隊(duì)列SeqQueue sq = new SeqQueue(6);try {// 入隊(duì)sq.offer(1);sq.offer(2);sq.offer(3);sq.offer(4);} catch (Exception e) {e.printStackTrace();}System.out.println("隊(duì)列長度 " + sq.length());Object obj = sq.poll();System.out.println(obj + "出隊(duì)后，長度 " + sq.length());System.out.println("隊(duì)首元素：" + sq.peek());sq.display();/* 這里有問題，多次入隊(duì)出隊(duì)操作，造成有存儲空間卻不能進(jìn)行入隊(duì)操作的"假溢出"現(xiàn)象try {sq.offer(88);sq.offer(88);sq.poll();sq.poll();sq.offer(88);sq.poll();} catch (Exception e) {e.printStackTrace();}System.out.println("\n長度 " + sq.length());sq.display();*//* 隊(duì)列長度 4 2出隊(duì)后，長度 3 隊(duì)首元素：2 2 3 4 */}}

2. 循環(huán)隊(duì)列

package com.lovely.queue;/*** * @author echo lovely** 2020年5月19日下午8:53:03* * 循環(huán)順序隊(duì)列* 順序隊(duì)列的多次入隊(duì)和出隊(duì) 會造成有儲存空間 卻不能進(jìn)行入隊(duì)操作的假溢出現(xiàn)象。*/ public class CircleSeqQueue {private Object[] queueElem; // 隊(duì)列的儲存空間private int front; // 指向隊(duì)首元素private int rear; // 指向隊(duì)尾元素的下一個(gè)儲存元素private int maxSize; // 隊(duì)列的最大儲存單元個(gè)數(shù)// 構(gòu)造最大儲存單位個(gè)數(shù)為maxSize的空隊(duì)列public CircleSeqQueue(int maxSize) {front = rear = 0;queueElem = new Object[maxSize];this.maxSize = maxSize;}// 將隊(duì)列置空public void clear() {front = rear = 0;}// 判斷隊(duì)列是否為空public boolean isEmpty() {return front == rear;}// 隊(duì)列的長度public int length() {return (rear - front + maxSize) % maxSize; }// 讀取隊(duì)首元素public Object peek() {if (isEmpty())return null;return queueElem[front];}// 入隊(duì)public void offer(Object x) throws Exception {if ((rear + 1) % maxSize == front) throw new Exception("隊(duì)列已滿");queueElem[rear] = x;rear = (rear + 1) % maxSize;}// 出隊(duì)public Object poll() {if (rear == front)return null;Object p = queueElem[front];front = (front + 1) % maxSize;return p;}// 遍歷隊(duì)列public void display() {if (!isEmpty()) {for (int i = 0; i < rear; i = (i + 1) % maxSize) {System.out.print(queueElem[i] + " ");}} elseSystem.out.println("此隊(duì)列為空！");} }

• 測試

package com.lovely.queue;public class TestCircleSeqQueue {public static void main(String[] args) {// 構(gòu)造長度為10的隊(duì)列CircleSeqQueue csq = new CircleSeqQueue(10);try {csq.offer(1);csq.offer(2);csq.offer(3);csq.offer(4);csq.offer(5);csq.offer(6);} catch (Exception e) {e.printStackTrace();}System.out.println("隊(duì)首元素：" + csq.peek());System.out.println("出隊(duì)：" + csq.poll());csq.display();}}/** 隊(duì)首元素：1 出隊(duì)：1 2 3 4 5 6 */

3. 鏈隊(duì)列

package com.lovely.queue;import com.lovely.linearList.Node;/*** * @author echo lovely* 2020年6月7日下午7:20:02* * 鏈隊(duì)列 * 使用單鏈表實(shí)現(xiàn)* 實(shí)現(xiàn)入隊(duì)隊(duì)尾 出隊(duì)隊(duì)首, 沒有中間的插入或者刪除* * 無需頭節(jié)點(diǎn) , front指向頭節(jié)點(diǎn) rear指向隊(duì)尾結(jié)點(diǎn)便可*/ public class LinkQueue implements IQueue {private Node front; // 隊(duì)首指針private Node rear; // 隊(duì)尾指針// 構(gòu)造空隊(duì)列public LinkQueue() {front = rear = null;}public void clear() {front = rear = null;}public boolean isEmpty() {// 隊(duì)首是否為空return front == null;}@Overridepublic int length() {Node p = front;int length = 0;while (p != null) {p = p.next;length ++;}return length;}// 返回隊(duì)首元素值public Object peek() {if (isEmpty()) return null;return front.data;}@Overridepublic void offer(Object x) throws Exception {// 入隊(duì)Node s = new Node(x);if (!isEmpty()) { // 隊(duì)列非空rear.next = s;rear = s;} else front = rear = s;}// 出隊(duì)public Object poll() {if (front == null)return null;Node p = front;front = front.next;if (p == rear) {rear = null; // 刪除結(jié)點(diǎn)為隊(duì)尾結(jié)點(diǎn)時(shí)需要修改rear}return p.data;}public void display() {if (!isEmpty()) {for(Node p = front;p != null;p = p.next) {System.out.print(p.data + "\t");}System.out.println();} else {System.out.println("此隊(duì)列為空");}}}

• 測試

package com.lovely.queue;public class TestLinkQueue {public static void main(String[] args) {// 鏈隊(duì)列的增刪改查LinkQueue lq = new LinkQueue();try {lq.offer(2);lq.offer(3);lq.offer(5);lq.offer(7);lq.offer(11);} catch (Exception e) {e.printStackTrace();}System.out.println("入隊(duì)的隊(duì)列：");lq.display();System.out.println("隊(duì)首元素：" + lq.peek());System.out.println("隊(duì)首出隊(duì)：" + lq.poll());lq.display();System.out.println("隊(duì)列的長度為：" + lq.length());}}/** 入隊(duì)的隊(duì)列： 2 3 5 7 11 隊(duì)首元素：2 隊(duì)首出隊(duì)：2 3 5 7 11 隊(duì)列的長度為：4*/

總結(jié)

以上是生活随笔為你收集整理的顺序队列，循环队列，链队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。