2025年《大话数据结构》队列——只允许在一端进行插入操作,而在另外一端进行删除操作的线性表

《大话数据结构》队列——只允许在一端进行插入操作,而在另外一端进行删除操作的线性表1 定义 队列是一种只允许在一端进行插入操作 而在另一端进行删除操作的线性表 简称 FIFO 符合生活习惯 排在第一个的优先出列 最后来的排在队伍后面 2 循环队列队列的顺序存储结构 所谓的入队操作 就是在队尾追加一个元素

大家好,我是讯享网,很高兴认识大家。

1.定义

队列是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表,简称:FIFO

符合生活习惯:排在第一个的优先出列,最后来的排在队伍后面


讯享网

 

 

2.循环队列------队列的顺序存储结构

所谓的入队操作,就是在队尾追加一个元素,而不需要移动任何元素,因此时间复杂度为O(1)。

定义:把队列这种头尾相接的顺序存储结构称之为循环队列。

front指针指向队头元素,rear指针指向队尾元素的下一个位置

如何判断队列满了?

而作为对比,下面4-12-7不作为队列满的的判决办法了,

而rear与front之间的关系存在于以下两种,所以得到通用的计算队列公式为:

 

/*循环队列的顺序存储结构*/ #define MAXMIZE 100 typedef struct { int data[MAXMIZE]; int front;//头指针 int rear;//尾指针,若队列不空,则指向队尾元素的下一个位置 }queue; //初始化队列 int init(queue *q) { q->front=0; q->rear=0; } / *返回 Q 的个数,也就是队列的当前长度* / int quelength(queue q) { return (q.rear-q.front+MAXMIZE)%MAXMIZE; } //插入新元素 /*若队列未满,则插入元素 e 为 Q 新的队尾元素*/ int insect(queue *q,int e) { q->data[q->rear]=e; q->rear=(q->rear+1)%MAXSIZE//将rear指针向后移一个位置,若到最后则转到数组头部 //判断队列为满的判断 if((q->rear+1)%MAXMIZE==q->front) return 0; return 1; } //删除元素 /*若队列不空,则删除q中队头元素。用 e返回其值*/ int delete(queue *q, int e) { e=q->data[q->front]; q->front=(q->front+1)%MAXMIZE; //队列为空的判断 if(q->front==q->rear) return 0; return 1; } 

讯享网

3.循环队列---队列的链式存储结构

定义:称之为链队列,队列的链式存储结构,就是线性表的单链表,只不过它只能尾进头出

队头指针指向链队列的头节点,队尾指针指向终端节点

空队列的时候,front和rear都指向头节点

讯享网//链队列的结构 //节点 typedef struct node { int data; struct node *next; }node,*qnode; //链表结构 typedef struct { qnodefront,rear;//队头,队尾指针 }linkqueue; 

1)入队操作

入队操作,就是在链表尾部插入节点

/*插入元素e为Q的新的队尾元素 */ //节点结构 typedef struct node { int data; struct node *next; }node,*qnode; //队列的链表结构 typedef struct { qnode front ,rear; }linkqueue; int enterqueue(linkqueue *q,int e) { //开辟一个新节点 qnode s=(qnode)malloc(sizeof(node)) s->data=e; s->next=NULL; q->rear->next=s;//操作(1),将新节点s作为q队尾指针的后继 s->rear=s;//操作(2),把s设置为队尾节点 if(!s) exit(OVERFLOW); }

2)出队操作

讯享网/*若队列不空,删除Q的队头元素,用e返回其值, 并返回1,否则返回0 */ typedef struct node { int data; struct node *next; }node,*pnode; typedef struct { pnode front,rear; }queue; int dequeue(queue *q,int *e) { pnode s; s=q->front->next;//操作(1),将预删除的队头节点暂存给s *e=q->data; q->front->next=s->next;//操作(2),将原头节点后继s->next赋值给头节点后继 //操作(3),若队头是队尾,则删除后,将rear指向头节点 if(q->rear==p) q->rear=q->front; //错误的情况 if(q-front==q->rear) return 0; return 1; }

 

 

总结:

在确定队列长度最大值的情况下,建议使用循环队列,否则,若无法预估队列的长度时,则用链队列

 

小讯
上一篇 2025-04-05 18:19
下一篇 2025-03-26 19:13

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82598.html