數(shù)據(jù)結(jié)構與算法之隊列的實現(xiàn)

引言

隊列同樣是一種特殊的線性表清钥,其插入和刪除的操作分別在表的兩端進行涯保,隊列的特點就是先進先出(FIFO)。我們把向隊列中插入元素的過程稱為入隊(Enqueue)空郊,刪除元素的過程稱為出隊(Dequeue)并把允許入隊的一端稱為隊尾宫莱,允許出的的一端稱為隊頭丈攒,沒有任何元素的隊列則稱為空隊.它的結(jié)構如下:


隊列結(jié)構.png

隊列實現(xiàn)

它的實現(xiàn)核心就是入隊和出隊操作,成員變量有隊頭、隊尾指針和隊列大小,Node節(jié)點是單向節(jié)點即可授霸。

package queue;

import List.Node;

/**
 * Created by chenming on 16/12/29.
 * 隊列的實現(xiàn)也可以由只對收尾操作的LinkedList實現(xiàn)巡验,這里給出它的基本實現(xiàn)原理
 */

public class Queue<T> {
    private Node<T> mHead;//隊頭指針
    private Node<T> mTail;//隊尾部指針
    private int mSize;//大小

    public Queue() {
        clear();
    }

    /**
     * 入隊操作
     *
     * @param item
     */
    public void enquene(T item) {
        Node<T> node = new Node<>(item, null, null);
        if (isEmpty()) {
            //隊列為空,從head插入
            mHead = node;
        } else {
            //隊列不為空,從尾部插入
            mTail.next = node;
        }

        mTail = node;//尾部指針后移
        mSize++;
    }

    /**
     * 出隊
     *
     * @return
     */
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }
        T item = mHead.mData;
        mHead = mHead.next;
        if (mHead == null) {
            mTail = null;//最后一個元素出隊, 更新tail指向null
        }
        mSize--;
        return item;

    }

    /**
     * 獲取隊列尾部元素,不刪除
     *
     * @return
     */
    public T tail() {
        return isEmpty() ? null : mTail.mData;
    }

    /**
     * 獲取隊列頭部元素,不刪除
     *
     * @return
     */
    public T head() {
        return isEmpty() ? null : mHead.mData;
    }

    public T getItem(int index) {
        if (index < 0 || index >= mSize) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> node = mHead;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.mData;
    }

    public boolean contains(T item) {
        for (int i = 0; i < size(); i++){
            if(getItem(i).equals(item)){
                return true;
            }
        }
        return false;
    }

    /**
     * 清空
     */
    public void clear() {
        mHead = mTail = null;
        mSize = 0;
    }

    /**
     * 判空
     *
     * @return
     */
    public boolean isEmpty() {
        return mHead == null && mTail == null;
    }

    public int size() {
        return mSize;
    }
}

其實隊列的本質(zhì)還是線性表,只是它的尾部只能添加元素碘耳,頭部只能刪除元素显设,它主要應用在生產(chǎn)者消費者模型中,在其中扮演緩沖區(qū)的角色辛辨。這里涉及到多線程編程的阻塞線程概念捕捂,具體的原理會在以后的多線程專題中詳細說明。代碼地址:數(shù)據(jù)結(jié)構與算法學習JAVA描述GayHub地址

最后編輯于
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末斗搞,一起剝皮案震驚了整個濱河市指攒,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌僻焚,老刑警劉巖允悦,帶你破解...
    沈念sama閱讀 211,817評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異虑啤,居然都是意外死亡隙弛,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,329評論 3 385
  • 文/潘曉璐 我一進店門咐旧,熙熙樓的掌柜王于貴愁眉苦臉地迎上來驶鹉,“玉大人,你說我怎么就攤上這事铣墨∈衣瘢” “怎么了?”我有些...
    開封第一講書人閱讀 157,354評論 0 348
  • 文/不壞的土叔 我叫張陵伊约,是天一觀的道長姚淆。 經(jīng)常有香客問我,道長屡律,這世上最難降的妖魔是什么是复? 我笑而不...
    開封第一講書人閱讀 56,498評論 1 284
  • 正文 為了忘掉前任产捞,我火速辦了婚禮蚤蔓,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘佳鳖。我一直安慰自己,他們只是感情好媒惕,可當我...
    茶點故事閱讀 65,600評論 6 386
  • 文/花漫 我一把揭開白布系吩。 她就那樣靜靜地躺著,像睡著了一般妒蔚。 火紅的嫁衣襯著肌膚如雪穿挨。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,829評論 1 290
  • 那天肴盏,我揣著相機與錄音科盛,去河邊找鬼。 笑死菜皂,一個胖子當著我的面吹牛贞绵,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播幌墓,決...
    沈念sama閱讀 38,979評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼但壮,長吁一口氣:“原來是場噩夢啊……” “哼冀泻!你這毒婦竟也來了常侣?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,722評論 0 266
  • 序言:老撾萬榮一對情侶失蹤弹渔,失蹤者是張志新(化名)和其女友劉穎胳施,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體肢专,經(jīng)...
    沈念sama閱讀 44,189評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡舞肆,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,519評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了博杖。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片椿胯。...
    茶點故事閱讀 38,654評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖剃根,靈堂內(nèi)的尸體忽然破棺而出哩盲,到底是詐尸還是另有隱情,我是刑警寧澤狈醉,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布廉油,位于F島的核電站,受9級特大地震影響苗傅,放射性物質(zhì)發(fā)生泄漏抒线。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,940評論 3 313
  • 文/蒙蒙 一渣慕、第九天 我趴在偏房一處隱蔽的房頂上張望嘶炭。 院中可真熱鬧抱慌,春花似錦、人聲如沸眨猎。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,762評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽宵呛。三九已至单匣,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間宝穗,已是汗流浹背户秤。 一陣腳步聲響...
    開封第一講書人閱讀 31,993評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留逮矛,地道東北人鸡号。 一個月前我還...
    沈念sama閱讀 46,382評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像须鼎,于是被迫代替她去往敵國和親鲸伴。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,543評論 2 349

推薦閱讀更多精彩內(nèi)容