不知道你有沒有過在餐廳打飯的經(jīng)歷倔矾，我們排的隊其實(shí)就是我們今天所講的主題妄均，我們在排隊的時候柱锹，在隊列頭部的人打好飯離開，新來的人排在隊尾丰包。這就是入隊和出隊的操作禁熏。所以，隊列的特性就是先進(jìn)先出邑彪。有了這個概念瞧毙，就可以開始今天的主題。先給出這篇文章的大致脈絡(luò)：
首先寄症，使用java語言描述了隊列的基本操作宙彪，有鏈?zhǔn)酱鎯晚樞?/p>
然后，介紹循環(huán)隊列和一系列需要注意的知識點(diǎn)
最后有巧，對隊列進(jìn)行一個總結(jié)释漆。
OK，開始今天的文章篮迎。
一灵汪、隊列基本操作
1、隊列的基本認(rèn)識
隊列的基本特性就是先進(jìn)先出（FIFO）柑潦。也就是第一個進(jìn)去的元素享言，第一個出來。現(xiàn)在給出一個標(biāo)準(zhǔn)的定義：
隊列就是一個只允許在一端進(jìn)行插入渗鬼，在另一端進(jìn)行刪除操作的線性表览露。
既然是線性表，按照存儲方式那就有兩種存儲方式譬胎，基于數(shù)組的順序存儲方式和基于鏈表的鏈?zhǔn)酱鎯Ψ绞健?/p>
隊列按照實(shí)現(xiàn)方式也分為兩種：
①差牛、單向隊列（Queue）：只能在一端插入數(shù)據(jù)，另一端刪除數(shù)據(jù)堰乔。
②偏化、雙向隊列（Deque）：每一端都可以進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作。
有了對概念分類有了了解镐侯，下面我們就是用java代碼來實(shí)現(xiàn)這些隊列
2侦讨、順序隊列的實(shí)現(xiàn)
順序隊列是基于數(shù)組實(shí)現(xiàn)的，針對于隊列的操作主要有以下幾個
（1）插入（2）刪除（3）查找元素（4）隊列長度（5）是否為空苟翻、
我們先給出最基本的操作圖解
下面就根據(jù)這幾個常用的操作使用java代碼來實(shí)現(xiàn)隊列
首先韵卤，我們定義一個操作隊列的接口
public interface Queue<T> {
//增加元素
void add(T t);
//刪除元素
T remove();
//隊列長度
int size();
//返回對頭元素，并未刪掉
T front();
//是否為空
boolean isEmpty();
//是否已滿
boolean isFull()
}
然后我們就開始去實(shí)現(xiàn)崇猫。
插入操作沈条，我們首先要先判斷當(dāng)前隊列是否已滿，如果滿了直接返回诅炉。接下來得到當(dāng)前元素的位置蜡歹。最后插入元素屋厘，再移動位置。
刪除操作與插入操作類似月而，首先要先判斷當(dāng)前隊列是否為空擅这，如不為空再移動指針（這里不是指針，指的是指向當(dāng)前元素位置的標(biāo)志）景鼠，刪除元素。
判斷當(dāng)前元素是否為空和是否已滿類似痹扇，只需要判斷當(dāng)前隊列的元素數(shù)量铛漓。
下面給出代碼實(shí)現(xiàn)。
public class ArrayQueue<T> implements Queue<T>{
private T[] data;
private int size;//元素個數(shù)
private int front;//隊列中第一個對象的位置
private int rear;//隊列中當(dāng)前對象的位置
//初始化方法
public ArrayQueue() {
data = (T[]) new Object[10];
size = 0;
front =0;
rear = 0;
}
//增加元素
@Override
public void add(T t) {
if(isFull()){
resize();
front = 0;
}
rear = (front+size)%data.length;
System.out.println(rear);
data[rear] = t;
size++;
}
//刪除元素
@Override
public T remove() {
if (isEmpty()) {
throw new RuntimeException("隊列為空!");
}
T tempData = data[front];
data[front] = null;
front = (front + 1) % (data.length);
size--;
return tempData;
}
//取得隊列大小
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
//判斷當(dāng)前隊列是否已滿
@Override
public boolean isFull(){
return size == data.length;
}
//取得當(dāng)前隊頭元素
@Override
public T front() {
if (isEmpty()) {
throw new RuntimeException("隊列為空!");
}
return data[front];
}
//擴(kuò)容
public void resize(){
/*注意重新擴(kuò)容的時候并不需要去設(shè)置size
* 隊列的大小并不能通過數(shù)組的大小直觀的顯示出來鲫构。
* 但是棧就可以直觀的通過數(shù)組的大小顯示出來*/
T[] tmp = (T[]) new Object[data.length*2];
System.arraycopy(data, 0, tmp, 0, data.length);
data = tmp;
tmp = null;//引用置為空浓恶，便于gc處理
}
}
3、鏈?zhǔn)疥犃械膶?shí)現(xiàn)
鏈?zhǔn)疥犃信c順序隊列不同结笨，每個節(jié)點(diǎn)不僅保存當(dāng)前元素的值包晰，還有指向下一個元素的指針。所以我們先看一下每個節(jié)點(diǎn)的圖解形式
使用代碼來表示就是
public class QueueNode<Item>{
Item item;
QueueNode next;
}
然后我們看鏈?zhǔn)疥犃腥腙牶统鲫牭牟僮?/p>
（a）空隊列 （b）X入隊 （c）y入隊 （d）x出隊
從上面的操作我們可以看到炕吸，實(shí)現(xiàn)上面的操作我們需要實(shí)現(xiàn)下面的代碼
（1）一個指向FIFO頭節(jié)點(diǎn)的指針
（2）一個指向FIFO尾節(jié)點(diǎn)的指針
（3）一個記錄節(jié)點(diǎn)數(shù)的Int變量
private QueueNode first;//指向FIFO頭節(jié)點(diǎn)的指針
private QueueNode last; //指向FIFO尾節(jié)點(diǎn)的指針
private int nodeNum; //記錄節(jié)點(diǎn)數(shù)的Int變量
（4）判斷當(dāng)前隊列是否為空
public boolean isEmpty(){
return first == null;
}
（5）隊列的大小
public int size(){
return nodeNum;
}
（6）入隊和出隊操作
//入隊
public void enqueue(Item item) {
QueueNode oldLast = last;
last = new QueueNode();
last.item = item;
last.next = null;
if (isEmpty()){
first = last;
} else{
oldLast.next = last;
}
nodeNum++;
}
//出隊
public Item dequeue(){
Item item = (Item) first.item;
first = first.next;
if (isEmpty()){
last = null;
}
nodeNum--;
return item;
}
（7）遍歷
private class LinkListIterator implements Iterator<Item>{
QueueNode node = first;
@Override
public boolean hasNext(){
return node.next != null;
}
@Override
public Item next(){
Item item = (Item) node.item;
node = node.next;
return item;
}
}
OK伐憾。有了上面的這些操作之后，下面給出一個完整的代碼
public class Queue<Item> implements Iterable<Item>{
private QueueNode first;
private QueueNode last;
private int nodeNum;
public boolean isEmpty(){
return first == null;
}
public int size(){
return nodeNum;
}
public void enqueue(Item item){
QueueNode oldLast = last;
last = new QueueNode();
last.item = item;
last.next = null;
if (isEmpty()){
first = last;
} else{
oldLast.next = last;
}
nodeNum++;
}
public Item dequeue(){
Item item = (Item) first.item;
first = first.next;
if (isEmpty()){
last = null;
}
nodeNum--;
return item;
}
@Override
public Iterator<Item> iterator(){
return new LinkListIterator();
}
private class LinkListIterator implements Iterator<Item>{
QueueNode node = first;
@Override
public boolean hasNext(){
return node.next != null;
}
@Override
public Item next(){
Item item = (Item) node.item;
node = node.next;
return item;
}
}
}
OK赫模，上面就是順序隊列和鏈?zhǔn)疥犃械幕緦?shí)現(xiàn)树肃。下面我們將介紹一種新的隊列循環(huán)隊列，為什么要有這個隊列瀑罗，我們先要考慮一個問題胸嘴，也就是我們的隊列彈出一個元素，那么這個空間將不能使用斩祭。這就是假溢出問題：
為了解決這個問題所以才出現(xiàn)了一個新的隊列-循環(huán)隊列
二劣像、循環(huán)隊列
我們先給出隊列的圖解形式
有了循環(huán)隊列的基本實(shí)現(xiàn)，我們思考一個問題摧玫，在之前我們可以根據(jù)rear直接得到當(dāng)前隊列是否為空和是否已滿耳奕。那么在循環(huán)隊列里面還可以這樣嘛？當(dāng)然不可以诬像，我們需要考慮font和rear的位置關(guān)系來判斷吮铭。我們看下面兩種情況：
一種是隊列為空的時候，front和rear都指向同一個位置颅停。一種是隊列已滿的時候谓晌，front和rear指向的元素緊鄰。
我們可以使用下面的公式來判斷
我們代碼實(shí)現(xiàn)一下循環(huán)隊列
public interface IQueue {
public void clear();
public boolean isEmpty();
public int length();
public Object peek();// 取隊首元素
public void offer(Object x) throws Exception;// 入隊
public Object poll();// 出隊
public void display();
}
然后是接口的實(shí)現(xiàn)
public class CircleSqQueue implements IQueue {
private Object[] queueElem;//隊列存儲空間
private int front;//隊首引用癞揉，若隊列不為空纸肉，指向隊首元素
private int rear;//隊尾引用溺欧，若隊列不為空，指向隊尾的下一個元素
public CircleSqQueue(int maxsize) {
front=rear=0;
queueElem=new Object[maxsize];//分配maxsize個單元
}
@Override
public void clear() {
front=rear=0;
}
@Override
public boolean isEmpty() {
return rear==front;
}
@Override
public int length() {
return (rear-front+queueElem.length)%queueElem.length;
}
@Override
public Object peek() {
if(front==rear){
return null;
}
else{
return queueElem[front];
}
}
@Override
public void offer(Object x) throws Exception {
if((rear+1)%queueElem.length==front){//隊滿
throw new Exception("隊列已滿");
}
else{
queueElem[rear]=x;
rear=(rear+1)%queueElem.length;//修改隊尾指針
}
}
@Override
public Object poll() {
if(front==rear){
return null;//隊列為空
}
else{
Object t=queueElem[front];
front=(front+1)%queueElem.length;
return t;
}
}
@Override
public void display() {
if(!isEmpty()){
for(int i=front;i!=rear;i=(i+1)%queueElem.length){
System.out.println(queueElem[i].toString()+" ");
}
}
else{
System.out.println("此隊列為空");
}
}
}
三柏肪、總結(jié)
對于隊列主要在于面試中常見的算法題姐刁，因?yàn)楦拍罘浅Ｈ菀桌斫猓覀冎灰鶕?jù)當(dāng)前實(shí)現(xiàn)的代碼進(jìn)行一些變化就好烦味。謝謝大家的關(guān)注聂使。
