C++利用链表模板类实现简易队列

首先我们需要了解链表和模板类，然后才能进一步学习如何利用链表模板类实现队列。

链表

链表是一种非常常用的数据结构，它通过“链”把一系列节点串在一起。每个节点包含一个存储数据的值和一个指向下一个节点的指针。链表可以分为单向链表和双向链表，其中单向链表中只能指向下一个节点，而双向链表中可以同时指向上一个和下一个节点。

下面是一个用C++实现单向链表的示例代码：

template<class T>
struct Node {
    T data;
    Node* next;
};

template<class T>
class LinkedList {
public:
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}

    void push_back(T data) {
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        if (!head) {
            head = newNode;
        }
        else {
            tail->next = newNode;
        }
        tail = newNode;
        size++;
    }

    void pop_front() {
        if (head == nullptr) return;

        Node<T>* oldHead = head;
        head = head->next;
        delete oldHead;

        if (head == nullptr) tail = nullptr;

        size--;
    }

    T front() const {
        return head->data;
    }

    T back() const {
        return tail->data;
    }

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

    int getSize() const {
        return size;
    }

private:
    Node<T>* head;
    Node<T>* tail;
    int size;
};

模板类

模板类是C++中的一种很有用的构件，它可以帮助我们实现泛型程序设计。模板类可以定义成员变量、成员函数和嵌套类等，同时可以接受任何数据类型作为其参数。

下面是一个用C++实现模板类的示例代码：

template<class T>
class Stack {
public:
    Stack() : top(-1) {}

    void push(T data) {
        arr[++top] = data;
    }

    T pop() {
        return arr[top--];
    }

private:
    static const int MAX_SIZE = 100;
    T arr[MAX_SIZE];
    int top;
};

队列

队列是一种先进先出的简单数据结构，通常可以用数组或链表来实现。我们可以利用链表模板类来实现自己的队列。

下面是一个用C++利用链表模板类实现队列的示例代码：

template<class T>
class Queue {
public:
    Queue() : linkedList(LinkedList<T>()) {}

    void enqueue(T data) {
        linkedList.push_back(data);
    }

    void dequeue() {
        linkedList.pop_front();
    }

    T front() const {
        return linkedList.front();
    }

    T back() const {
        return linkedList.back();
    }

    bool empty() const {
        return linkedList.empty();
    }

    int getSize() const {
        return linkedList.getSize();
    }

private:
    LinkedList<T> linkedList;
};

这样就实现了一个用链表模板类实现的队列。我们可以通过调用enqueue、dequeue、front等函数来操作队列。

此外，下面是一个用Queue类实现的示例程序：

int main() {
    Queue<int> q;

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);

    while (!q.empty()) {
        cout << q.front() << " ";
        q.dequeue();
    }

    return 0;
}

输出结果为：1 2 3 4

这是一个很简单的队列示例程序，它会把1、2、3、4依次加入队列中，并出队时按顺序输出。