队列的基本操作！

浅浅的花香味﹌ 2022-04-11 08:08 410阅读 0赞

1.链式队列

//队列结点结构体

typedef struct QNode

{ QElemType data;

QNode *next;

}*Queueptr;

-——————————————-

//指向结点的指针

struct LinkQueue

{ Queueptr front,rear;

}

[cpp] view plain copy print ?

  1. void InitQueue(LinkQueue &Q)
  2. { // 构造一个空队列Q
  3. if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
  4. exit(OVERFLOW);
  5. Q.front->next=NULL;
  6. }
  8. void DestroyQueue(LinkQueue &Q)
  9. { // 销毁队列Q(无论空否均可)
  10. while(Q.front)
  11. {
  12. Q.rear=Q.front->next;
  13. free(Q.front);
  14. Q.front=Q.rear;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空
  15. }
  16. }
  18. void ClearQueue(LinkQueue &Q)
  19. { // 将Q清为空队列
  20. QueuePtr p,q;
  21. Q.rear=Q.front;
  22. p=Q.front->next;
  23. Q.front->next=NULL;//只留下头结点
  24. while(p)
  25. {
  26. q=p;
  27. p=p->next;
  28. free(q);
  29. }
  30. }
  32. Status QueueEmpty(LinkQueue Q)
  33. { // 若Q为空队列，则返回TRUE，否则返回FALSE
  34. if(Q.front->next==NULL)//注意不要把链式队列的判空条件与循环队列混淆
  35. return TRUE;
  36. else
  37. return FALSE;
  38. }
  40. int QueueLength(LinkQueue Q)
  41. { // 求队列的长度
  42. int i=0;
  43. QueuePtr p;
  44. p=Q.front;
  45. while(Q.rear!=p)
  46. {
  47. i++;
  48. p=p->next;
  49. }
  50. return i;
  51. }
  53. Status GetHead(LinkQueue Q,QElemType &e)
  54. { // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR
  55. QueuePtr p;
  56. if(Q.front==Q.rear)
  57. return ERROR;
  58. p=Q.front->next;
  59. e=p->data;
  60. return OK;
  61. }
  63. void EnQueue(LinkQueue &Q,QElemType e)
  64. { // 插入元素e为Q的新的队尾元素
  65. QueuePtr p;
  66. if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败
  67. exit(OVERFLOW);
  68. p->data=e;
  69. p->next=NULL;
  70. Q.rear->next=p;
  71. Q.rear=p;
  72. }
  74. Status DeQueue(LinkQueue &Q,QElemType &e)
  75. { // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
  76. QueuePtr p;
  77. if(Q.front==Q.rear)
  78. return ERROR;
  79. p=Q.front->next;
  80. e=p->data;
  81. Q.front->next=p->next;
  82. if(Q.rear==p)
  83. Q.rear=Q.front;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值
  84. free(p);
  85. return OK;
  86. }
  88. void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
  89. { // 从队头到队尾依次对队列Q中每个元素调用函数vi()
  90. QueuePtr p;
  91. p=Q.front->next;
  92. while(p)
  93. {
  94. vi(p->data);
  95. p=p->next;
  96. }
  97. printf(“\n”);

  98. }</STRONG>

    void InitQueue(LinkQueue &Q) { // 构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) 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;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空 } } 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(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; if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败 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;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值 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”); }

2.顺序队列—-循环队列

性质如下:

1.头指针指向对头元素，尾指针指向队尾的下一个位置。(这里的指针都是为指针，实际是数组序号)

2.为了区分队满与对空，则定义一个存储空间为MAX_QSIZE大小的队列只允许存放MAX_QSIZE-1个数据。

3.判空条件为:if(Q.front ==Q.rear) return true;

判满条件为:if((Q.rear+1)%MAX_QSIZE==Q.front) return true;

4.循环队列的长度为:(Q.read-Q.front+MAX_SIZE)%MAX_QSIZE

5.当删除对头元素或者在对尾插入元素时指针均需向后移动。操作为:

Q.rear=(Q.rear+1)%MAX_QSIZE;

Q.front=(Q.front+1)%MAX_QSIZE;

结构体定义如下:

struct SqQueue

{QElemType *base;//指向开辟的空间的首地址

int front;

int rear;

}

[cpp] view plain copy print ?

  1. void InitQueue(SqQueue &Q)
  2. { // 构造一个空队列Q
  3. Q.base=(QElemType *)malloc(MAX_QSIZE*sizeof(QElemType));
  4. if(!Q.base) // 存储分配失败
  5. exit(OVERFLOW);
  6. Q.front=Q.rear=0;
  7. }
  9. void DestroyQueue(SqQueue &Q)
  10. { // 销毁队列Q，Q不再存在
  11. if(Q.base)
  12. free(Q.base);
  13. Q.base=NULL;
  14. Q.front=Q.rear=0;
  15. }
  17. void ClearQueue(SqQueue &Q)
  18. { // 将Q清为空队列
  19. Q.front=Q.rear=0;
  20. }
  22. Status QueueEmpty(SqQueue Q)
  23. { // 若队列Q为空队列，则返回TRUE；否则返回FALSE
  24. if(Q.front==Q.rear) // 队列空的标志
  25. return TRUE;
  26. else
  27. return FALSE;
  28. }
  30. int QueueLength(SqQueue Q)
  31. { // 返回Q的元素个数，即队列的长度
  32. return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
  33. }
  35. Status GetHead(SqQueue Q,QElemType &e)
  36. { // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
  37. if(Q.front==Q.rear) // 队列空
  38. return ERROR;
  39. e=Q.base[Q.front];//等价于e=*(Q.base+Q.front)
  40. return OK;
  41. }
  43. Status EnQueue(SqQueue &Q,QElemType e)
  44. { // 插入元素e为Q的新的队尾元素
  45. if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满
  46. return ERROR;
  47. Q.base[Q.rear]=e;//等价于*(Q.base+Q.rear)=e
  48. Q.rear=(Q.rear+1)%MAX_QSIZE;
  49. return OK;
  50. }
  52. Status DeQueue(SqQueue &Q,QElemType &e)
  53. { // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
  54. if(Q.front==Q.rear) // 队列空
  55. return ERROR;
  56. e=Q.base[Q.front];
  57. Q.front=(Q.front+1)%MAX_QSIZE;
  58. return OK;
  59. }
  61. void QueueTraverse(SqQueue Q,void(*vi)(QElemType))
  62. { // 从队头到队尾依次对队列Q中每个元素调用函数vi()
  63. int i;
  64. i=Q.front;
  65. while(i!=Q.rear)
  66. {
  67. vi(Q.base[i]);
  68. i=(i+1)%MAX_QSIZE;
  69. }
  70. printf(“\n”);
  71. }

发表评论

表情：
评论列表 （有 0 条评论，410人围观）

还没有评论，来说两句吧...

相关阅读

    相关 队列的基本操作

    目录 一、什么是队列？ 二、用数组实现队列 代码实现： 数组实现的缺点： 三、用链表实现队列 代码实现： -------------------- 一、什么

    r囧r小猫r囧r小猫/ 0 赞/ 172 阅读

    相关 循环队列的基本操作

    循环队列设置不同队空与队满条件的解决方案 为了解决顺序队列假溢出的问题，我们采用的方案是少用一个元素空间，此时的指针状态是队尾指针加1才与队头指针重合，于是此时队满的判定

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 358 阅读