如何修改指定单链表类定义以实现Queue（队列）？

首先先修正原代码里的几个语法错误，不然根本无法正常编译运行：

• StringNode类里的stringNode* next要改成StringNode* next（类名大小写必须一致）
• 构造函数里的head == NULL是比较操作，要改成赋值head = NULL
• 析构函数声明多了分号，应该是~StringLinkedList() {

接下来，队列是**先进先出(FIFO)**结构，原单链表仅支持头部的增删操作，要适配队列需要做以下核心修改：

关键修改项 #

• 给StringLinkedList的私有成员添加尾指针StringNode* tail，用来快速定位队尾，避免每次入队都遍历整个链表
• 调整构造函数，同时初始化head和tail为NULL
• 添加入队方法void addBack(const string& e)，实现队尾插入元素（对应队列的enqueue操作）
• 原有的front()方法可直接作为获取队首元素的接口（对应队列的peek操作）
• 原有的removeFront()方法可直接作为出队操作（对应队列的dequeue操作），但要补充：移除队首后如果队列变空，需同步把尾指针置空

修改后的完整代码 #

#include <iostream>
#include <string>

using namespace std;

class StringNode {
private:
    string elem;
    StringNode* next; // 修正类名大小写错误

    friend class StringLinkedList;
};

class StringLinkedList {
public:
    // 初始化头尾指针
    StringLinkedList() : head(NULL), tail(NULL) {}

    // 修正析构函数语法错误
    ~StringLinkedList() {
        while (!empty()) {
            removeFront();
        }
    }

    bool empty() const {
        return head == NULL;
    }

    // 获取队首元素（队列peek操作）
    const string& front() const {
        return head->elem;
    }

    // 入队操作：队尾添加元素
    void addBack(const string& e) {
        StringNode* newNode = new StringNode;
        newNode->elem = e;
        newNode->next = NULL;

        if (empty()) {
            // 空队列时，头尾指针都指向新节点
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    // 出队操作：移除队首元素
    void removeFront() {
        StringNode* old = head;
        head = head->next;
        // 队列空了要同步置空尾指针
        if (empty()) {
            tail = NULL;
        }
        delete old;
    }

private:
    StringNode* head;
    StringNode* tail; // 添加尾指针
};

补充说明 #

• 队列的核心逻辑就是队尾入、队首出，添加尾指针后入队操作的时间复杂度从O(n)降到了O(1)，效率大幅提升
• 使用时，通过addBack入队、front查看队首、removeFront出队、empty判断队列是否为空，完全符合队列的使用习惯

内容的提问来源于stack exchange，提问作者thebig1