C++ 双向遍历队列实现 - 代码详解及示例

#include

template class Node { public: T data; Node* prev; Node* next; Node(T value) : data(value), prev(nullptr), next(nullptr) {} };

template class Deque { private: Node* front; Node* rear;

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

~Deque() {
    while (!isEmpty()) {
        removeFront();
    }
}

bool isEmpty() {
    return (front == nullptr);
}

void addFront(T value) {
    Node<T>* newNode = new Node<T>(value);

    if (isEmpty()) {
        front = rear = newNode;
    } else {
        front->prev = newNode;
        newNode->next = front;
        front = newNode;
    }
}

void addRear(T value) {
    Node<T>* newNode = new Node<T>(value);

    if (isEmpty()) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        newNode->prev = rear;
        rear = newNode;
    }
}

void removeFront() {
    if (isEmpty()) {
        std::cout << "Deque is empty." << std::endl;
        return;
    }

    Node<T>* temp = front;
    front = front->next;

    if (front != nullptr) {
        front->prev = nullptr;
    } else {
        rear = nullptr;
    }

    delete temp;
}

void removeRear() {
    if (isEmpty()) {
        std::cout << "Deque is empty." << std::endl;
        return;
    }

    Node<T>* temp = rear;
    rear = rear->prev;

    if (rear != nullptr) {
        rear->next = nullptr;
    } else {
        front = nullptr;
    }

    delete temp;
}

void display() {
    if (isEmpty()) {
        std::cout << "Deque is empty." << std::endl;
        return;
    }

    Node<T>* current = front;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

};

int main() { Deque deque;

deque.addFront(1);
deque.addFront(2);
deque.addRear(3);
deque.addRear(4);

deque.display(); // Output: 2 1 3 4

deque.removeFront();
deque.removeRear();

deque.display(); // Output: 1 3

return 0;

}

这个双向遍历的队列使用了双向链表实现。它具有以下功能：

• isEmpty()：检查队列是否为空。
• addFront(value)：在队列的前面添加一个元素。
• addRear(value)：在队列的后面添加一个元素。
• removeFront()：从队列的前面移除一个元素。
• removeRear()：从队列的后面移除一个元素。
• display()：显示队列中的所有元素。

在主函数中，我们创建了一个Deque对象，并进行了一些操作来测试队列的功能。最后，我们通过调用display()方法来显示队列中的所有元素。