最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界今热点：[数据结构] 队列 (C语言)

来源：博客园


(资料图片)

队列

队列基本概念

队列( queue)是一种特殊的线性表结构，只从队尾插入新的元素，并且只从队首弹出元素。一般将队尾称为 rear，队首称为 front。

队列基本操作

（1）入队：从队尾 rear插入新元素；（2）出队：从队首 front弹出元素。

队列的特性

队列遵循 先进先出的原则。比如元素 1、2、3、4、5依次入队，且中途不存在出队过元素再次入队或其他元素入队，出队顺序为 1、2、3、4、5。

循环顺序队列

循环顺序队列基本概念

顺序队列是用数组实现的队列，但是由于定义的数组的空间有限，可以想象一下，当队首 front和 队尾 rear经过一系列操作都往后移动时，之前所使用到的空间都不会再被使用了，这造成了空间上的浪费。

所以定义顺序队列往往采用更加高效的 循环顺序队列，其基本上就是在顺序队列的基础上加了一点小小的修改。

循环顺序队列的入队操作

循环顺序队列入队操作图解

初始状态下的循环顺序队列

元素1入队

元素2、3、4、5入队

循环顺序队列入队操作代码

//队列元素入队void Enter_SqQueue(SqQueue *Q, int e){    if((Q->rear + 1) % MAXSIZE == Q->front){printf("队列已满\n");return;    }    Q->data[Q->rear] = e;               //在队尾指向的地址赋值    Q->rear = (Q->rear + 1) % MAXSIZE;  //队尾指针进1}

循环顺序队列的出队操作

循环顺序队列出队操作图解

元素1出队

元素2、3、4、5出队

循环顺序队列出队操作代码

//队列元素出队void Depart_SqQueue(SqQueue *Q, int *e){    if(IsEmpty(Q)){printf("队列中无元素\n");return;    }    *e = Q->data[Q->front];             //取出队首指针指向的地址元素    Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1}

循环顺序队列中的循环示例

入队

此时队列rear虽然指向数组的最后，但循环操作可以使其重复利用之前使用的空间。

出队

类似的此时队列front指向数组的最后

循环顺序队列完整程序

源代码

#include#include#include#define MAXSIZE 1000typedef int Elemtype;typedef struct SqQueue{    Elemtype data[MAXSIZE];    int front;           //队列前指针    int rear;            //队列后指针}SqQueue;//初始化void Create_SqQueue(SqQueue *Q){    Q->front = Q->rear = 0;}//判断队列是否为空bool IsEmpty(SqQueue *Q){    return Q->front == Q->rear;}//求得队列长度int SqQueue_Length(SqQueue *Q){    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;}//队列元素入队void Enter_SqQueue(SqQueue *Q, int e){    if((Q->rear + 1) % MAXSIZE == Q->front){printf("队列已满\n");return;    }    Q->data[Q->rear] = e;               //在队尾指向的地址赋值    Q->rear = (Q->rear + 1) % MAXSIZE;  //队尾指针进1}//队列元素出队void Depart_SqQueue(SqQueue *Q, int *e){    if(IsEmpty(Q)){printf("队列中无元素\n");return;    }    *e = Q->data[Q->front];             //取出队首指针指向的地址元素    Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1}//取队首int Get_front(SqQueue *Q){    if(IsEmpty(Q)){printf("队列为空\n");return -1;    }    return Q->data[Q->front];}int main(){    SqQueue myQueue;    Elemtype a[5] = {35, 30, 11, 23, 9};    Create_SqQueue(&myQueue);    for(int i = 0; i < 5; i++)        Enter_SqQueue(&myQueue, a[i]);    Elemtype e;    Depart_SqQueue(&myQueue, &e);    printf("出队元素: %d\n", e);    printf("元素22入队并将所有元素出队: \n");    Enter_SqQueue(&myQueue, 22);    while(!IsEmpty(&myQueue)){    printf("%d ", Get_front(&myQueue));    Depart_SqQueue(&myQueue, &e);    }    return 0;}

程序运行结果

链队列

链队列基本概念

链队列是链式的队列结构，其拥有一个 front指针作为队首，一般队首 front是不带数据的；还有一个 rear指针作为队尾，队尾 rear指向队列的最后一个元素。链队列的操作和链表也有一些相似之处。

链队列的入队操作

链队列入队操作图解

初始状态下的链队列

元素1入队

元素2、3入队

链队列入队操作代码

//链队列元素入队void Enter_LinkQueue(LinkQueue *Q, int e){    Linknode *node = (Linknode*)malloc(sizeof(Linknode));    node->data = e;    node->next = NULL;    Q->rear->next = node;     //原先队列尾指针后继next指向新节点node    Q->rear = node;           //尾指针重新指向新节点node}

链队列的出队操作

链队列出队操作图解

元素1出队

链队列出队操作代码

当链队列只有一个元素并且将其出队时，需要特判一下，将链队列置于空队列的状态。

//链队列元素出队void Depart_LinkQueue(LinkQueue *Q, int *e){    if(Q->rear == Q->front) return;    Linknode *p;    p = Q->front->next;       //要删除的节点暂存给p    *e = p->data;             //取出删除队头节点的数据    Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点    if(Q->rear == p)          //当队列只有一个元素的情况    Q->rear = Q->front;       free(p);}

链队列完整程序

源代码

#include#include#includetypedef int Elemtype;//队列节点结构typedef struct Linknode{    Elemtype data;             //队列节点数据域    struct Linknode *next;     //队列next指针域}Linknode;//链队列整体结构typedef struct LinkQueue{    Linknode *front;           //链队列首指针  队首指针不带数据    Linknode *rear;            //链队列尾指针}LinkQueue;//初始化创建链队列void Create_LinkQueue(LinkQueue *Q){    Q->front = Q->rear = (Linknode*)malloc(sizeof(Linknode));    Q->front->next == NULL;}//链队列元素入队void Enter_LinkQueue(LinkQueue *Q, int e){    Linknode *node = (Linknode*)malloc(sizeof(Linknode));    node->data = e;    node->next = NULL;    Q->rear->next = node;     //原先队列尾指针后继next指向新节点node    Q->rear = node;           //尾指针重新指向新节点node}//链队列元素出队void Depart_LinkQueue(LinkQueue *Q, int *e){    if(Q->rear == Q->front) return;    Linknode *p;    p = Q->front->next;       //要删除的节点暂存给p    *e = p->data;             //取出删除队头节点的数据    Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点    if(Q->rear == p)          //当队列只有一个元素的情况    Q->rear = Q->front;          free(p);}//判断是否为空bool IsEmpty(LinkQueue *Q){    return Q->front == Q->rear;}//取队首int Front_LinkQueue(LinkQueue *Q){    if(IsEmpty(Q)){printf("队列为空\n");return -1;    }    return Q->front->next->data;}int main(){    LinkQueue myQueue;    Create_LinkQueue(&myQueue);    Enter_LinkQueue(&myQueue, 1);    Enter_LinkQueue(&myQueue, 2);    Enter_LinkQueue(&myQueue, 3);    printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue));        Elemtype e;    Depart_LinkQueue(&myQueue, &e);    printf("出队的元素为 %d \n", e);    printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue));        printf("\n所有元素出队：\n");    while(!IsEmpty(&myQueue)){    printf("%d ", Front_LinkQueue(&myQueue));    Depart_LinkQueue(&myQueue, &e);    }    return 0;}

程序运行结果

关键词： 顺序队列 基本概念