Chinaunix首页 | 论坛 | 博客
  • 博客访问: 35662
  • 博文数量: 24
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 246
  • 用 户 组: 普通用户
  • 注册时间: 2016-02-14 20:13
  • 认证徽章:
文章分类

全部博文(24)

文章存档

2017年(5)

2016年(19)

我的朋友

分类: C/C++

2016-03-08 08:21:53


  1. /*
  2.  * 根据郝斌老师视频整理
  3.  * 编译环境:
  4.  * guo@linux:~$ gcc --version
  5.  * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
  6.  * 静态循环队列
  7.  */
  8. #include <stdio.h>
  9. #include <malloc.h>

  10. #define QUEUE_LENGTH 6
  11. #define FALSE 0
  12. #define TRUE 1

  13. typedef struct Queue
  14. {
  15.     int *pBase;
  16.     int front;
  17.     int rear;
  18. }QUEUE, *PQUEUE;


  19. /**********************声明**********************************/
  20. /*初始化静态循环队列*/
  21. void InitQueue(PQUEUE pQueue);
  22. /*判断队列是否已满*/
  23. int IsFullQueue(PQUEUE pQueue);
  24. /*判断队列是否为空*/
  25. int IsEmptyQueue(PQUEUE pQueue);
  26. /*入队*/
  27. int EnQueue(PQUEUE pQueue, int val);
  28. /*出队*/
  29. void DeQueue(PQUEUE pQueue, int *pVal);
  30. /*遍历*/
  31. void TraverseQueue(PQUEUE pQueue);


  32. /*
  33.  * 函数名称:InitQueue。
  34.  * 输入参数:pQueue队列的地址。
  35.  * 输出参数:无。
  36.  * 函数说明:新建一个静态队列。
  37.  * 申请一块内存,作为int类型的数组,长度为QUEUE_LENGTH。
  38.  * front(头部)和rear(尾部)作为数组的下标。
  39.  * 队列的特点是"先入先出"
  40.  */
  41. void InitQueue(PQUEUE pQueue)
  42. {
  43.     pQueue->pBase = (int *)malloc(sizeof(int)*QUEUE_LENGTH);
  44.     pQueue->front = 0;
  45.     pQueue->rear = 0;

  46.     return ;
  47. }


  1. /*
  2.  * 函数名称:IsFullQueue。
  3.  * 输入参数:pQueue队列的地址。
  4.  * 输出参数:如果队列已满,返回TRUE;否则返回FALSE。
  5.  * 函数说明:判断一个队列是否已满。
  6.  * 如果数组只剩一个位置没有有效元素,则认为队列已满。
  7.  * rear是最后一个有效元素的下一个位置。
  8.  * 还有一种方式是增加一个变量,记录队列个数来判断队列是否已满。不常用此方法。
  9.  */
  10. int IsFullQueue(PQUEUE pQueue)
  11. {
  12.     if ((pQueue->rear+1)%QUEUE_LENGTH == pQueue->front)
  13.         return TRUE;
  14.     else
  15.         return FALSE;
  16. }


  1. /*
  2.  * 函数名称:IsEmptyQueue。
  3.  * 输入参数:pQueue队列的地址。
  4.  * 输出参数:如果队列为空,返回TRUE;否则返回FALSE。
  5.  * 函数说明:判断一个队列是否为空。
  6.  * 如果数组的rear下标和front下标相等,则认为队列为空。
  7.  */
  8. int IsEmptyQueue(PQUEUE pQueue)
  9. {
  10.     if (pQueue->rear == pQueue->front)
  11.         return TRUE;
  12.     else
  13.         return FALSE;
  14. }


  1. /*
  2.  * 函数名称:EnQueue。
  3.  * 输入参数:pQueue队列的地址;value要入队的元素。
  4.  * 输出参数:入队成功,返回TRUE;队列已满,返回FALSE。
  5.  * 函数说明:入队。
  6.  */
  7. int EnQueue(PQUEUE pQueue, int value)
  8. {
  9.     if (IsFullQueue(pQueue))
  10.     {
  11.         printf("Queue is full!\n");
  12.         return FALSE;
  13.     }
  14.     else
  15.     {
  16.         pQueue->pBase[pQueue->rear] = value;
  17.         /*rear是最后一个有效元素的下一个位置*/
  18.         pQueue->rear = (pQueue->rear+1) % QUEUE_LENGTH;
  19.         return TRUE;
  20.     }
  21. }

  1. /*
  2.  * 函数名称:TraverseQueue。
  3.  * 输入参数:pQueue队列的地址。
  4.  * 输出参数:无。
  5.  * 函数说明:将静态循环队列遍历输出。
  6.  */
  7. void TraverseQueue(PQUEUE pQueue)
  8. {
  9.     int i = pQueue->front;
  10.     
  11.     while (i != pQueue->rear)
  12.     {
  13.         printf("%d ", pQueue->pBase[i]);
  14.         i = (i+1) % QUEUE_LENGTH;
  15.     }
  16.     printf("\n");
  17.     
  18.     return;
  19. }


  1. /*
  2.  * 函数名称:DeQueue。
  3.  * 输入参数:pQueue队列的地址;pValue存储出队的元素。
  4.  * 输出参数:无。
  5.  * 函数说明:出队,并将出队元素保存。
  6.  */
  7. void DeQueue(PQUEUE pQueue, int *pValue)
  8. {
  9.     if (IsEmptyQueue(pQueue))
  10.         return;
  11.     *pValue = pQueue->pBase[pQueue->front];
  12.     pQueue->front = (pQueue->front + 1) % QUEUE_LENGTH;

  13.     return ;
  14. }

  15. int main(void)
  16. {
  17.     QUEUE queue;
  18.     int TempValue;
  19.     
  20.     InitQueue(&queue);
  21.     
  22.     EnQueue(&queue, 1);
  23.     EnQueue(&queue, 2);
  24.     EnQueue(&queue, 3);
  25.     EnQueue(&queue, 4);
  26.     EnQueue(&queue, 5);
  27.     EnQueue(&queue, 6);
  28.     EnQueue(&queue, 7);
  29.     EnQueue(&queue, 8);
  30.     
  31.     TraverseQueue(&queue);
  32.     
  33.     DeQueue(&queue, &TempValue);
  34.     TraverseQueue(&queue);
  35.     printf("Dequeue is %d\n", TempValue);

  36.     EnQueue(&queue, 6);
  37.     EnQueue(&queue, 7);
  38.     
  39.     DeQueue(&queue, &TempValue);
  40.     TraverseQueue(&queue);
  41.     printf("Dequeue is %d\n", TempValue);
  42.     
  43.     return 0;
  44. }



阅读(609) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册