本系列博客習(xí)題來自《算法(第四版)》豪墅，算是本人的讀書筆記，如果有人在讀這本書的黔寇，歡迎大家多多交流偶器。為了方便討論，本人新建了一個微信群(算法交流)缝裤，想要加入的屏轰，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外憋飞，本人的個人博客 http://www.kyson.cn 也在不停的更新中霎苗，歡迎一起討論

算法(第4版)

知識點(diǎn)

• 雙端隊列Deque

題目

1.3.33 Deque。一個雙向隊列(或者稱為deque)和楅蛔觯或隊列類似唁盏，但它同時支持在兩端添加或刪除元素。Deque能夠存儲一組元素并支持如下API检眯。

API for a generic double-ended queue

1.3.33 Deque. A double-ended queue or deque (pronounced “deck”) is like a stack or a queue but supports adding and removing items at both ends. A deque stores a collec- tion of items and supports the following API: Write a class Deque that uses a doubly-linked list to implement this API and a class ResizingArrayDeque that uses a resizing array.

分析

雙端隊列就是一個兩端都是結(jié)尾的隊列锰瘸。隊列的每一端都可以插入數(shù)據(jù)項和移除數(shù)據(jù)項驴党。這些方法可以叫作insertLeft()和insertRight()，以及removeLeft()和removeRight()获茬。如果嚴(yán)格禁止調(diào)用insertLeft()和removeLeft()方法（或禁用右段的操作），雙端隊列功能就和棧一樣倔既。禁止調(diào)用insertLeft()和removeRight()（或相反的另一對方法）恕曲，它的功能就和隊列一樣了。雙端隊列與棽秤浚或隊列相比佩谣，是一種多用途的數(shù)據(jù)結(jié)構(gòu)，在容器類庫中有時會用雙端隊列來提供棧和隊列兩種功能实蓬。

• Java中的雙端隊列類
  Deque.java：Java的Util庫自帶Deque類茸俭，因此可以直接new一個Deque對象吊履，大家可以找相關(guān)教程查看Deque的用法
• Objective-C中的雙端隊列
  CFArray.C：是CoreFoundation框架中的數(shù)組實(shí)現(xiàn)類，它就通過Deque實(shí)現(xiàn)的调鬓。關(guān)于CoreFoundation框架就不多說了艇炎，iOS開發(fā)的小伙伴應(yīng)該都知道。

分析

本人所有簡書的算法文章詳細(xì)分析已經(jīng)移入小專欄：算法四習(xí)題詳解腾窝，歡迎大家訂閱

答案

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

    private Item[] a;

    private int head = 1;
    private int tail = 1;

    public boolean isEmpty() {
        return head == tail;
    }

    public ResizingArrayDeque2() {
        a = (Item[]) (new Object[2]);
    }

    public int size() {
        return tail - head;
    }

    public void pushLeft(Item item) {
        if (head == 0) {
            resize(3 * size());
        }
        a[--head] = item;
    }

    private void resize(int max) {
        if (max < 3) {
            max = 3;
        }
        Item tmp[] = (Item[]) new Object[max];
        int j = max / 3;

        for (int i = head; i < tail; i++) {
            tmp[j++] = a[i];
        }
        a = tmp;
        head = max / 3;
        tail = j;
    }

    public void pushRight(Item item) {
        if (tail == a.length) {
            resize(3 * size());
        }
        a[tail++] = item;
    }

    public Item popLeft() {
        if (isEmpty()) {
            return null;
        }
        if (size() * 6 < a.length) {
            resize(size() * 3);
        }
        return a[head++];
    }

    public Item popRight() {
        if (isEmpty()) {
            return null;
        }
        if (size() * 6 < a.length) {
            resize(size() * 3);
        }
        return a[--tail];
    }

    public Iterator<Item> iterator() {
        return new DequeIterator();
    }

    private class DequeIterator implements Iterator<Item> {

        private int index = head;

        public boolean hasNext() {
            return index < tail;
        }

        public Item next() {
            Item x = a[index++];
            return x;
        }

        public void remove() {

        }

    }

    public static void main(String[] args) {
        ResizingArrayDeque2<String> deque = new ResizingArrayDeque2<String>(10);
        deque.pushRight("我");
        deque.pushRight("的");
        deque.pushRight("名字");
        deque.pushRight("叫頂級程序員不穿女裝");
        deque.pushRight("微博:https://m.weibo.cn/p/1005056186766482");

        for (String string : deque) {
            System.out.println(string);
        }
        System.out.println("===========================");

        ResizingArrayDeque2<String> deque1 = new ResizingArrayDeque2<String>(10);
        deque1.pushLeft("我");
        deque1.pushLeft("的");
        deque1.pushLeft("名字");
        deque1.pushLeft("叫頂級程序員不穿女裝");
        deque1.pushLeft("微博:https://m.weibo.cn/p/1005056186766482");

        for (String string : deque1) {
            System.out.println(string);
        }
        System.out.println("===========================");

        deque.popLeft();

        for (String string : deque) {
            System.out.println(string);
        }

        System.out.println("===========================");
        deque1.popRight();

        for (String string : deque1) {
            System.out.println(string);
        }

    }

}

代碼索引

ResizingArrayDeque2.java

視頻講解

廣告

我的首款個人開發(fā)的APP壁紙寶貝上線了缀踪，歡迎大家下載。

壁紙寶貝