網(wǎng)上看了好多實現(xiàn)隊列的實現(xiàn)方式，做個個人總結(jié)慢宗。隊列的主要特征就是 先進(jìn)先出恒傻。實現(xiàn)隊列基本上有兩種思路實現(xiàn)：
1.使用數(shù)組（弊端是數(shù)據(jù)有大小限制，會出現(xiàn)隊列已滿的情況）
2.通過鏈表
下面分別來講一下這兩種 方式
1.使用數(shù)組的方式
使用數(shù)據(jù)的方式可以理解為一個隊列是一個圓形的數(shù)組辛燥，分別用兩個參數(shù)記錄隊頭（front）和隊尾(rear)的位置。
20130806120215890.jpg
如果只是用頭和尾來標(biāo)識的話還不能滿足要求缝其，因為剛頭和尾相同時挎塌，還要區(qū)分是空的還是滿的情況，所以需要加一個參數(shù)記錄當(dāng)前隊列個數(shù)氏淑。
簡單的實現(xiàn)代碼如下
public class MyQueue<T> {
private Object[] array;
private int size;
private int front;
private int rear;
private int counter;
public MyQueue(int size) {
array = new Object[size];
this.size = size;
this.front = 0;
this.rear = 0;
this.counter = 0;
}
public boolean isFull() {
return this.counter >= this.size;
}
public boolean isEmpty() {
return this.counter <= 0;
}
/**把數(shù)據(jù)放入隊列*/
public boolean push(Object data) {
if(isFull()) return false;
array[this.rear] = data;
this.rear = (this.rear + 1) % this.size;
this.counter ++;
return true;
}
/**刪除隊列最前面的數(shù)*/
public boolean delete() {
if(isEmpty()) return false;
this.front = (this.front+1) % this.size;
this.counter --;
return true;
}
/**出出隊并刪除數(shù)據(jù)*/
public T getData(){
if(isEmpty()) return null;
return (T) array[this.front];
}
/**出出隊并刪除數(shù)據(jù)*/
public T pull() {
T data = getData();
delete();
return data;
}
}
測試代碼
MyQueue1<Integer> queue = new MyQueue1<Integer>(5);
for (int i = 0; i < 20; i++) {
boolean f = queue.push(i);
System.out.println(i + " = " +f);
if(i % 3 == 0) {
System.out.println("輸出:"+queue.pull());
}
}
int ind = 0;
while (ind < 30) {
ind ++;
System.out.println(" 輸出:"+queue.pull());
}
好了勃蜘，下面再來介紹通過鏈表的方式。
2 鏈表的實現(xiàn)方法
先看下圖
隊列.jpg
鏈表的方式的思路就是在每個節(jié)點存數(shù)據(jù)的同時記錄下一個節(jié)點的信息
Node代碼
public class Node {
private Object val;
private Node next;
public Node(){}
public Node(Object value) {
val = value;
}
public void setNext(Node next) {
this.next = next;
}
public Object getValue() {
return val;
}
public Node getNext() {
return next;
}
}
隊列代碼
public class MyQueue {
private Node front = new Node();
private Node rear = front;
public boolean isEmpty() {
return front == rear;
}
/**向隊列中放入數(shù)據(jù)*/
public boolean push(Object o) {
Node node = new Node(o);
this.rear.setNext(node);
this.rear = node;
return true;
}
/**從隊列中讀取數(shù)據(jù)*/
public Object pull() {
if(isEmpty()) return null;
Node deNode = front.getNext();
Object val = deNode.getValue();
//判斷是否最后一個節(jié)點
if(deNode.getNext() == null) {
front = rear;
} else {
front.setNext(deNode.getNext());
}
return val;
}
}
