当前位置: article > 正文

队列----定义和实现

作者：笔触狂放9 | 2024-07-27 21:44:21

踩

队列----定义和实现

1、队列的定义

队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端front进行插入，而在另一端rear进行删除。
队首(front) ：允许进行删除的一端称为队首。
队尾(rear) ：允许进行插入的一端称为队尾。
　　例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。

队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an ，即队列的修改是依先进先出的原则进行的，如图所示。

2 、队列的抽象数据类型定义
ADT Queue{
数据对象：D ={ ai|ai∈ElemSet, i=1, 2, …, n, n >= 0 }

数据关系：R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n }
约定a1端为队首，an端为队尾。
基本操作：
Create()：创建一个空队列；
EmptyQue()：若队列为空，则返回true ，否则返回flase ；

FullQue();若队列为满，则返回true ，否则返回flase ；
⋯⋯
InsertQue(x) ：向队尾插入元素x；
DeleteQue(x) ：删除队首元素x；
} ADT Queue

3、队列的表示和实现

队列可以由三种方式实现：静态数组队列、动态数组队列和链式队列。

(1)静态数组队列（循环数组队列实现）

[cpp]view plaincopy 
   
print?
 循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。  
 /* 队列的顺序存储结构(循环队列) */  
 #define MAX_QSIZE 5 /* 最大队列长度+1 */  
 typedef struct  
 {  
   QElemType *base; /* 初始化的动态分配存储空间 */  
   int front; /* <span style="color:#ff0000;">头指针，若队列不空，指向队列头元素</span> */  
   int rear;  /* <span style="color:#cc0000;">尾指针，若队列不空，指向队列尾元素的下一个位置</span> */  
 }SqQueue;  
    
 /* 循环队列的基本操作(9个) */  
 void InitQueue(SqQueue *Q)  
 { /* 构造一个空队列Q */  
   Q->base=malloc(MAX_QSIZE*sizeof(QElemType));  
   if(!Q->base) /* 存储分配失败 */  
     exit(OVERFLOW);  
   Q->front=Q->rear=0;/*空队列*/  
 }  
    
 void DestroyQueue(SqQueue *Q)  
 { /* 销毁队列Q，Q不再存在 */  
   if(Q->base)  
     free(Q->base);  
   Q->base=NULL;  
   Q->front=Q->rear=0;  
 }  
    
 void ClearQueue(SqQueue *Q)  
 { /* 将Q清为空队列 */  
   Q->front=Q->rear=0;  
 }  
    
 Status QueueEmpty(SqQueue Q)  
 { /* 若队列Q为空队列，则返回TRUE；否则返回FALSE */  
   if(Q.front==Q.rear) /* 队列空的标志 */  
     return TRUE;  
   else  
     return FALSE;  
 }  
    
 int QueueLength(SqQueue Q)  
 { /* 返回Q的元素个数，即队列的长度 */  
   return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;  
 }  
    
 Status GetHead(SqQueue Q,QElemType *e)  
 { /* 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR */  
   if(Q.front==Q.rear) /* 队列空 */  
     return ERROR;  
   *e=Q.base[Q.front];  
   return OK;  
 }  
    
 Status EnQueue(SqQueue *Q,QElemType e)  
 { /* 插入元素e为Q的新的队尾元素 */  
   if((Q->rear+1)%MAX_QSIZE==Q->front) /* 队列满 */  
     return ERROR;  
   Q->base[Q->rear]=e;  
   Q->rear=(Q->rear+1)%MAX_QSIZE;  
   return OK;  
 }  
    
 Status DeQueue(SqQueue *Q,QElemType *e)  
 { /* 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR */  
   if(Q->front==Q->rear) /* 队列空 */  
     return ERROR;  
   *e=Q->base[Q->front];  
   Q->front=(Q->front+1)%MAX_QSIZE;  
   return OK;  
 }  
    
 void QueueTraverse(SqQueue Q,void(*vi)(QElemType))  
 { /* 从队头到队尾依次对队列Q中每个元素调用函数vi() */  
   int i;  
   i=Q.front;  
   while(i!=Q.rear)  
   {  
     vi(Q.base[i]);  
     i=(i+1)%MAX_QSIZE;  
   }  
   printf("\n");  
 }  

(2)动态数组队列

[cpp]view plaincopy 
   
print?

(3)链式队列

[cpp]view plaincopy 
   
print?
 单链队列  
 单链队列使用链表作为基本数据结果，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高  
 /* 单链队列——队列的链式存储结构 */  
 typedef struct QNode  
 {  
   QElemType data;  
   struct QNode *next;  
 }QNode,*QueuePtr;  
    
 typedef struct  
 {  
   QueuePtr front,rear; /* 队头、队尾指针 */  
 }LinkQueue;  
    
 /* 链队列的基本操作(9个) */  
 void InitQueue(LinkQueue *Q)  
 { /* 构造一个空队列Q */  
   Q->front=Q->rear=malloc(sizeof(QNode));  
   if(!Q->front)  
     exit(OVERFLOW);  
   Q->front->next=NULL;  
 }  
    
 void DestroyQueue(LinkQueue *Q)  
 { /* 销毁队列Q(无论空否均可) */  
   while(Q->front)  
   {  
     Q->rear=Q->front->next;  
     free(Q->front);  
     Q->front=Q->rear;  
   }  
 }  
    
 void ClearQueue(LinkQueue *Q)  
 { /* 将Q清为空队列 */  
   QueuePtr p,q;  
   Q->rear=Q->front;  
   p=Q->front->next;  
   Q->front->next=NULL;  
   while(p)  
   {  
     q=p;  
     p=p->next;  
     free(q);  
   }  
 }  
    
 Status QueueEmpty(LinkQueue Q)  
 { /* 若Q为空队列，则返回TRUE，否则返回FALSE */  
   if(Q.front->next==NULL)  
     return TRUE;  
   else  
     return FALSE;  
 }  
    
 int QueueLength(LinkQueue Q)  
 { /* 求队列的长度 */  
   int i=0;  
   QueuePtr p;  
   p=Q.front;  
   while(Q.rear!=p)  
   {  
     i++;  
     p=p->next;  
   }  
   return i;  
 }  
    
 Status GetHead_Q(LinkQueue Q,QElemType *e)  
 { /* 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR */  
   QueuePtr p;  
   if(Q.front==Q.rear)  
     return ERROR;  
   p=Q.front->next;  
   *e=p->data;  
   return OK;  
 }  
    
 void EnQueue(LinkQueue *Q,QElemType e)  
 { /* 插入元素e为Q的新的队尾元素 */  
   QueuePtr p=malloc(sizeof(QNode));  
   if(!p) /* 存储分配失败 */  
     exit(OVERFLOW);  
   p->data=e;  
   p->next=NULL;  
   Q->rear->next=p;  
   Q->rear=p;  
 }  
    
 Status DeQueue(LinkQueue *Q,QElemType *e)  
 { /* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR */  
   QueuePtr p;  
   if(Q->front==Q->rear)  
     return ERROR;  
   p=Q->front->next;  
   *e=p->data;  
   Q->front->next=p->next;  
   if(Q->rear==p)  
     Q->rear=Q->front;  
   free(p);  
   return OK;  
 }  
    
 void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))  
 { /* 从队头到队尾依次对队列Q中每个元素调用函数vi() */  
   QueuePtr p;  
   p=Q.front->next;  
   while(p)  
   {  
     vi(p->data);  
     p=p->next;  
   }  
   printf("\n");  
 }  

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/891784