数据结构与算法学习笔记三---队列的链式存储表示和实现(C++)

目录

前言

1.队列的概念

2.队列的表示和实现

1.定义

2.初始化

​编辑

3.销毁队列

4.清空队列

5.队列判空

6.队列长度

7.获取队头元素

8.入队

9.出队

10.遍历

11.完整代码

---

前言

    这篇博客主要讲的是对队列的链式存储。

1.队列的概念

        队列是一种访问受限的线性表。仅允许在表的一端进行插入操作，在表的另一端进行删除操作。和日常生活中的排队是一致的，最先进入队列的元素最早离开。插入的一端称为队头(front)，删除的一端称为队尾(rear)。

        队列的示意图如下：

        图1.队列的示意图

2.队列的表示和实现

1.定义

        我们使用指针我们使用指向结点元素的指针分别表示队列的队头和队尾。

typedef int ElemType;
typedef struct QNode{
    ElemType data;
    struct QNode * next;
}QNode,*QueuePtr;

typedef struct {
    QueuePtr  front,rear;
}LinkQueue;

2.初始化

        链队列的初始化是构造一个只有一个头结点的空队，使队头和队尾指针指向次节点，并将节点的指针置为NULL。如下图2所示。

        图2.链队列的操作示意图

队列的初始化代码如下：

//初始化
Status initLinkQueue(LinkQueue *queue) {
    queue->front = queue->rear = new QNode;
    if (!queue->front) {
        return 0; // 内存分配失败
    }
    queue->front->next = NULL;
    return 1;
}

3.销毁队列

        为链队列增加销毁方法相对简单，只需释放链表中的所有节点即可。

// 销毁队列
Status destroyQueue(LinkQueue *queue) {
    QueuePtr p, q;
    p = queue->front;
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    queue->front = queue->rear = NULL;
    return 1;
}

4.清空队列

        清空队列的方法类似于销毁队列，但是不释放头结点。可以通过循环释放除头结点外的所有节点，并将头结点的 front 和 rear 指针重新指向头结点。

// 清空队列
Status clearQueue(LinkQueue *queue) {
    QueuePtr p, q;
    p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    queue->front->next = NULL; // 确保头结点的 next 指针为空，即队列为空
    // 注意：这里不释放 queue->front，因为它是队列的永久头节点
    queue->rear = queue->front; // 重新设置队尾指针
    return 1;
}

5.队列判空

        当对头和队尾相同的时候，队列为空。

//判空
Status isEmpty(LinkQueue *queue) {
    return queue->front->next == NULL; // 如果头指针的下一个节点为空，则队列为空
}

6.队列长度

        可以通过遍历队列中的元素来计算队列的长度。

// 求队列长度
int queueLength(LinkQueue *queue) {
    int length = 0;
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

7.获取队头元素

              获取链队列头元素的时候，首先要判断链队列是否是空队列，如果队列为空，不操作；否则，获取队列的头结点的下一个元素即可（因为我们这里用到了头结点，头结点的数据域是不可用使用的）。

//获取队列头元素
Status getHead(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    *e = queue->front->next->data;
    return 1;
}

8.入队

        入队的过程其实是生成一个新的节点，并且修改尾指针，并且把尾指针设置称为新的节点。

//入队
Status enQueue(LinkQueue *queue, ElemType e) {
    QueuePtr p = new QNode;
    if (!p) {
        return 0; // 内存分配失败
    }
    p->data = e;
    p->next = NULL;
    queue->rear->next = p;
    queue->rear = p;
    return 1;
}

9.出队

        连队列的出队首先是判断链队列是否为空，如果为空，则不操作；否则取出表头元素，修改头指针。

//出队
Status deQueue(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    QueuePtr p = queue->front->next;
    *e = p->data;
    queue->front->next = p->next;
    if (queue->rear == p) {
        queue->rear = queue->front; // 如果出队后队列为空，修改队尾指针
    }
    delete p;
    return 1;
}

10.遍历

        这里当队头和队尾相同的时候，链队列即为空队列。

// 遍历队列
void traverseLinkQueue(LinkQueue *queue) {
    if (isEmpty(queue)) {
        cout << "Queue is empty." << endl;
        return;
    }
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        cout << p->data << " "; // 输出队列中的元素
        p = p->next;
    }
    cout << endl; // 输出完毕后换行
}

11.完整代码

#include <iostream>
using namespace std;

typedef int ElemType;
typedef int Status;
typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr  front, rear;
} LinkQueue;

//初始化
Status initLinkQueue(LinkQueue *queue) {
    queue->front = queue->rear = new QNode;
    if (!queue->front) {
        return 0; // 内存分配失败
    }
    queue->front->next = NULL;
    return 1;
}
// 清空队列
Status clearQueue(LinkQueue *queue) {
    QueuePtr p, q;
    p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    queue->front->next = NULL; // 确保头结点的 next 指针为空，即队列为空
    // 注意：这里不释放 queue->front，因为它是队列的永久头节点
    queue->rear = queue->front; // 重新设置队尾指针
    return 1;
}

//判空
Status isEmpty(LinkQueue *queue) {
    return queue->front->next == NULL; // 如果头指针的下一个节点为空，则队列为空
}
// 求队列长度
int queueLength(LinkQueue *queue) {
    int length = 0;
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}



//入队
Status enQueue(LinkQueue *queue, ElemType e) {
    QueuePtr p = new QNode;
    if (!p) {
        return 0; // 内存分配失败
    }
    p->data = e;
    p->next = NULL;
    queue->rear->next = p;
    queue->rear = p;
    return 1;
}

//出队
Status deQueue(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    QueuePtr p = queue->front->next;
    *e = p->data;
    queue->front->next = p->next;
    if (queue->rear == p) {
        queue->rear = queue->front; // 如果出队后队列为空，修改队尾指针
    }
    delete p;
    return 1;
}

//获取队列头元素
Status getHead(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    *e = queue->front->next->data;
    return 1;
}
// 遍历队列
void traverseLinkQueue(LinkQueue *queue) {
    if (isEmpty(queue)) {
        cout << "Queue is empty." << endl;
        return;
    }
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        cout << p->data << " "; // 输出队列中的元素
        p = p->next;
    }
    cout << endl; // 输出完毕后换行
}

int main(int argc, const char * argv[]) {
    LinkQueue queue;
    cout<<"链队列初始化中..."<<endl;
    if (initLinkQueue(&queue)) {
        cout<<"链队列初始化成功"<<endl;
    }
    cout<<"链队列判空和长度..."<<endl;
    cout<<"队列长度:"<<queueLength(&queue)<<endl;
    if (isEmpty(&queue)) {
        cout<<"队列为空"<<endl;
    }
    // 入队
    enQueue(&queue, 1);
    enQueue(&queue, 2);
    enQueue(&queue, 3);
    traverseLinkQueue(&queue);
    ElemType head;
    if (getHead(&queue, &head)) {
        cout<<"队头指针:"<<head<<endl;
    }
    cout<<"出队测试......"<<endl;
    int element;
    if (deQueue(&queue, &element)) {
        cout<<"出队列成功,出队元素:"<<element<<endl;
    }
    cout<<"出队之后的队列......"<<endl;
    traverseLinkQueue(&queue);
    cout<<"清空队列......"<<endl;
    if (clearQueue(&queue)) {
        cout<<"队列清空成功,队列长度:"<<queueLength(&queue)<<endl;
    }
    // 出队并打印
    ElemType e;
    while (!isEmpty(&queue)) {
        deQueue(&queue, &e);
        cout << e << " ";
    }
    cout << endl;
    
    return 0;
}

---