眾所周知，隊(duì)列是一種先進(jìn)先出（First-in-first-out 簡(jiǎn)稱FIFO）數(shù)據(jù)結(jié)構(gòu)甚疟。
為了實(shí)現(xiàn)隊(duì)列茧跋，我們??可以使用動(dòng)態(tài)數(shù)組和指向隊(duì)列頭部的索引。
如上所述悲幅，隊(duì)列應(yīng)該支持兩個(gè)操作：enqueue和dequeue套鹅。Enqueue會(huì)向隊(duì)列追加一個(gè)新元素，而dequeue會(huì)刪除第一個(gè)元素汰具。所以我們需要一個(gè)索引來指出起點(diǎn)卓鹿。
代碼如下：
class MyCircularQueue {
final int[] a;
int front, rear = -1, len = 0;
public MyCircularQueue(int k) { a = new int[k];}
public boolean enQueue(int val) {
if (!isFull()) {
rear = (rear + 1) % a.length;
a[rear] = val;
len++;
return true;
} else return false;
}
public boolean deQueue() {
if (!isEmpty()) {
front = (front + 1) % a.length;
len--;
return true;
} else return false;
}
public int Front() { return isEmpty() ? -1 : a[front];}
public int Rear() {return isEmpty() ? -1 : a[rear];}
public boolean isEmpty() { return len == 0;}
public boolean isFull() { return len == a.length;}
}
上面的代碼有個(gè)問題就是，隨著p_start 增加留荔，空間的浪費(fèi)吟孙。對(duì)此，我們進(jìn)行優(yōu)化，使用循環(huán)的隊(duì)列（Circular Queue）代碼如下：
class MyCircularQueue {
private int[] data;
private int head;
private int tail;
private int size;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
data = new int[k];
head = -1;
tail = -1;
size = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull() == true) {
return false;
}
if (isEmpty() == true) {
head = 0;
}
tail = (tail + 1) % size;
data[tail] = value;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
if (head == tail) {
head = -1;
tail = -1;
return true;
}
head = (head + 1) % size;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (isEmpty() == true) {
return -1;
}
return data[head];
}
/** Get the last item from the queue. */
public int Rear() {
if (isEmpty() == true) {
return -1;
}
return data[tail];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return head == -1;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return ((tail + 1) % size) == head;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
原理就是：使用固定大小的數(shù)組（a fixed-size array）和兩個(gè)變量（two pointers）-head 指示起始位置和 tail 指示結(jié)束位置杰妓，初始化時(shí)head 和tail 均為-1肥隆，入隊(duì)（enQueue）的時(shí)候(tail+1)% fixed-size,出隊(duì)（deQueue）的時(shí)候(head+1)% fixed-size,head == 1時(shí)候隊(duì)列為空，((tail + 1) % size) == head時(shí)候隊(duì)列滿了稚失。
很多高級(jí)語言栋艳，都有內(nèi)置的隊(duì)列庫(kù)，所以我們不需要重復(fù)造輪子（reinvent the whell）,比如Java
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
// 1. Initialize a queue.
Queue<Integer> q = new LinkedList();
// 2. Get the first element - return null if queue is empty.
System.out.println("The first element is: " + q.peek());
// 3. Push new element.
q.offer(5);
q.offer(13);
q.offer(8);
q.offer(6);
// 4. Pop an element.
q.poll();
// 5. Get the first element.
System.out.println("The first element is: " + q.peek());
// 7. Get the size of the queue.
System.out.println("The size is: " + q.size());
}
}
