言
本篇介紹隊列的定義、隊列的實作方式（數組實作隊列，連結清單實作隊列），如果你需要了解其他資料結構，請點選下面連結檢視！！！
了解更多：資料結構與算法目錄整理
隊列
一、隊列的定義
隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。
隊列的資料元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中删除一個隊列元素稱為出隊。因為隊列隻允許在一端插入，在另一端删除，是以隻有最早進入隊列的元素才能最先從隊列中删除，故隊列又稱為先進先出（FIFO—first in first out）線性表。
二、隊列的實作方式（順序存儲于鍊式存儲）
1）隊列的基本操作及其說明
| 方法名 | 傳回值 | 參數類型 | 說明 |
|---|---|---|---|
| isFull() | boolean | 無 | 判斷隊列是否為滿 |
| isEmpty() | boolean | 無 | 判斷隊列是否為空 |
| add(int data) | void | int | 向隊列中添加元素 |
| getOne() | int | 無 | 從隊列中去除元素 |
| getHead() | int | 無 | 擷取頭部元素 |
| getQueue() | List | 無 | 擷取隊列元素 |
| size() | int | 無 | 擷取隊列中元素的個數 |
2）隊列的數組實作
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import javax.management.RuntimeErrorException;
/**
* *隊列的數組實作
* @author 蠟筆小新
*
*/
public class Test3 {
public static void main(String []args) {
boolean temp=true;
ArrQueue arrQueue=new ArrQueue(3);
while(temp) {
System.out.println("isFull:隊列是否為滿");
System.out.println("isEmpty:隊列是否為空");
System.out.println("add:添加元素");
System.out.println("getOne:擷取元素");
System.out.println("getHead:擷取頭部元素");
System.out.println("getQueue:擷取隊列");
System.out.println("size:擷取隊列中元素的個數");
System.out.println("exit:退出程式");
System.out.println("輸入你的操作指令：");
Scanner scanner=new Scanner(System.in);
String str=scanner.nextLine();
switch(str) {
case "isFull":
System.out.println(arrQueue.isFull());
break;
case "isEmpty":
System.out.println(arrQueue.isEmpty());
break;
case "add":
System.out.println("輸入要添加的資料：");
int n=scanner.nextInt();
arrQueue.add(n);
break;
case "getOne":
try {
int m = arrQueue.getOne();
System.out.println(m);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "getHead":
try {
int s=arrQueue.getHead();
System.out.println(s);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case "getQueue":
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case "size":
System.out.println(arrQueue.size());
break;
case "exit":
temp=false;
break;
default:
System.out.println("輸入有誤");
break;
}
}
System.out.println("程式退出！");
}
}
class ArrQueue{
private int maxSize; //隊列的最大容量
private int front; //隊列頭
private int rear; //隊列尾
private int []arr; //模拟隊列
public ArrQueue(int maxSize) {
this.maxSize=maxSize;
front=-1; //指向頭部的前一個位置
rear=-1; //指向尾部的位置
arr=new int[maxSize]; //初始化數組
}
//判斷隊列是否為空
public boolean isEmpty() {
return front==rear;
}
//判斷隊列是否為滿
public boolean isFull() {
return rear==maxSize-1;
}
//向隊列中添加元素
public void add(int data) {
if(isFull()) {
System.out.println("隊列已滿");
return ;
}
arr[++rear]=data;
}
//從隊列中去除元素
public int getOne() throws Exception{
if(isEmpty()) {
throw new Exception("隊列為空");
}
return arr[++front];
}
//size() int 無 擷取隊列中元素的個數
//getHead() int 無 擷取頭部元素
public int getHead() throws Exception {
if(isEmpty()) {
throw new Exception("隊列為空");
}
return arr[front+1];
}
//擷取隊列元素
public List getQueue() {
if(isEmpty()) {
throw new RuntimeException("隊列為空");
}
List list=new ArrayList<>();
for(int i=front+1;i<=rear;i++) {
list.add(arr[i]);
}
return list;
}
//擷取隊列元素個數
public int size() {
if(isEmpty()) {
return 0;
}
return rear+1;
}
} 複制
運作結果：
以上就是隊列的數組實作，但是我們發現以上方法隻能使用一次，無法做到複用的效果，是以對以上代碼進行修改如下：
對以上程式中的 getOne()方法進行修改
//從隊列中去除元素
public int getOne() throws Exception{
if(isEmpty()) {
throw new Exception("隊列為空");
}
int t=arr[++front];
if(isEmpty()) {
front=rear=-1;
}
else {
for(int i=front+1;i<=rear;i++) {
arr[i-1]=arr[i];
}
front--;
rear--;
}
return t;
} 複制
3）隊列的連結清單實作
正在神速整理中。。。。。敬請期待