队列的实现

一、顺序队列

[cpp] view plaincopy
  1.    
  2. typedef  int QElemType;  
  3.    
  4.   // c3-3.h 队列的顺序存储结构(可用于循环队列和非循环队列)  
  5.  #define MAXQSIZE 5 // 最大队列长度(对于循环队列，最大队列长度要减1)  
  6.  struct SqQueue  
  7.  {  
  8.    QElemType *base; // 初始化的动态分配存储空间  
  9.    int front; // 头指针,若队列不空,指向队列头元素  
  10.    int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置  
  11.  };  
  12.    
  13.  // bo3-4.cpp 顺序队列(非循环,存储结构由c3-3.h定义)的基本操作(9个)  
  14.  Status InitQueue(SqQueue &Q)  
  15.  { // 构造一个空队列Q  
  16.    Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));  
  17.    if(!Q.base) // 存储分配失败  
  18.      exit(OVERFLOW);  
  19.    Q.front=Q.rear=0;  
  20.    return OK;  
  21.  }  
  22.   
  23.  Status DestroyQueue(SqQueue &Q)  
  24.  { // 销毁队列Q,Q不再存在  
  25.    if(Q.base)  
  26.      free(Q.base);  
  27.    Q.base=NULL;  
  28.    Q.front=Q.rear=0;  
  29.    return OK;  
  30.  }  
  31.   
  32.  Status ClearQueue(SqQueue &Q)  
  33.  { // 将Q清为空队列  
  34.    Q.front=Q.rear=0;  
  35.    return OK;  
  36.  }  
  37.   
  38.  Status QueueEmpty(SqQueue Q)  
  39.  { // 若队列Q为空队列,则返回TRUE,否则返回FALSE  
  40.    if(Q.front==Q.rear) // 队列空的标志  
  41.      return TRUE;  
  42.    else  
  43.      return FALSE;  
  44.  }  
  45.   
  46.  int QueueLength(SqQueue Q)  
  47.  { // 返回Q的元素个数,即队列的长度  
  48.    return(Q.rear-Q.front);  
  49.  }  
  50.   
  51.  Status GetHead(SqQueue Q,QElemType &e)  
  52.  { // 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR  
  53.    if(Q.front==Q.rear) // 队列空  
  54.      return ERROR;  
  55.    e=*(Q.base+Q.front);  
  56.    return OK;  
  57.  }  
  58.   
  59.  Status EnQueue(SqQueue &Q,QElemType e)  
  60.  { // 插入元素e为Q的新的队尾元素  
  61.    if(Q.rear>=MAXQSIZE)  
  62.    { // 队列满，增加1个存储单元  
  63.      Q.base=(QElemType *)realloc(Q.base,(Q.rear+1)*sizeof(QElemType));  
  64.      if(!Q.base) // 增加单元失败  
  65.        return ERROR;  
  66.    }  
  67.    *(Q.base+Q.rear)=e;  
  68.    Q.rear++;  
  69.    return OK;  
  70.  }  
  71.   
  72.  Status DeQueue(SqQueue &Q,QElemType &e)  
  73.  { // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR  
  74.    if(Q.front==Q.rear) // 队列空  
  75.      return ERROR;  
  76.    e=Q.base[Q.front];  
  77.    Q.front=Q.front+1;  
  78.    return OK;  
  79.  }  
  80.   
  81.  Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))  
  82.  { // 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败  
  83.    int i;  
  84.    i=Q.front;  
  85.    while(i!=Q.rear)  
  86.    {  
  87.      vi(*(Q.base+i));  
  88.      i++;  
  89.    }  
  90.    printf(" ");  
  91.    return OK;  
  92.  }  


二、链队列

[cpp] view plaincopy
  1. typedef int QElemType;  
  2.   
  3. // c3-2.h 单链队列－－队列的链式存储结构  
  4. typedef struct QNode  
  5. {  
  6.   QElemType data;  
  7.   QNode *next;  
  8. }*QueuePtr;  
  9.   
  10. struct LinkQueue  
  11. {  
  12.   QueuePtr front,rear; // 队头、队尾指针  
  13. };  
  14.   
  15.   
  16. // bo3-2.cpp 链队列(存储结构由c3-2.h定义)的基本操作(9个)  
  17. Status InitQueue(LinkQueue &Q)  
  18. { // 构造一个空队列Q  
  19.   if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))  
  20.     exit(OVERFLOW);  
  21.   Q.front->next=NULL;  
  22.   return OK;  
  23. }  
  24.   
  25. Status DestroyQueue(LinkQueue &Q)  
  26. { // 销毁队列Q(无论空否均可)  
  27.   while(Q.front)  
  28.   {  
  29.     Q.rear=Q.front->next;  
  30.     free(Q.front);  
  31.     Q.front=Q.rear;  
  32.   }  
  33.   return OK;  
  34. }  
  35.   
  36. Status ClearQueue(LinkQueue &Q)  
  37. { // 将Q清为空队列  
  38.   QueuePtr p,q;  
  39.   Q.rear=Q.front;  
  40.   p=Q.front->next;  
  41.   Q.front->next=NULL;  
  42.   while(p)  
  43.   {  
  44.     q=p;  
  45.     p=p->next;  
  46.     free(q);  
  47.   }  
  48.   return OK;  
  49. }  
  50.   
  51. Status QueueEmpty(LinkQueue Q)  
  52. { // 若Q为空队列,则返回TRUE,否则返回FALSE  
  53.   if(Q.front==Q.rear)  
  54.     return TRUE;  
  55.   else  
  56.     return FALSE;  
  57. }  
  58.   
  59. int QueueLength(LinkQueue Q)  
  60. { // 求队列的长度  
  61.   int i=0;  
  62.   QueuePtr p;  
  63.   p=Q.front;  
  64.   while(Q.rear!=p)  
  65.   {  
  66.     i++;  
  67.     p=p->next;  
  68.   }  
  69.   return i;  
  70. }  
  71.   
  72. Status GetHead(LinkQueue Q,QElemType &e)  
  73. { // 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR  
  74.   QueuePtr p;  
  75.   if(Q.front==Q.rear)  
  76.     return ERROR;  
  77.   p=Q.front->next;  
  78.   e=p->data;  
  79.   return OK;  
  80. }  
  81.   
  82. Status EnQueue(LinkQueue &Q,QElemType e)  
  83. { // 插入元素e为Q的新的队尾元素  
  84.   QueuePtr p;  
  85.   if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败  
  86.     exit(OVERFLOW);  
  87.   p->data=e;  
  88.   p->next=NULL;  
  89.   Q.rear->next=p;  
  90.   Q.rear=p;  
  91.   return OK;  
  92. }  
  93.   
  94. Status DeQueue(LinkQueue &Q,QElemType &e)  
  95. { // 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR  
  96.   QueuePtr p;  
  97.   if(Q.front==Q.rear)  
  98.     return ERROR;  
  99.   p=Q.front->next;  
  100.   e=p->data;  
  101.   Q.front->next=p->next;  
  102.   if(Q.rear==p)  
  103.     Q.rear=Q.front;  
  104.   free(p);  
  105.   return OK;  
  106. }  
  107.   
  108. Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType))  
  109. { // 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败  
  110.   QueuePtr p;  
  111.   p=Q.front->next;  
  112.   while(p)  
  113.   {  
  114.     vi(p->data);  
  115.     p=p->next;  
  116.   }  
  117.   printf(" ");  
  118.   return OK;  
  119. }  

三、循环队列

[cpp] view plaincopy
    1. // c3-3.h 队列的顺序存储结构(可用于循环队列和非循环队列)  
    2. #define MAXQSIZE 5 // 最大队列长度(对于循环队列，最大队列长度要减1)  
    3. struct SqQueue  
    4. {  
    5.   QElemType *base; // 初始化的动态分配存储空间  
    6.   int front; // 头指针,若队列不空,指向队列头元素  
    7.   int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置  
    8. };  
    9.   
    10. // bo3-3.cpp 循环队列(存储结构由c3-3.h定义)的基本操作(9个)  
    11. Status InitQueue(SqQueue &Q)  
    12. { // 构造一个空队列Q  
    13.   Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));  
    14.   if(!Q.base) // 存储分配失败  
    15.     exit(OVERFLOW);  
    16.   Q.front=Q.rear=0;  
    17.   return OK;  
    18. }  
    19.   
    20. Status DestroyQueue(SqQueue &Q)  
    21. { // 销毁队列Q,Q不再存在  
    22.   if(Q.base)  
    23.     free(Q.base);  
    24.   Q.base=NULL;  
    25.   Q.front=Q.rear=0;  
    26.   return OK;  
    27. }  
    28.   
    29. Status ClearQueue(SqQueue &Q)  
    30. { // 将Q清为空队列  
    31.   Q.front=Q.rear=0;  
    32.   return OK;  
    33. }  
    34.   
    35. Status QueueEmpty(SqQueue Q)  
    36. { // 若队列Q为空队列,则返回TRUE,否则返回FALSE  
    37.   if(Q.front==Q.rear) // 队列空的标志  
    38.     return TRUE;  
    39.   else  
    40.     return FALSE;  
    41. }  
    42.   
    43. int QueueLength(SqQueue Q)  
    44. { // 返回Q的元素个数,即队列的长度  
    45.   return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;  
    46. }  
    47.   
    48. Status GetHead(SqQueue Q,QElemType &e)  
    49. { // 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR  
    50.   if(Q.front==Q.rear) // 队列空  
    51.     return ERROR;  
    52.   e=*(Q.base+Q.front);  
    53.   return OK;  
    54. }  
    55.   
    56. Status EnQueue(SqQueue &Q,QElemType e)  
    57. { // 插入元素e为Q的新的队尾元素  
    58.   if((Q.rear+1)%MAXQSIZE==Q.front) // 队列满  
    59.     return ERROR;  
    60.   Q.base[Q.rear]=e;  
    61.   Q.rear=(Q.rear+1)%MAXQSIZE;  
    62.   return OK;  
    63. }  
    64.   
    65. Status DeQueue(SqQueue &Q,QElemType &e)  
    66. { // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR  
    67.   if(Q.front==Q.rear) // 队列空  
    68.     return ERROR;  
    69.   e=Q.base[Q.front];  
    70.   Q.front=(Q.front+1)%MAXQSIZE;  
    71.   return OK;  
    72. }  
    73.   
    74. Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))  
    75. { // 从队头到队尾依次对队列Q中每个元素调用函数vi().一旦vi失败,则操作失败  
    76.   int i;  
    77.   i=Q.front;  
    78.   while(i!=Q.rear)  
    79.   {  
    80.     vi(*(Q.base+i));  
    81.     i=(i+1)%MAXQSIZE;  
    82.   }  
    83.   printf(" ");  
    84.   return OK;  
    85. } 
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/heyonggang/p/3388590.html