本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 双端队列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.

分析

双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。这些方法可以叫作insertLeft()和insertRight()，以及removeLeft()和removeRight()。如果严格禁止调用insertLeft()和removeLeft()方法（或禁用右段的操作），双端队列功能就和栈一样。禁止调用insertLeft()和removeRight()（或相反的另一对方法），它的功能就和队列一样了。双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。

• Java中的双端队列类
  Deque.java：Java的Util库自带Deque类，因此可以直接new一个Deque对象，大家可以找相关教程查看Deque的用法
• Objective-C中的双端队列
  CFArray.C：是CoreFoundation框架中的数组实现类，它就通过Deque实现的。关于CoreFoundation框架就不多说了，iOS开发的小伙伴应该都知道。

分析

本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅

答案

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

视频讲解

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。

壁纸宝贝