欧美大陆成人中出,你懂得911日本

不知道你有沒有過在餐廳打飯的經(jīng)歷，我們排的隊其實就是我們今天所講的主題，我們在排隊的時候，在隊列頭部的人打好飯離開，新來的人排在隊尾。這就是入隊和出隊的操作。所以，隊列的特性就是先進(jìn)先出。有了這個概念，就可以開始今天的主題。先給出這篇文章的大致脈絡(luò)：

首先，使用java語言描述了隊列的基本操作，有鏈?zhǔn)酱鎯晚樞?/p>
然后，介紹循環(huán)隊列和一系列需要注意的知識點(diǎn)

最后，對隊列進(jìn)行一個總結(jié)。

OK，開始今天的文章。

一、隊列基本操作

1、隊列的基本認(rèn)識

隊列的基本特性就是先進(jìn)先出（FIFO）。也就是第一個進(jìn)去的元素，第一個出來?，F(xiàn)在給出一個標(biāo)準(zhǔn)的定義：

隊列就是一個只允許在一端進(jìn)行插入，在另一端進(jìn)行刪除操作的線性表。

既然是線性表，按照存儲方式那就有兩種存儲方式，基于數(shù)組的順序存儲方式和基于鏈表的鏈?zhǔn)酱鎯Ψ绞健?/p>

隊列按照實現(xiàn)方式也分為兩種：

①、單向隊列（Queue）：只能在一端插入數(shù)據(jù)，另一端刪除數(shù)據(jù)。

②、雙向隊列（Deque）：每一端都可以進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作。

有了對概念分類有了了解，下面我們就是用java代碼來實現(xiàn)這些隊列

2、順序隊列的實現(xiàn)

順序隊列是基于數(shù)組實現(xiàn)的，針對于隊列的操作主要有以下幾個

（1）插入（2）刪除（3）查找元素（4）隊列長度（5）是否為空、

我們先給出最基本的操作圖解

2-順序隊列入隊出隊.png

下面就根據(jù)這幾個常用的操作使用java代碼來實現(xiàn)隊列

首先，我們定義一個操作隊列的接口

public interface Queue<T> {
      //增加元素
     void add(T t);
      //刪除元素
      T remove();
      //隊列長度
      int size();
      //返回對頭元素，并未刪掉
      T front();  
      //是否為空
      boolean isEmpty();
      //是否已滿
      boolean isFull()
}

然后我們就開始去實現(xiàn)。

插入操作，我們首先要先判斷當(dāng)前隊列是否已滿，如果滿了直接返回。接下來得到當(dāng)前元素的位置。最后插入元素，再移動位置。

刪除操作與插入操作類似，首先要先判斷當(dāng)前隊列是否為空，如不為空再移動指針（這里不是指針，指的是指向當(dāng)前元素位置的標(biāo)志），刪除元素。

判斷當(dāng)前元素是否為空和是否已滿類似，只需要判斷當(dāng)前隊列的元素數(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)疥犃械膶崿F(xiàn)

鏈?zhǔn)疥犃信c順序隊列不同，每個節(jié)點(diǎn)不僅保存當(dāng)前元素的值，還有指向下一個元素的指針。所以我們先看一下每個節(jié)點(diǎn)的圖解形式

3-鏈?zhǔn)疥犃行问?png

使用代碼來表示就是

public class QueueNode<Item>{
    Item item;
    QueueNode next;
}

然后我們看鏈?zhǔn)疥犃腥腙牶统鲫牭牟僮?/p>

4-鏈?zhǔn)疥犃性鰟h改查.png

（a）空隊列（b）X入隊（c）y入隊（d）x出隊

從上面的操作我們可以看到，實現(xiàn)上面的操作我們需要實現(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)疥犃械幕緦崿F(xiàn)。下面我們將介紹一種新的隊列循環(huán)隊列，為什么要有這個隊列，我們先要考慮一個問題，也就是我們的隊列彈出一個元素，那么這個空間將不能使用。這就是假溢出問題：

4-5假溢出問題.png

為了解決這個問題所以才出現(xiàn)了一個新的隊列-循環(huán)隊列

二、循環(huán)隊列

我們先給出隊列的圖解形式

5-循環(huán)隊列.png

有了循環(huán)隊列的基本實現(xiàn)，我們思考一個問題，在之前我們可以根據(jù)rear直接得到當(dāng)前隊列是否為空和是否已滿。那么在循環(huán)隊列里面還可以這樣嘛？當(dāng)然不可以，我們需要考慮font和rear的位置關(guān)系來判斷。我們看下面兩種情況：

6-判斷位置.png

一種是隊列為空的時候，front和rear都指向同一個位置。一種是隊列已滿的時候，front和rear指向的元素緊鄰。

我們可以使用下面的公式來判斷

7-計算隊列長度的公式.png

我們代碼實現(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();
}

然后是接口的實現(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é)

對于隊列主要在于面試中常見的算法題，因為概念非常容易理解，我們只要根據(jù)當(dāng)前實現(xiàn)的代碼進(jìn)行一些變化就好。謝謝大家的關(guān)注。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

深入分析數(shù)據(jù)結(jié)構(gòu)中的隊列（java語言實現(xiàn)）

深入分析數(shù)據(jù)結(jié)構(gòu)中的隊列（java語言實現(xiàn)）

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

深入分析數(shù)據(jù)結(jié)構(gòu)中的隊列（java語言實現(xiàn)）

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av