HOME

双端队列的实现：双向链表实现

引言

双端队列（Deque）是一种抽象数据类型，允许在两端进行插入和删除操作的数据结构。与一般的队列相比，双端队列提供更灵活的操作方式。本文将探讨如何使用双向链表来实现双端队列，并通过具体的代码示例来展示其实现细节。

双端队列的特点

双端队列的主要特点是其两端的插入和删除操作，具体包括：

这些操作的实现基于双向链表结构，能够高效地支持双端队列的各种操作需求。

双向链表的基本概念

在讨论如何使用双向链表实现双端队列之前，首先需要了解双向链表的相关概念。双向链表是一种线性数据结构，其中每个节点包含三个部分：一个值（data）和两个指针（next 和 prev），分别指向下一个节点和前一个节点。

双端队列的结构设计

为了实现双端队列，我们需要定义一些基本的数据结构：

基于上述信息，我们首先定义一个节点类 Node 用于表示链表中的每个节点：

template <typename T>
class Node {
public:
    T data;
    Node<T>* next;
    Node<T>* prev;

    Node(T value) : data(value), next(nullptr), prev(nullptr) {}
};

接下来定义双端队列类 Deque，其中包含添加、删除和读取元素的方法：

template <typename T>
class Deque {
private:
    Node<T>* front;
    Node<T>* rear;

public:
    Deque() : front(nullptr), rear(nullptr) {}

    void pushFront(T value);
    void pushBack(T value);
    T popFront();
    T popBack();
    T getFront();
    T getBack();

    bool isEmpty();
};

双端队列的具体实现

pushFront 和 pushBack 方法

在双端队列中，我们可以轻松地向队首或队尾添加元素。我们定义了 pushFront 和 pushBack 两个方法来分别在头部和尾部插入新节点：

template <typename T>
void Deque<T>::pushFront(T value) {
    Node<T>* newNode = new Node<T>(value);
    if (isEmpty()) {
        front = rear = newNode;
    } else {
        newNode->next = front;
        front->prev = newNode;
        front = newNode;
    }
}

template <typename T>
void Deque<T>::pushBack(T value) {
    Node<T>* newNode = new Node<T>(value);
    if (isEmpty()) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        newNode->prev = rear;
        rear = newNode;
    }
}

popFront 和 popBack 方法

出队操作同样简单，我们只需要从头部或尾部移除节点并返回其值：

template <typename T>
T Deque<T>::popFront() {
    if (isEmpty()) return nullptr;

    Node<T>* temp = front;
    T value = front->data;
    front = front->next;
    if (front == nullptr) rear = nullptr;
    else front->prev = nullptr;
    delete temp;
    return value;
}

template <typename T>
T Deque<T>::popBack() {
    if (isEmpty()) return nullptr;

    Node<T>* temp = rear;
    T value = rear->data;
    rear = rear->prev;
    if (rear == nullptr) front = nullptr;
    else rear->next = nullptr;
    delete temp;
    return value;
}

getFront 和 getBack 方法

获取队首或队尾的元素也很简单，只需返回对应的节点值即可：

template <typename T>
T Deque<T>::getFront() {
    if (isEmpty()) return nullptr;
    return front->data;
}

template <typename T>
T Deque<T>::getBack() {
    if (isEmpty()) return nullptr;
    return rear->data;
}

isEmpty 方法

最后，我们定义了一个简单的检查队列是否为空的方法：

template <typename T>
bool Deque<T>::isEmpty() {
    return front == nullptr;
}

总结

通过上述实现，我们可以看到使用双向链表来构建双端队列是非常直观且高效的。这种方法不仅支持在两端进行插入和删除操作，而且通过简单的指针操作可以方便地对节点进行管理。这种设计使得双端队列能够灵活应对各种应用场景下的需求。