计算机考研择校咨询
请添加清华姚哥微信
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。
队列的基本操作：
1、InitQueue(&Q)：初始化队列，构造一个空队列Q。
2、QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
3、EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
4、DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。
5、GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x。
typedef struct{ElemType data[MAXSIZE]; //存放队列元素int front,rear;}SqQueue;
讯享网
我们把队列的这种头尾相接的顺序存储结构称为循环队列。
当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。
初始时：Q->front = Q->rear=0。
队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。
队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。
队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。
队空的条件：Q->front == Q->rear 。
为了区分队空还是队满的情况，有三种处理方式：
（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图 ( d2 ）所示。
（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == O ；队满的条件为 Q->size == Maxsize 。这两种情况都有 Q->front == Q->rear
（3）类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。
讯享网//循环队列的顺序存储结构typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int/循环队列的顺序存储结构/typedef struct{ElemType data[MAXSIZE];int front; //头指针int rear; //尾指针,若队列不空，指向队列尾元素的下一个位置}SqQueue;
/初始化一个空队列Q/Status InitQueue(SqQueue *Q){Q->front = 0;Q->rear = 0;return OK;}
讯享网/初始化一个空队列Q/Status InitQueue(SqQueue *Q){Q->front = 0;Q->rear = 0;return OK;}
//求循环队列的长度/返回Q的元素个数，也就是队列的当前长度/int QueueLength(SqQueue Q){return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;}
讯享网//循环队列入队/若队列未满，则插入元素e为Q新的队尾元素/Status EnQueue(SqQueue *Q, ElemType e){if((Q->rear + 1) % MAXSIZE == Q->front){return ERROR; //队满}Q->data[Q->rear] = e; //将元素e赋值给队尾Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一位置，若到最后则转到数组头部return OK;}
//循环队列出队/若队列不空，则删除Q中队头元素，用e返回其值/Status DeQueue(SqQueue *Q, ElemType *e){if(isEmpty(Q)){return REEOR; //队列空的判断}*e = Q->data[Q->front]; //将队头元素赋值给eQ->front = (Q->front + 1) % MAXSIZE; //front指针向后移一位置，若到最后则转到数组头部}
队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已。
空队列时，front和real都指向头结点。
当Q->front == NULL 并且 Q->rear == NULL 时，链队列为空。
讯享网/链式队列结点/typedef struct {ElemType data;struct LinkNode *next;}LinkNode;/链式队列/typedef struct{LinkNode *front, *rear; //队列的队头和队尾指针}LinkQueue;
/链式队列初始化/void InitQueue(LinkQueue *Q){ Q->front = Q->rear = (LinkNode)malloc(sizeof(LinkNode)); //建立头结点Q->front->next = NULL; //初始为空}
讯享网/链式队列入队/Status EnQueue(LinkQueue *Q, ElemType e){LinkNode s = (LinkNode)malloc(sizeof(LinkNode));s->data = e;s->next = NULL;Q->rear->next = s; //把拥有元素e新结点s赋值给原队尾结点的后继Q->rear = s; //把当前的s设置为新的队尾结点return OK;}
/链式队列出队//若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR/Status DeQueue(LinkQueue *Q, Elemtype *e){LinkNode p;if(Q->front == Q->rear){return ERROR;}p = Q->front->next; //将欲删除的队头结点暂存给p*e = p->data; //将欲删除的队头结点的值赋值给eQ->front->next = p->next; //将原队头结点的后继赋值给头结点后继//若删除的队头是队尾，则删除后将rear指向头结点if(Q->rear == p){Q->rear = Q->front;}free(p);return OK;}
更多择校信息请前往“姚哥计算机考研”公众号查找
免费资料领取详细流程
2.公众号后台关键字回复：思维导图/代码大全/英语作文
免费择校咨询姚哥微信：fgtlmz660
2023计算机考研交流3群:
👇👇👇
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/193774.html