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

目录

前言

1.队列的顺序存储方式的实现

1.定义

2.队列初始化

3.销毁

4.队列是否为空

5.队列长度

6.清空队列

7.队列头元素

8.入队

9.出队

10.完整代码

2.队列的链式存储方式的实现

1.定义

2.队列初始化

3.销毁

4.队列是否为空

5.队列长度

6.清空队列

7.队列头元素

8.入队

9.出队

10.完整代码

---

前言

    队列也是一中受限的线性表，只能在表的一段进行插入操作，在表的另外一段进行删除操作。和线性表一样，仍然是一对一的关系。存储结构也有两种方式：顺序队列和链队列。运算规则为先进先出。基本操作位入队或者出队，建空队列，判断队列为空或者队列已满等操作。

        队列在现实中也有着很多的应用场景，例如离散事件的模拟、操作系统中的作业调度等。

        队列仅在表尾进行插入操作，在表头进行删除操作。它是一种先进先出的线性表。

        在队首删除元素成为出队，在队尾插入元素成为入队。

1.队列的顺序存储方式的实现

1.定义

#define MAXQSIZE 100 // 最大队列长度

struct SeqListQueue{
    int *base;
    int front;
    int rear;
};

2.队列初始化

// 队列初始化
void initQueue(SeqListQueue &seqQueue){
    seqQueue.base = (int *)malloc(sizeof(int) * MAXQSIZE); // 为队列的数组成员分配内存空间
    if (!seqQueue.base) {
        std::cerr << "内存分配失败！" << std::endl;
        exit(EXIT_FAILURE);
    }
    seqQueue.front = seqQueue.rear = 0; // 初始化队列的 front 和 rear 指针
}

3.销毁

// 销毁队列
void destroyQueue(SeqListQueue &seqQueue) {
    free(seqQueue.base);
    seqQueue.base = nullptr;
    seqQueue.front = seqQueue.rear = 0;
}

4.队列是否为空

// 判断队列是否为空
bool isEmptyQueue(SeqListQueue seqQueue) {
    return seqQueue.front == seqQueue.rear;
}

5.队列长度

// 获取队列长度
int queueLength(SeqListQueue seqQueue) {
    return (seqQueue.rear - seqQueue.front + MAXQSIZE) % MAXQSIZE;
}

6.清空队列

// 清空队列
void clearQueue(SeqListQueue &seqQueue) {
    seqQueue.front = seqQueue.rear = 0; // 将 front 和 rear 指针重置为零
}

7.队列头元素

// 获取队列的队首元素
bool getFront(SeqListQueue seqQueue, int &element) {
    if (seqQueue.front == seqQueue.rear) {
        std::cerr << "队列为空，无法获取队首元素！" << std::endl;
        return false;
    }
    element = seqQueue.base[seqQueue.front];
    return true;
}

8.入队

// 入队
bool enQueue(SeqListQueue &seqQueue, int element) {
    if ((seqQueue.rear + 1) % MAXQSIZE == seqQueue.front) {
        std::cerr << "队列已满，无法入队！" << std::endl;
        return false;
    }
    seqQueue.base[seqQueue.rear] = element;
    seqQueue.rear = (seqQueue.rear + 1) % MAXQSIZE;
    return true;
}

9.出队

// 出队
bool deQueue(SeqListQueue &seqQueue, int &element) {
    if (seqQueue.front == seqQueue.rear) {
        std::cerr << "队列为空，无法出队！" << std::endl;
        return false;
    }
    element = seqQueue.base[seqQueue.front];
    seqQueue.front = (seqQueue.front + 1) % MAXQSIZE;
    return true;
}

10.完整代码

#include <iostream>
#include <cstdlib> // for malloc, free

#define MAXQSIZE 100 // 最大队列长度

struct SeqListQueue{
    int *base;
    int front;
    int rear;
};

// 队列初始化
void initQueue(SeqListQueue &seqQueue){
    seqQueue.base = (int *)malloc(sizeof(int) * MAXQSIZE); // 为队列的数组成员分配内存空间
    if (!seqQueue.base) {
        std::cerr << "内存分配失败！" << std::endl;
        exit(EXIT_FAILURE);
    }
    seqQueue.front = seqQueue.rear = 0; // 初始化队列的 front 和 rear 指针
}

// 入队
bool enQueue(SeqListQueue &seqQueue, int element) {
    if ((seqQueue.rear + 1) % MAXQSIZE == seqQueue.front) {
        std::cerr << "队列已满，无法入队！" << std::endl;
        return false;
    }
    seqQueue.base[seqQueue.rear] = element;
    seqQueue.rear = (seqQueue.rear + 1) % MAXQSIZE;
    return true;
}

// 出队
bool deQueue(SeqListQueue &seqQueue, int &element) {
    if (seqQueue.front == seqQueue.rear) {
        std::cerr << "队列为空，无法出队！" << std::endl;
        return false;
    }
    element = seqQueue.base[seqQueue.front];
    seqQueue.front = (seqQueue.front + 1) % MAXQSIZE;
    return true;
}

// 输出队列元素
void printQueue(SeqListQueue seqQueue) {
    int i = seqQueue.front;
    while (i != seqQueue.rear) {
        std::cout << seqQueue.base[i] << " ";
        i = (i + 1) % MAXQSIZE;
    }
    std::cout << std::endl;
}

// 销毁队列
void destroyQueue(SeqListQueue &seqQueue) {
    free(seqQueue.base);
    seqQueue.base = nullptr;
    seqQueue.front = seqQueue.rear = 0;
}

// 判断队列是否为空
bool isEmptyQueue(SeqListQueue seqQueue) {
    return seqQueue.front == seqQueue.rear;
}

// 获取队列长度
int queueLength(SeqListQueue seqQueue) {
    return (seqQueue.rear - seqQueue.front + MAXQSIZE) % MAXQSIZE;
}

// 清空队列
void clearQueue(SeqListQueue &seqQueue) {
    seqQueue.front = seqQueue.rear = 0; // 将 front 和 rear 指针重置为零
}

// 获取队列的队首元素
bool getFront(SeqListQueue seqQueue, int &element) {
    if (seqQueue.front == seqQueue.rear) {
        std::cerr << "队列为空，无法获取队首元素！" << std::endl;
        return false;
    }
    element = seqQueue.base[seqQueue.front];
    return true;
}

int main() {
    SeqListQueue seqQueue;
    initQueue(seqQueue); // 初始化队列

    // 测试入队
    for (int i = 1; i <= 5; ++i) {
        enQueue(seqQueue, i * 10);
    }

    // 输出队列元素
    std::cout << "队列元素：";
    printQueue(seqQueue);

    // 获取队首元素
    int frontElement;
    if (getFront(seqQueue, frontElement)) {
        std::cout << "队首元素：" << frontElement << std::endl;
    }

    // 测试出队
    int element;
    for (int i = 0; i < 3; ++i) {
        if (deQueue(seqQueue, element)) {
            std::cout << "出队元素：" << element << std::endl;
        }
    }

    // 输出队列元素
    std::cout << "队列元素：";
    printQueue(seqQueue);

    // 判断队列是否为空
    if (isEmptyQueue(seqQueue)) {
        std::cout << "队列为空" << std::endl;
    } else {
        std::cout << "队列不为空" << std::endl;
    }

    // 获取队列长度
    std::cout << "队列长度为：" << queueLength(seqQueue) << std::endl;

    // 清空队列
    clearQueue(seqQueue);

    // 判断队列是否为空
    if (isEmptyQueue(seqQueue)) {
        std::cout << "清空队列后，队列为空" << std::endl;
    } else {
        std::cout << "清空队列后，队列不为空" << std::endl;
    }

    // 销毁队列
    destroyQueue(seqQueue);

    return 0;
}

2.队列的链式存储方式的实现

1.定义

typedef struct QNode {
    int data;          // 元素
    struct QNode *next;  // 指向下一个节点的指针
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front; // 队首指针
    QueuePtr rear;  // 队尾指针
} LinkQueue;

2.队列初始化

// 初始化队列
void initQueue(LinkQueue &link) {
    link.front = link.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!link.front) {
        exit(-1); // 内存分配失败
    }
    link.front->next = NULL;
}

3.销毁

void destroyQueue(LinkQueue &queue) {
    QueuePtr p, q;
    p = queue.front;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    queue.front = queue.rear = nullptr; // 将队首和队尾指针置为空指针
}

4.队列是否为空

// 判断队列是否为空
bool isEmptyQueue(LinkQueue queue) {
    return queue.front == queue.rear;
}

5.队列长度

// 获取队列长度
int queueLength(LinkQueue queue) {
    int length = 0;
    QueuePtr p = queue.front->next;
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

6.清空队列

// 清空队列
void clearQueue(LinkQueue &queue) {
    QueuePtr p = queue.front->next;
    while (p) {
        QueuePtr temp = p;
        p = p->next;
        free(temp);
    }
    queue.front->next = nullptr;
    queue.rear = queue.front;
}

7.队列头元素

// 获取队列的头元素
int getFront(LinkQueue queue) {
    if (isEmptyQueue(queue)) {
        cout << "队列为空！" << endl;
        return -1;
    }
    return queue.front->next->data;
}

8.入队

// 入队
void enQueue(LinkQueue &queue, int element) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); // 申请内存空间
    if (!p) {
        exit(-1); // 内存分配失败
    }
    p->data = element;
    p->next = NULL;
    queue.rear->next = p;
    queue.rear = p;
}

9.出队

// 出队
int deQueue(LinkQueue &queue, int &element) {
    if (queue.rear == queue.front) {
        return 0; // 队列为空
    }
    QueuePtr p = queue.front->next;
    element = p->data;
    queue.front->next = p->next;
    if (queue.rear == p) {
        queue.rear = queue.front;
    }
    free(p);
    return 1;
}

10.完整代码

#include <iostream>
#include <cstdlib> // for malloc, free
using namespace std;

typedef int ElementType;

typedef struct QNode {
    int data;          // 元素
    struct QNode *next;  // 指向下一个节点的指针
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front; // 队首指针
    QueuePtr rear;  // 队尾指针
} LinkQueue;

// 初始化队列
void initQueue(LinkQueue &link) {
    link.front = link.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!link.front) {
        exit(-1); // 内存分配失败
    }
    link.front->next = NULL;
}

// 入队
void enQueue(LinkQueue &queue, int element) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); // 申请内存空间
    if (!p) {
        exit(-1); // 内存分配失败
    }
    p->data = element;
    p->next = NULL;
    queue.rear->next = p;
    queue.rear = p;
}

// 出队
int deQueue(LinkQueue &queue, int &element) {
    if (queue.rear == queue.front) {
        return 0; // 队列为空
    }
    QueuePtr p = queue.front->next;
    element = p->data;
    queue.front->next = p->next;
    if (queue.rear == p) {
        queue.rear = queue.front;
    }
    free(p);
    return 1;
}

// 销毁队列
void destroyQueue(LinkQueue &queue) {
    QueuePtr p, q;
    p = queue.front;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    queue.front = queue.rear = nullptr; // 将队首和队尾指针置为空指针
}

// 清空队列
void clearQueue(LinkQueue &queue) {
    QueuePtr p = queue.front->next;
    while (p) {
        QueuePtr temp = p;
        p = p->next;
        free(temp);
    }
    queue.front->next = nullptr;
    queue.rear = queue.front;
}

// 判断队列是否为空
bool isEmptyQueue(LinkQueue queue) {
    return queue.front == queue.rear;
}

// 获取队列长度
int queueLength(LinkQueue queue) {
    int length = 0;
    QueuePtr p = queue.front->next;
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

// 获取队列的头元素
int getFront(LinkQueue queue) {
    if (isEmptyQueue(queue)) {
        cout << "队列为空！" << endl;
        return -1;
    }
    return queue.front->next->data;
}

// 输出队列元素
void printQueue(LinkQueue queue) {
    QueuePtr p = queue.front->next;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkQueue queue;
    initQueue(queue); // 初始化队列

    // 测试入队
    enQueue(queue, 10);
    enQueue(queue, 20);
    enQueue(queue, 30);

    // 输出队列元素
    cout << "队列元素：";
    printQueue(queue);

    // 测试出队
    int element;
    if (deQueue(queue, element)) {
        cout << "出队元素：" << element << endl;
    } else {
        cout << "队列为空，无法出队！" << endl;
    }

    // 输出队列元素
    cout << "队列元素：";
    printQueue(queue);

    // 清空队列
    clearQueue(queue);

    // 测试是否为空
    if (isEmptyQueue(queue)) {
        cout << "队列已清空或为空" << endl;
    } else {
        cout << "队列不为空" << endl;
    }

    // 测试队列长度
    cout << "队列长度为：" << queueLength(queue) << endl;

    // 测试获取队列头元素
    cout << "队列头元素为：" << getFront(queue) << endl;

    return 0;
}

 3.线性表、栈、队列的区别

        相同点：逻辑结构相同，都是线性的；都可以用顺序存储或者链式存储；栈和队列都是两种特殊的线性表，即受限的线性表(知识对插入、删除运算加以限制)。

        不同点：

1.运算规则不同

        线性表为随机存储，栈只允许在一段进行插入和删除运算，因而是后进先出表LIFO。

        队列是只允许在一段进行插入、另一端进行删除操作，因而是先进先出表FIFO。

2.用途不同

        线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。