1.2 Queue
什麼是Queue: Queue是一種特殊的線性表, 限定只能在表的一端進行插入(隊尾), 而在另一端進行刪除操作(隊頭), 特點是"先進先出"(FIFO).
Queue的基本操作:
insert:在隊尾插入資料
remove: 從隊頭移走資料
peek: 查看隊頭的資料
Circular Queue: 為了避免queue未滿, 卻不能插入新資料項的問題, 可以讓隊頭隊尾的指標繞回陣列開始的位置, 這就是circular queue, 又稱作ring buffer.
Queue的效能: insert和remove的時間複雜度均為O(1)
一個簡單的circular queue的實作(原始碼點我):
package idv.carl.datastructures.queue;
/**
* @author Carl Lu
*/
public class CircularQueue {
private int[] queue;
private int head;
private int tail;
// Number of elements in this queue
private int elementCount;
public CircularQueue(int length) {
queue = new int[length];
head = 0;
tail = -1;
elementCount = 0;
}
public void insert(int element) {
// Check the tail index already exceed the max length or not
if (tail == queue.length - 1) {
tail = -1;
}
tail++;
queue[tail] = element;
elementCount++;
if (elementCount > queue.length) {
elementCount = queue.length;
}
}
public int remove() {
if (elementCount == 0) {
return 0;
}
int temp = queue[head];
queue[head] = 0;
// Check the head index already exceed the max length or not
if (head == queue.length - 1) {
/*
* If the removed node is tail, it means that the next node will be removed must be the
* head node since this is a circular queue, so reset head index to 0.
*/
head = 0;
} else {
head++;
}
elementCount--;
return temp;
}
public int peek() {
return queue[head];
}
public boolean isEmpty() {
return elementCount == 0;
}
public boolean isFull() {
return elementCount == queue.length;
}
public int getElementCount() {
return elementCount;
}
}
Last updated
Was this helpful?