簡(jiǎn)介
棧是“后進(jìn)先出”（LIFO，Last InFirst Out）的數(shù)據(jù)結(jié)構(gòu)嗡善，與之相反，隊(duì)列是“先進(jìn)先出”（FIFO，F(xiàn)irst InFirst Out）的數(shù)據(jù)結(jié)構(gòu)
隊(duì)列的作用就像售票口前的人們站成的一排一樣：第一個(gè)進(jìn)入隊(duì)列的人將最先買到票菩鲜，最后排隊(duì)的人最后才能買到票
在計(jì)算機(jī)操作系統(tǒng)或網(wǎng)路中，有各種隊(duì)列在安靜地工作著惦积。打印作業(yè)在打印隊(duì)列中等待打印接校。當(dāng)敲擊鍵盤時(shí)，也有一個(gè)存儲(chǔ)鍵盤鍵入內(nèi)容的隊(duì)列狮崩，如果我們敲擊了一個(gè)鍵蛛勉，而計(jì)算機(jī)又暫時(shí)在做其他事情，敲擊的內(nèi)容不會(huì)丟失睦柴，它會(huì)排在隊(duì)列中等待诽凌，直到計(jì)算機(jī)有時(shí)間來(lái)讀取它，利用隊(duì)列保證了鍵入內(nèi)容在處理時(shí)其順序不會(huì)改變
棧的插入和刪除數(shù)據(jù)項(xiàng)的命名方法很標(biāo)準(zhǔn)坦敌，成為push和pop侣诵，隊(duì)列的方法至今也沒(méi)有一個(gè)標(biāo)準(zhǔn)化的方法，插入可以稱作put狱窘、add或enque等杜顺，刪除可以叫作delete、get蘸炸、remove或deque等
隊(duì)列示意圖
隨著隊(duì)頭元素不斷地移除躬络，數(shù)組前面空出的位置會(huì)越來(lái)越多，當(dāng)隊(duì)尾指針移到最后的位置時(shí)搭儒，即使隊(duì)列沒(méi)有滿穷当，我們也不能再插入新的數(shù)據(jù)項(xiàng)了提茁，如下圖：
解決這種缺點(diǎn)的方法是環(huán)繞式處理，即讓隊(duì)尾指針回到數(shù)組的第一個(gè)位置馁菜，
形成循環(huán)隊(duì)列（也成為緩沖環(huán)）茴扁。雖然在存儲(chǔ)上是線形的，但是在邏輯上它是一個(gè)首尾銜接的環(huán)形：
public class Queue {
private int[] queues;
private int maxSize;
private int front;
private int rear;
private int length;
public Queue(int maxSize) {
queues = new int[maxSize];
this.maxSize = maxSize;
this.front = 0;
this.rear = -1;
this.length = 0;
}
//插入
public void insert(int value) throws Exception {
if (isFull()){
throw new Exception("隊(duì)列已滿");
}
if (rear == maxSize -1){
rear = -1;
}
queues[++rear] = value;
length++;
}
//移除
public boolean remove() throws Exception {
if (isEmpty()){
throw new Exception("隊(duì)列為空");
}
int elem = queues[front++];
if (front == maxSize){
front = 0;
}
length--;
return true;
}
//查看隊(duì)頭元素
public int peek() throws Exception {
if (isEmpty()){
throw new Exception("隊(duì)列為空火邓！");
}
return queues[front];
}
//獲取隊(duì)列長(zhǎng)度
public int getSize(){
return length;
}
//判空
public boolean isEmpty(){
return (length == 0);
}
//判滿
public boolean isFull(){
return (length == maxSize);
}
public void display(){
if (front < rear){
for (int i = front;i <= rear;i++){
System.out.print(queues[i]+" ");
}
System.out.print("\n");
}else {
for (int i = front;i < maxSize;i++){
System.out.print(queues[i]+" ");
}
for (int i = rear;i < front;i++){
System.out.print(queues[i]+" ");
}
}
}
}
//測(cè)試
public static void main(String[] args) throws Exception {
Queue queue = new Queue(5);
queue.insert(1);
queue.display();
queue.remove();
queue.display();
System.out.println(queue.peek());
System.out.println(queue.getSize());
queue.insert(6);
queue.display();
}
優(yōu)先級(jí)隊(duì)列
優(yōu)先級(jí)隊(duì)列有一個(gè)隊(duì)頭和一個(gè)隊(duì)尾丹弱，并且也是從隊(duì)頭移除數(shù)據(jù)，從隊(duì)尾插入數(shù)據(jù)铲咨，不同的是躲胳，在優(yōu)先級(jí)隊(duì)列中，數(shù)據(jù)項(xiàng)按關(guān)鍵字的值排序纤勒，數(shù)據(jù)項(xiàng)插入的時(shí)候會(huì)按照順序插入到合適的位置坯苹。（簡(jiǎn)單來(lái)說(shuō)就是按照優(yōu)先級(jí)排序，插入按照優(yōu)先級(jí)大小插入）摇天。
插入圖
刪除圖
除了可以快速訪問(wèn)優(yōu)先級(jí)最高的數(shù)據(jù)項(xiàng)粹湃，優(yōu)先級(jí)隊(duì)列還應(yīng)該可以實(shí)現(xiàn)相當(dāng)快的插入，因此泉坐，優(yōu)先級(jí)隊(duì)列通常使用一種稱為堆的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)为鳄。具體實(shí)現(xiàn)如下：
