隊列（Queue）
? 隊列是一種具有一定操作約束的線性表经伙，它的插入和刪除操作都只能在一端進行扶叉，數(shù)據插入叫做入隊，數(shù)據刪除稱為出隊帕膜，它是一種典型的先進先出（FIFO）的結構枣氧。
抽象數(shù)據類型描述
? 數(shù)據對象集：一個有0個或多個元素的線性表。
? 操作集：Item 代表數(shù)據元素類型
-
boolean isEmpty()判斷隊列是否為空 -
int length()返回隊列的大小 -
void addQueue(Item item)入隊 -
Item deleteQueue()出隊
隊列的順序存儲
? 采用聲明的固定大小的數(shù)組來存儲數(shù)據垮刹，因為隊列是先進先出的达吞，入隊和出隊只在一端進行，所以會發(fā)生數(shù)組內部空間無法得到充分利用的情況（隨著入隊和出隊操作不斷進行荒典，隊首指針和隊尾指針會不停的往后移動酪劫，這樣數(shù)組前面的空間就無法得到充分的利用），所以需要用到循環(huán)隊列寺董，而采取循環(huán)的關鍵就是取余數(shù)覆糟。對隊首指針和隊尾指針加一后需要進行取余數(shù)的操作，這樣指針可以實現(xiàn)循環(huán)螃征。完整代碼如下：
public class ArrayQueue<Item> {
private Item[] data;
private int first;
private int last;
private int size;
public ArrayQueue(int size){
data = (Item[]) new Object[size];
}
public boolean isEmpty(){
return size==0;
}
public int length(){
return size;
}
public void addQueue(Item item){
// 先判斷是否滿了
if (size == data.length){
System.out.println("隊列已滿!");
return;
} else{
last = (last + 1)%data.length;
data[last] = item;
size = size+1;
}
}
public Item deleteQueue(){
// 先判斷是否為空
if (size == 0){
System.out.println("隊列為空!");
return null;
} else{
first = (first + 1)%data.length;
size = size-1;
return data[first];
}
}
public void printData(){
int current = (first+1)%data.length;
for (int i=1; i<=size; i++){
System.out.print(data[current] + " ");
current = (current+1)%data.length;
}
System.out.println();
}
public static void main(String[] args) {
ArrayQueue<Integer> testQ = new ArrayQueue<>(5);
testQ.addQueue(1);
testQ.addQueue(2);
testQ.deleteQueue();
testQ.addQueue(3);
testQ.deleteQueue();
testQ.addQueue(4);
testQ.addQueue(5);
testQ.printData();
}
}
隊列的鏈式存儲
? 由于鏈表的頭部和尾部對于插入和刪除操作的適應性不同（鏈表頭部插入和刪除均很方便搪桂，鏈表尾部插入方便，無法刪除）盯滚，所以隊首（出隊操作）要設在鏈表的鏈表頭部踢械，隊尾（入隊操作）設在鏈表尾部，然后還需要注意的地方就是魄藕，在第一次入隊時需要把隊首指針也指向第一個結點内列，在刪除了最后一個元素時需要把隊尾指針指向null，完整代碼如下：
public class Queue<Item> implements Iterable<Item>{
private Node first; // 指向最早添加的結點
private Node last; //指向最近添加的結點
private int N;
private class Node{
Item item;
Node next;
}
public boolean isEmpty(){
return first == null; // 或者N等于0
}
public int size(){
return N;
}
public void enqueue(Item item){
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
// 剛開始時背率，如果隊列為空话瞧，要把first也指向第一個元素
if (isEmpty()){
first = last;
}else{
oldLast.next = last;
}
N = N + 1;
}
public Item dequeue(){
Item item = first.item;
first = first.next;
// 如果刪除之后為空，也要把last指向null
if (isEmpty()){
last = null;
}
N = N - 1;
return item;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
private Node current = first;
@Override
public boolean hasNext() {
return current!= null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove() {}
}
}
