简介

此模块为学校数据结构必修课学习内容的记录与分享

全文大体分为一下几个部分

• 前言
• 背景
• 分析（伪代码部分）
• 代码
• 结果
• Points

前言

由于前段时间赶团队培训进度，后面需要对培训内容进行总结，因此以后相当一部分时间在 homework 上面的时间可能会减少，因此先贴出主要思路及要点，后面抽时间进行细节补充与整理

又挖坑了…QAQ

背景

是一种广泛应用于操作系统、网络通信以及高级算法等领域的重要数据结构

特点是：先进先出、顺序储存

在数组基础上增加了首尾两个指针用来控制数据的进出

可视化图像

静态

动态

注意，这里想成了front 进，rear出了

一般的代码应该是rear进，front出

不过代码思想是一样的，就不修改了，哈哈哈

从这张图上我们也可以看到，（链）队列就是在链表的基础上添加了头尾指针，用来在链表的基础上拓展“先进先出”的特性

联系到前面学习链表时候对应的用数组来模拟动态链表的静态链表，我们可以想到还可以有”静态队列“的数据结构

想一想，是否是用数组替换链表，用相对下标替换指针呢？

Bingo! 后面可能会出文章去展开说下这个结构【挖坑ing】

代码

注意，下面的代码是构建的包含头节点的单链表

经过上面的解释，我们也不难写出下面的代码：

typedef struct LinkedNode {
    int data;
    struct LinkedNode *next;
}*LinkedNodePtr;

typedef struct LinkedQueue {
    // 指针类型和指针指向的数据类型是一致的
    struct LinkedNode *front;
    struct LinkedNode *rear;
}*LinkedQueuePtr;

完整代码

#include<stdio.h>
#include<malloc.h>
typedef struct LinkedNode {
    int data;
    struct LinkedNode *next;
}*LinkedNodePtr;

typedef struct LinkedQueue {
    // 指针类型和指针指向的数据类型是一致的
    // 这里就是纯粹的指针
    struct LinkedNode *front;
    struct LinkedNode *rear;
}*LinkedQueuePtr;

// 初始化带一个头节点的队列
// 前后指针指向同一个节点
LinkedQueuePtr InitQueue() {
    LinkedQueuePtr result = (LinkedQueuePtr)malloc(sizeof(struct LinkedQueue));
    LinkedNodePtr node = (LinkedNodePtr)malloc(sizeof(struct LinkedNode));

    result->front = node;
    result->rear = node;

    return result;
}

// 向队列插入新元素
void EnQueue(LinkedQueuePtr Queue, int data) {
    LinkedNodePtr NewNode = (LinkedNodePtr)malloc(sizeof(struct LinkedNode));
    NewNode->data = data;
    NewNode->next = NULL;
    
    // 因为创造是带有节点的链队列，因此不用判断是否为空，直接进行插入操作
    // 插在链表尾部
    Queue->rear->next = NewNode;
    // 更新rear尾指针
    Queue->rear = NewNode;
}// Of EnQueue

// 输出队列中的元素
void OutPutQueue(LinkedQueuePtr Queue) {
    LinkedNodePtr temp = Queue->front->next;

    while(temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }//of while
    printf("\n");
}// Of OutPutQueue

int DeQueue(LinkedQueuePtr Queue) {
    int result;
    LinkedNodePtr tempNode;

    if(Queue->front == Queue->rear) {
        printf("队列为空\n");
        return -1;
    }

    tempNode = Queue->front->next;
    result = tempNode->data;
    Queue->front->next = Queue->front->next->next;
    // 处理特殊情况 队列中只有一个元素
    if(Queue->rear == tempNode) {
        Queue->rear = Queue->front;
    }
    free(tempNode);
    return result;
    
}

void testLinkQueue(){
	LinkedQueuePtr tempQueuePtr;
	tempQueuePtr = InitQueue();
	EnQueue(tempQueuePtr, 10);
	EnQueue(tempQueuePtr, 30);
	EnQueue(tempQueuePtr, 50);

	OutPutQueue(tempQueuePtr);

	printf("dequeue gets %d\r\n", DeQueue(tempQueuePtr));
	printf("dequeue gets %d\r\n", DeQueue(tempQueuePtr));
	printf("dequeue gets %d\r\n", DeQueue(tempQueuePtr));
	printf("dequeue gets %d\r\n", DeQueue(tempQueuePtr));

	EnQueue(tempQueuePtr, 8);
	OutPutQueue(tempQueuePtr);
}


int main() {
    testLinkQueue();
    return 0;
}

输出

PS D:\a_study\code_vs\DataStructure\LinkedQueue> g++ -finput-charset=UTF-8 code.cpp -o kernel
PS D:\a_study\code_vs\DataStructure\LinkedQueue> ./kernel
10 30 50 
dequeue gets 10
dequeue gets 30
dequeue gets 50
The queue is empty.
dequeue gets -1
8

Points

队列的头与尾

要注意的是，在队列中：

• front为队首，是数据出来的位置
• rear 为队尾，是数据进去的位置