当前位置:   article > 正文

增加了front和rear后的顺序队列_队列front 和 rear

队列front 和 rear

有了front使得取出顺序队列首元素的操作不用再移动后面的数据元素节点,时间复杂度变为O(1);有了rear使得链式队列的插入操作不用遍历整个队列,时间复杂度也是O(1)

头文件

  1. #ifndef __SEQQUEUE_H__
  2. #define __SEQQUEUE_H__
  3. typedef void SeqQueue;
  4. SeqQueue* SeqQueue_Create(int capacity);
  5. void SeqQueue_Destroy(SeqQueue* queue);
  6. void SeqQueue_Clear(SeqQueue* queue);
  7. int SeqQueue_Append(SeqQueue* queue, void* item);
  8. void* SeqQueue_Retrieve(SeqQueue* queue);
  9. void* SeqQueue_Header(SeqQueue* queue);
  10. int SeqQueue_Length(SeqQueue* queue);
  11. int SeqQueue_Capacity(SeqQueue* queue);
  12. #endif

模块文件

  1. #include <malloc.h>
  2. #include "SeqQueueV2.h"
  3. typedef unsigned int TSeqQueueNode;
  4. typedef struct _tag_SeqQueue{
  5. int capacity;
  6. int length;
  7. int front;//指向队列头部,实质是一个下标
  8. int rear;//指向队列尾部,实质是一个下标
  9. TSeqQueueNode* node;
  10. }TSeqQueue;
  11. SeqQueue* SeqQueue_Create(int capacity)
  12. {
  13. TSeqQueue* ret = NULL;
  14. if(capacity > 0){
  15. ret = (TSeqQueue*)malloc(sizeof(TSeqQueue) + sizeof(TSeqQueueNode)*capacity);
  16. }
  17. if(ret != NULL){
  18. ret->capacity = capacity;
  19. ret->length = 0;
  20. ret->front = 0;//一开始的时候都为0
  21. ret->rear = 0;
  22. ret->node = (TSeqQueueNode*)(ret+1);//通过指针运算使得node指向真正的数据元素节点
  23. }
  24. return ret;
  25. }
  26. void SeqQueue_Destroy(SeqQueue* queue)
  27. {
  28. free(queue);
  29. }
  30. void SeqQueue_Clear(SeqQueue* queue)
  31. {
  32. TSeqQueue* sQueue = (TSeqQueue*)queue;
  33. if(sQueue != NULL){
  34. sQueue->length = 0;
  35. sQueue->front = 0;
  36. sQueue->rear = 0;
  37. }
  38. }
  39. int SeqQueue_Append(SeqQueue* queue, void* item)
  40. {
  41. TSeqQueue* sQueue = (TSeqQueue*)queue;
  42. int ret = (sQueue != NULL) && (item !=NULL) && (sQueue->length < sQueue->capacity);
  43. if(ret){
  44. sQueue->node[sQueue->rear] = (TSeqQueueNode)item;
  45. sQueue->rear = (sQueue->rear + 1) % sQueue->capacity;//注意这个技巧,循环使用队列中的空间
  46. sQueue->length++;
  47. }
  48. return ret;
  49. }
  50. void* SeqQueue_Retrieve(SeqQueue* queue)
  51. {
  52. TSeqQueue* sQueue = (TSeqQueue*)queue;
  53. void* ret = SeqQueue_Header(queue);
  54. if(sQueue != NULL){
  55. sQueue->front = (sQueue->front + 1) % sQueue->capacity;注意这个技巧,循环使用队列中的空间
  56. sQueue->length--;
  57. }
  58. return ret;
  59. }
  60. void* SeqQueue_Header(SeqQueue* queue)
  61. {
  62. TSeqQueue* sQueue = (TSeqQueue*)queue;
  63. void* ret = NULL;
  64. if((sQueue != NULL) && (sQueue->length > 0)){
  65. ret = (void*)(sQueue->node[sQueue->front]);//注意类型转换
  66. }
  67. return ret;
  68. }
  69. int SeqQueue_Length(SeqQueue* queue)
  70. {
  71. TSeqQueue* sQueue = (TSeqQueue*)queue;
  72. int ret = -1;
  73. if(sQueue != NULL){
  74. ret = (sQueue->length);
  75. }
  76. return ret;
  77. }
  78. int SeqQueue_Capacity(SeqQueue* queue)
  79. {
  80. TSeqQueue* sQueue = (TSeqQueue*)queue;
  81. int ret = -1;
  82. if(sQueue != NULL){
  83. ret = (sQueue->capacity);
  84. }
  85. return ret;
  86. }

测试文件

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "SeqQueueV2.h"
  4. /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  5. int main(int argc, char *argv[])
  6. {
  7. SeqQueue* queue = SeqQueue_Create(6);
  8. int a[10] = {0};
  9. int i = 0;
  10. for(i=0; i<10; i++)
  11. {
  12. a[i] = i + 1;
  13. SeqQueue_Append(queue, a + i);
  14. }
  15. printf("Header: %d\n", *(int*)SeqQueue_Header(queue));
  16. printf("Length: %d\n", SeqQueue_Length(queue));
  17. printf("Capacity: %d\n", SeqQueue_Capacity(queue));
  18. while( SeqQueue_Length(queue) > 0 )
  19. {
  20. printf("Retrieve: %d\n", *(int*)SeqQueue_Retrieve(queue));
  21. }
  22. printf("\n");
  23. for(i=0; i<10; i++)
  24. {
  25. a[i] = i + 1;
  26. SeqQueue_Append(queue, a + i);
  27. printf("Retrieve: %d\n", *(int*)SeqQueue_Retrieve(queue));
  28. }
  29. SeqQueue_Destroy(queue);
  30. return 0;
  31. }


本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/975032
推荐阅读
相关标签
  

闽ICP备14008679号