数据结构【链式队列】

基于链式存储结构的队列实现与分析

一、引言

队列作为一种重要的数据结构，在计算机科学的众多领域有着广泛应用，如操作系统中的任务调度、网络通信中的数据缓冲等。本文通过C++ 代码实现了一个基于链式存储结构的队列，并对其进行详细解析。

二、代码实现

（一）结构体定义

typedef struct node{
    int date;
    struct node* next;
}lstqu;
typedef struct nodeb {
    lstqu* front, * rear;
}qq;
qq* Q;

这里定义了两个结构体，lstqu 用于表示队列中的节点，每个节点包含一个数据域 date 和一个指向下一个节点的指针 next。qq 结构体用于表示整个队列，包含队头指针 front 和队尾指针 rear。

（二）初始化队列

qq* initqueue()
{
    lstqu* p;
    qq* Q;
    p = (lstqu*)malloc(sizeof(lstqu));
    Q = (qq*)malloc(sizeof(qq));
    Q->front = p;
    Q -> rear = p;
    return Q;
}

在 initqueue 函数中，首先为一个新的节点分配内存空间 p，然后为整个队列分配内存空间 Q。将队头和队尾指针都指向这个新创建的节点，这个节点作为队列的初始状态，此时队列中没有实际的数据元素。

（三）判断队列是否为空

int empty(qq*Q)
{
    if (Q->front == Q->rear) return 1;
    else return 0;
}

empty 函数通过判断队头指针和队尾指针是否相等来确定队列是否为空。如果相等，说明队列中没有元素，返回 1；否则返回 0。

（四）入队操作

void push(qq* Q, int x){
    lstqu* q = (lstqu*)malloc(sizeof(lstqu));
    q->date = x;
    q->next = NULL;
    Q->rear->next = q;
    Q->rear = q;
}

push 函数实现了入队操作。首先为新元素分配内存空间 q，将数据 x 存入节点的数据域，并将节点的 next 指针设为 NULL。然后将队尾节点的 next 指针指向新节点，最后更新队尾指针 rear 指向新节点。

（五）出队操作

int pop(qq* Q, int *x){
    lstqu* q = (lstqu*)malloc(sizeof(lstqu));
    if (empty(Q)) {
        cout << "队列已空\n";
        return 0;
    }
    q = Q->front->next;
    *x = q->date;
    Q->front->next = q->next;
    if (q->next == NULL){
        Q->front = Q->rear;
    }
    free(q);
    return 1;
}

pop 函数用于出队操作。首先检查队列是否为空，如果为空则输出提示信息并返回 0。否则，获取队头节点的下一个节点 q，将其数据域的值赋给 *x，然后将队头指针 front 的 next 指针指向下一个节点，即跳过要出队的节点。如果出队后队列变为空（即出队节点的 next 指针为 NULL），则更新队头指针 front 与队尾指针 rear 相等。最后释放出队节点的内存空间，并返回 1 表示操作成功。

（六）获取队头元素

int front(qq* Q, int* x) {
    lstqu* q = (lstqu*)malloc(sizeof(lstqu));
    if (empty(Q)) {
        cout << "队列已空\n";
        return 0;
    }
    *x = Q->front->next->date;
    return 1;
}

front 函数用于获取队头元素的值。同样先检查队列是否为空，若为空则输出提示并返回 0。否则，将队头节点的下一个节点的数据域值赋给 *x 并返回 1。

（七）打印队列

void printq(qq* Q){
    lstqu* q = Q->front->next;
    if (q == NULL) cout << "无";
    else {
        while (q!= NULL)
        {
            cout << q->date << " ";
            q = q->next;
        }
        cout << "打印好了" << endl;
    }
}

printq 函数用于打印队列中的所有元素。从队头节点的下一个节点开始，遍历整个队列，依次输出每个节点的数据域值，直到遇到 NULL 指针，表示遍历结束。

（八）主函数测试

结果如下：

三、总结

通过上述代码实现，我们成功构建了一个基于链式存储结构的队列，并通过测试函数验证了其基本操作的正确性。链式存储结构的队列在处理动态数据时具有灵活性，避免了顺序存储结构可能出现的溢出问题。然而，在实现过程中要注意内存的管理，及时释放不再使用的节点内存，以防止内存泄漏。同时，对于复杂的应用场景，还可以进一步优化和扩展队列的功能，如增加获取队列长度等操作。