算法與數(shù)據(jù)結(jié)構(gòu):棧,隊(duì)列,包及其鏈表實(shí)現(xiàn)

圖片來自 unsplash

棧 , 隊(duì)列 , 背包

  • **棧 : **棧 , 在之前的一篇文章里面已經(jīng)講過了 , 遵從先入后出原則 (FILO) .
  • **隊(duì)列 : **隊(duì)列 , 顧名思義 , 就像排隊(duì)一樣 , 先排隊(duì)的人先處理 , 遵從先入先出原則 (FIFO) .
  • **背包 : **在這里的背包 , 就像平時(shí)用的背包一樣 , 用來裝東西 , 但是里面的東西順序不重要 . 而 隊(duì)列 是有序的 . 得注意的是 , 背包 , 只能添加元素節(jié)點(diǎn) , 而不能刪除元素節(jié)點(diǎn) .

方法列表

  • 棧 ( Stack )
    • void push(Item item) : 添加一個(gè)元素節(jié)點(diǎn) .
    • Item pop() : 刪除棧頂元素節(jié)點(diǎn) .
    • boolean isEmpty() : 判斷棧是否為空 .
    • int size() : 返回棧長(zhǎng)度 .
  • 隊(duì)列 ( Queue )
    • void enqueue(Item item) : 加入新元素節(jié)點(diǎn)到隊(duì)列 .
    • Item dequeue() : 刪除最早進(jìn)入隊(duì)列的元素節(jié)點(diǎn) .
    • boolean isEmpty() : 判斷隊(duì)列是否為空 .
    • int size() : 返回隊(duì)列長(zhǎng)度 .
  • 背包 ( Bag )
    • void add(Item item) : 添加新元素節(jié)點(diǎn)到背包 .
    • boolean isEmpty() : 判斷背包是否為空 .
    • int size() : 返回背包大小 .

鏈表實(shí)現(xiàn)棧 , 隊(duì)列 , 背包

鏈表在之前的文章里已經(jīng)將過了 , 這里就不多說了 .

鏈表實(shí)現(xiàn)棧

public class Stack<Item> implements Iterable<Item> {

    private Node head = null;
    private int length = 0;

    public Stack(){}
    
    public void push(Item item) {
        Node node = new Node(item);
        node.next = this.head;
        this.head = node;
        length++;
    }

    public Item pop() {
        Node node = this.head;
        this.head = this.head.next;
        this.length--;
        return node.item;
    }

    public int size() {
        return this.length;
    }

    public boolean isEmpty() {
        return this.length == 0;
    }

    private class Node {
        public Item item;
        public Node next;

        public Node(Item item) {
            this.item = item;
        }
    }

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

    private class ListIterator<Item> implements Iterator<Item> {

        private Node current = head;

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

        @Override
        public Item next() {
            Item item = (Item) current.item;
            current = current.next;
            return item;
        }

        @Override
        public void remove() {}
    }

    @Override
    public Spliterator<Item> spliterator() {
        return null;
    }
}

鏈表實(shí)現(xiàn)隊(duì)列

public class Queue<Item> implements Iterable<Item> {

    private Node head = null; //最先入隊(duì)的元素
    private int length = 0; //隊(duì)列長(zhǎng)度
    private Node last = null; //最后入隊(duì)的元素

    private class Node {
        public Item item = null;
        public Node next = null;

        public Node(Item item) {
            this.item = item;
        }
    }

    public Queue() {
    }

    public boolean isEmpty() {
        return this.length == 0;
    }

    public int size() {
        return this.length;
    }

    public void enqueue(Item item) {
        Node node = new Node(item);

        if (isEmpty()) {
            this.head = this.last = node;
        }else{
            this.last.next = node;
            this.last = node;
        }
        this.length++;
    }

    public Item dequeue() {
        Item item = this.head.item;
        this.head = this.head.next;
        if (size()==1){
            last =null;
        }
        this.length--;
        return item;
    }

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

    private class ListIterator<Item> implements Iterator<Item> {

        private Node current = head;

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

        @Override
        public Item next() {
            Item item = (Item) current.item;
            current = current.next;
            return item;
        }

        @Override
        public void remove() {}
    }
}

鏈表實(shí)現(xiàn)背包

public class Bag<Item> implements Iterable<Item> {

    private int length = 0;
    private Node head;

    public Bag(){}

    private class Node {
        public Item item = null;
        public Node next = null;

        public Node(Item item) {
            this.item = item;
        }
    }

    public int size(){
        return this.length;
    }

    public boolean isEmpty(){
        return this.length == 0;
    }

    public void add(Item item){
        Node node = new Node(item);
        if (isEmpty()){
            this.head = node;
        }else {
            Node current = this.head;
            while (current.next!=null){
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
    }

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

    private class ListIterator<Item> implements Iterator<Item> {

        private Node current = head;

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

        @Override
        public Item next() {
            Item item = (Item) current.item;
            current = current.next;
            return item;
        }

        @Override
        public void remove() {}
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子歌懒,更是在濱河造成了極大的恐慌科平,老刑警劉巖闻蛀,帶你破解...
    沈念sama閱讀 222,627評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件潘飘,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡崩掘,警方通過查閱死者的電腦和手機(jī)吼驶,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,180評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門惩激,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人蟹演,你說我怎么就攤上這事风钻。” “怎么了酒请?”我有些...
    開封第一講書人閱讀 169,346評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵骡技,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我羞反,道長(zhǎng)布朦,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,097評(píng)論 1 300
  • 正文 為了忘掉前任昼窗,我火速辦了婚禮是趴,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘澄惊。我一直安慰自己唆途,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,100評(píng)論 6 398
  • 文/花漫 我一把揭開白布缤削。 她就那樣靜靜地躺著窘哈,像睡著了一般吹榴。 火紅的嫁衣襯著肌膚如雪亭敢。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,696評(píng)論 1 312
  • 那天图筹,我揣著相機(jī)與錄音帅刀,去河邊找鬼。 笑死远剩,一個(gè)胖子當(dāng)著我的面吹牛扣溺,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播瓜晤,決...
    沈念sama閱讀 41,165評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼锥余,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了痢掠?” 一聲冷哼從身側(cè)響起驱犹,我...
    開封第一講書人閱讀 40,108評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤嘲恍,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后雄驹,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體佃牛,經(jīng)...
    沈念sama閱讀 46,646評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,709評(píng)論 3 342
  • 正文 我和宋清朗相戀三年医舆,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了俘侠。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,861評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡蔬将,死狀恐怖爷速,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情霞怀,我是刑警寧澤遍希,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站里烦,受9級(jí)特大地震影響凿蒜,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜胁黑,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,196評(píng)論 3 336
  • 文/蒙蒙 一废封、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧丧蘸,春花似錦漂洋、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,698評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至弟孟,卻和暖如春贝咙,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背拂募。 一陣腳步聲響...
    開封第一講書人閱讀 33,804評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工庭猩, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人陈症。 一個(gè)月前我還...
    沈念sama閱讀 49,287評(píng)論 3 379
  • 正文 我出身青樓蔼水,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親录肯。 傳聞我的和親對(duì)象是個(gè)殘疾皇子趴腋,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,860評(píng)論 2 361

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

  • 上一章進(jìn)行了ArrayList源碼分析,這一章分析一下另一個(gè)重要的List集合LinkedList。 Linked...
    wo883721閱讀 555評(píng)論 0 0
  • 目錄 1. 棧和隊(duì)列1.用兩個(gè)隊(duì)列實(shí)現(xiàn)棧2.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列3.實(shí)現(xiàn)一個(gè)棧优炬,可以用常數(shù)級(jí)時(shí)間找出棧中的最小值4.判...
    MigrationUK閱讀 3,040評(píng)論 4 20
  • LinkedList簡(jiǎn)介 首先看看LinkedList與Collection的關(guān)系: LinkedList的繼承...
    聶叼叼閱讀 640評(píng)論 0 1
  • 最終他們結(jié)婚了疏叨,我也遇到了疼我愛我的男朋友。人生本來就沒有相欠穿剖,別人對(duì)你付出蚤蔓,是因?yàn)樽约合矚g,你對(duì)別人付出糊余,是因?yàn)?..
    小白兔123456閱讀 114評(píng)論 0 1
  • 他說贬芥,這是我玩的最后一把了吐辙,我要A了。 他說蘸劈,游戲畢竟只是游戲昏苏,戰(zhàn)力刷的再高,工資也不能多漲一分威沫。 他說贤惯,我快結(jié)婚...
    鹿飲河閱讀 558評(píng)論 2 4