隊(duì)列

2018年10月31日

隊(duì)列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)

1够滑,隊(duì)列的鏈表實(shí)現(xiàn)

public class ListQueue<Item> implements Iterable<Item> {
    private class Node {
        Item item;
        Node next;
    }

    private Node first;
    private Node last;
    private int N;

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item item) {
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) {
            first = last;
        } else {
            oldLast.next = last;
        }
        N++;
    }

    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        if (isEmpty()) {
            last = null;
        }
        N--;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ListIterator(first);
    }

    private class ListIterator implements Iterator<Item> {
        private Node current;

        public ListIterator(Node first) {
            current = first;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

2添怔,隊(duì)列的數(shù)組實(shí)現(xiàn)

public class ResizingArrayQueue<Item> implements Iterable<Item> {
    private Item[] a = (Item[]) new Object[2];
    private int N;
    private int first;
    private int last;

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[(first + i) % a.length];
        }
        a = temp;
        first = 0;
        last = N;
    }

    public void enqueue(Item item) {
        if (N == a.length) {
            resize(2 * a.length);
        }
        a[last++] = item;
        if (last == a.length) {
            //環(huán)形數(shù)組,到底了從頭計(jì)數(shù)
            last = 0;
        }
        N++;
    }

    public Item dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item item = a[first];
        //避免對(duì)象游離续徽,即保存一個(gè)不需要的對(duì)象的引用
        a[first] = null;
        first++;
        N--;
        if (first == a.length) {
            //環(huán)形數(shù)組畏妖,到底了從頭開始
            first = 0;
        }
        if (N > 0 && N == a.length / 4) {
            resize(a.length / 2);
        }
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ArrayIterator();
    }

    private class ArrayIterator implements Iterator<Item> {
        private int i = 0;

        @Override
        public boolean hasNext() {
            return i < N;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item item = a[(first + i) % a.length];
            i++;
            return item;
        }
    }
}

3,隊(duì)列的應(yīng)用

  • 圓圈中最后剩下的數(shù)字
    題目:0, 1, …, n-1這n個(gè)數(shù)字排成一個(gè)圓圈踢代,從數(shù)字0開始每次從這個(gè)圓圈里刪除第m個(gè)數(shù)字盲憎。求出這個(gè)圓圈里剩下的最后一個(gè)數(shù)字。
   public int lastRemainingSolution(int n, int m) {
       Queue<Integer> queue = new LinkedList<>();
       for (int i = 0; i < n; i++) {
           queue.offer(i);
       }
       int count = 0;
       int result = -1;
       while (!queue.isEmpty()) {
           if (count == m - 1) {
               result = queue.poll();
               count = 0;
           }
           if (!queue.isEmpty()) {
               queue.offer(queue.poll());
           }
           count++;
       }
       return result;
   }
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末胳挎,一起剝皮案震驚了整個(gè)濱河市饼疙,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌慕爬,老刑警劉巖窑眯,帶你破解...
    沈念sama閱讀 211,639評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異医窿,居然都是意外死亡磅甩,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,277評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門姥卢,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)卷要,“玉大人渣聚,你說(shuō)我怎么就攤上這事∩妫” “怎么了奕枝?”我有些...
    開封第一講書人閱讀 157,221評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)瓶堕。 經(jīng)常有香客問(wèn)我倍权,道長(zhǎng),這世上最難降的妖魔是什么捞烟? 我笑而不...
    開封第一講書人閱讀 56,474評(píng)論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮当船,結(jié)果婚禮上题画,老公的妹妹穿的比我還像新娘。我一直安慰自己德频,他們只是感情好苍息,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,570評(píng)論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著壹置,像睡著了一般竞思。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上钞护,一...
    開封第一講書人閱讀 49,816評(píng)論 1 290
  • 那天盖喷,我揣著相機(jī)與錄音,去河邊找鬼难咕。 笑死课梳,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的余佃。 我是一名探鬼主播暮刃,決...
    沈念sama閱讀 38,957評(píng)論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼爆土!你這毒婦竟也來(lái)了椭懊?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,718評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤步势,失蹤者是張志新(化名)和其女友劉穎氧猬,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體立润,經(jīng)...
    沈念sama閱讀 44,176評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡狂窑,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,511評(píng)論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了桑腮。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片泉哈。...
    茶點(diǎn)故事閱讀 38,646評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出丛晦,到底是詐尸還是另有隱情奕纫,我是刑警寧澤,帶...
    沈念sama閱讀 34,322評(píng)論 4 330
  • 正文 年R本政府宣布烫沙,位于F島的核電站匹层,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏锌蓄。R本人自食惡果不足惜升筏,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,934評(píng)論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望瘸爽。 院中可真熱鬧您访,春花似錦、人聲如沸剪决。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,755評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)柑潦。三九已至享言,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間渗鬼,已是汗流浹背览露。 一陣腳步聲響...
    開封第一講書人閱讀 31,987評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留譬胎,地道東北人肛循。 一個(gè)月前我還...
    沈念sama閱讀 46,358評(píng)論 2 360
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像银择,于是被迫代替她去往敵國(guó)和親多糠。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,514評(píng)論 2 348

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

  • 原文鏈接:深入剖析java并發(fā)之阻塞隊(duì)列LinkedBlockingQueue與ArrayBlockingQueu...
    Walter_Hu閱讀 715評(píng)論 0 0
  • 0.目錄 1.優(yōu)先隊(duì)列ADT 2.幾種實(shí)現(xiàn) 3.二叉堆 4.d-堆 5.左式堆 6.斜堆 7.二項(xiàng)隊(duì)列 8.斐波那...
    王偵閱讀 3,067評(píng)論 1 2
  • 早上起來(lái)被鬧鐘給弄醒了浩考,其實(shí)睡眠質(zhì)量不是很好夹孔。鬧鈴雖然響了,但是還是不想起來(lái)析孽,因?yàn)樗貌皇呛芎么钌恕W罱哺忻傲耍那?..
    巴克0000閱讀 139評(píng)論 0 0
  • 如果我喜歡你的時(shí)候 你正巧也歡喜著我 這樣真好可是呀 浪漫的事只存在想象里 現(xiàn)實(shí)里沒(méi)有剛好的相知 明知的不可能 偏...
    子禾啊閱讀 256評(píng)論 0 6
  • 文/沛花仙子 上一篇《這個(gè)年袜瞬,你在哪里過(guò)》 1. 元旦怜俐,是陽(yáng)歷年的一月一號(hào),陽(yáng)歷新的一年的開始邓尤。但是拍鲤,人們的心理上...
    沐芷鯉閱讀 779評(píng)論 6 2