双端队列，英文名deque（读音同deck）。因为今天做题用stl投机取巧疯了（本应该是链表专题练习），所以补点训练量。别到时候考试不让用stl容器那就麻烦了。

参照了The Algorithms

基本实现

链表

因为数组维护太麻烦了，所以我们以双向链表为基础。

template <class ValueType>
struct Node {
    ValueType data {};
    std::shared_ptr<Node<ValueType>> next;
    std::shared_ptr<Node<ValueType>> prev;
};

框架

我们写想好我们的双端队列要实现哪些功能，搭建好类的框架。

template <class ValueType>
class deque {

  private:
    std::shared_ptr<Node<ValueType>> front;
    std::shared_ptr<Node<ValueType>> rear;
    std::size_t size {0};

  public:
    void clear();
    bool empty() const;
    void push_front(const ValueType& item);
    void push_back(const ValueType& item);
    void pop_front();
    void pop_back();
    ValueType front() const;
    ValueType rear() const;
}

完整具体实现

template <class ValueType>
struct Node {
    ValueType data {};
    std::shared_ptr<Node<ValueType>> next;
    std::shared_ptr<Node<ValueType>> prev;
};

template <class ValueType>
class deque {

  private:
    std::shared_ptr<Node<ValueType>> front;
    std::shared_ptr<Node<ValueType>> rear;
    size_t size_ = 0;

  public:

    void clear() {
        front = nullptr;
        rear = nullptr;
        size = 0;
    }

    bool empty() const {
        return size == 0;
    }

    void push_front(const ValueType& item) {
        auto new_node = std::make_shared<Node<ValueType>>;
        new_node->data = item;
        new_node->next = nullptr;

        if (empty()) {
            front = new_node;
            rear = new_node;
        } else {
            new_node->next = front;
            front->prev = new_node;
            front = new_node;
        }
        size++;
    }

    void push_back(const ValueType& item) {
        auto new_node = std::make_shared<Node<ValueType>>;
        new_node->data = item;

        if (empty()) {
            front = new_node;
            rear = new_node;
        } else {
            rear->next = new_node;
            new_node->prev = rear;
            rear = new_node;
        }
        size++;
    }

    void pop_front() {
        if (empty()) {
            return;
        }
        if (size == 1) {
            front = nullptr;
            rear = nullptr;
        } else {
            front = front->next;
            front->prev = nullptr;
        }
        size--;
    }

    void pop_back() {
        if (empty()) {
            return;
        }
        if (size == 1) {
            front = nullptr;
            rear = nullptr;
        } else {
            rear = rear->prev;
            rear->next = nullptr;
        }
        size--;
    } 

    ValueType front() const {
        return front->data;
    }

    ValueType rear() const {
        return rear->data;
    }
}

stl确实强大，智能指针可以让人免于c语言内存管理的烦恼。

总结

虽然简单，但还是有几个坑点。

1. 压入要分情况，空队列和非空队列。
2. 弹出要分情况，弹出之后是空队列还是非空队列。可以通过'size == 1'来判断。
3. 每个操作都要注意是否需要对'size'进行操作。

---

开个小坑，日后实现个c语言版本的。