顺序队列

  1 /*
  2 顺序队列
  3 LJK 2018-07-04
  4 */
  5 /*
  6 队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。
  7 先进先出（简称FIFOI），允许插入的一端称为队尾，允许删除的一端称为队头
  8 队列的头尾相接的顺序存储结构称为循环队列
  9 当front = rear 时，此时队列为空队列而非剩一个元素，为了避免只有一个元素时，队头和队尾重合使处理变的麻烦
 10 重要公式：1.队列满：(rear + 1) % MAXSIZE == front
 11           2.长度公式:(rear - front + MAXSIZE) % MAXSIZE
 12           3.rear指针向后移一位:Q->rear = (Q->rear + 1) % MAXSIZE
 13 */ 
 14 
 15 #include<stdio.h>
 16 #include<stdlib.h>
 17 #include<cmath>
 18 
 19 #define OK 1
 20 #define ERROR 0
 21 #define TRUE 1
 22 #define FALSE 0
 23 #define MAXSIZE 20     // 存储空间初始分配量
 24 
 25 typedef int QElemType;
 26 typedef int Status;
 27 
 28 typedef struct
 29 {
 30     QElemType data[MAXSIZE];
 31     int front;
 32     int rear;
 33 }SqQueue;
 34 
 35 Status InitQueue(SqQueue *Q)
 36 {
 37     Q->front = Q->rear = 0;
 38     return OK; 
 39 }
 40 
 41 Status QueueEmpty(SqQueue Q)
 42 {
 43     if (Q.front == Q.rear) return TRUE;
 44     else return FALSE;
 45 }
 46 
 47 Status EnQueue(SqQueue *Q, QElemType e)
 48 {
 49     if ((Q->rear + 1) % MAXSIZE == Q->front) return ERROR; // 队列已满
 50     Q->data[Q->rear] = e;
 51     Q->rear = (Q->rear + 1) % MAXSIZE; // rear指针向后移一位，若到最后转到数组头
 52     return OK;
 53 }
 54 
 55 Status QueueTraverse(SqQueue Q)
 56 {
 57     int i = Q.front;
 58     while (i!=Q.rear)
 59     {
 60         printf("%d ", Q.data[i]);
 61         i = (i + 1) % MAXSIZE;
 62     }
 63     printf("
");
 64     return OK;
 65 }
 66 
 67 int QueueLength(SqQueue Q)
 68 {
 69     return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
 70 }
 71 
 72 Status DeQueue(SqQueue *Q, QElemType *e)
 73 {
 74     if (Q->front == Q->rear) return ERROR;
 75     *e = Q->data[Q->front];
 76     Q->front = (Q->front + 1) % MAXSIZE;  // front指针向前移一位 
 77     return OK;
 78 }
 79 
 80 Status GetHead(SqQueue Q, QElemType *e)
 81 {
 82     if (Q.front == Q.rear) return ERROR;
 83     *e = Q.data[Q.front];
 84     return OK;
 85 }
 86 
 87 Status ClearQueue(SqQueue *Q)
 88 {
 89     Q->front = Q->rear = 0;
 90     return OK;
 91 }
 92 
 93 int main()
 94 {
 95     Status j;
 96     int i = 0, l;
 97     QElemType d;
 98     SqQueue q;
 99 
100     InitQueue(&q);
101     printf("初始化后，是否为空 %d (1:空 0:否)
", QueueEmpty(q));
102 
103     printf("插入一些数据:
");
104     do
105     {
106         d = i + 100;
107         if (d == -1) break;
108         i++;
109         EnQueue(&q, d);
110     } while (i < MAXSIZE-1);
111     QueueTraverse(q);
112     printf("
");
113 
114     printf("Len(queue) = %d
", QueueLength(q));
115     printf("是否为空 %d (1:空 0:否)
", QueueEmpty(q));
116     printf("
");
117 
118     printf("连续%d次由队头删除元素，队尾插入元素
", MAXSIZE);
119     for ( l = 1; l < MAXSIZE; l++)
120     {
121         DeQueue(&q, &d);
122         printf("删除的元素是%d,插入的元素是%d 
", d, l + 1000);
123         d = l + 1000;
124         EnQueue(&q, d);
125     }
126     l = QueueLength(q);
127 
128     printf("Queue:");
129     QueueTraverse(q);
130     printf("
");
131 
132     j = GetHead(q, &d);
133     if (j) printf("HeadData:%d
", d);
134 
135     ClearQueue(&q);
136     printf("清空队列后，是否为空 %d (1:空 0:否)
", QueueEmpty(q));
137 
138     getchar();
139     return 0;
140 }