队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。
队列是一种先进先出的线性表，简称FIFO，把允许插入的一端称为队尾，允许删除的一端称为队头。
根据物理结构，队列也有两种，顺序队列和链式队列。
顺序队列
顺序队列的基本操作
Status InitQueue(SqQueue *Q){
Q->front = Q->rear = 0;
return OK;
}
Status ClearQueue(SqQueue *Q){
Q->front = Q->rear = 0;
return OK;
}
Status QueueEmpty(SqQueue Q){
if(Q.front == Q.rear) return YES;
return NO;
}
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
Status GetHead(SqQueue Q,QElemType *e){
if(Q.front == Q.rear) return ERROR;
*e = Q.data[Q.front];
return OK;
}
Status EnQueue(SqQueue *Q,QElemType e){
if((Q->rear) == MAXSIZE) return ERROR;
Q->data[Q->rear++] = e;
return OK;
}
#if 0
//算法复杂度为O(n)
Status DeQueue(SqQueue *Q,QElemType *e){
if(Q->front == Q->rear) return ERROR;
*e = Q->data[Q->front];
for(int i = 0; i < Q->rear; i++){
Q->data[i] = Q->data[i+1];
}
Q->rear--;
return OK;
}
#else
//存在假溢出问题
Status DeQueue(SqQueue *Q,QElemType *e){
if(Q->front > Q->rear) return ERROR;
*e = Q->data[Q->front];
Q->front++;
return 0;
}
#endif
Status QueueTraverse(SqQueue Q){
int i = Q.front;
while(i != Q.rear){
printf("%d ", Q.data[i]);
i ++;
}
printf("\n");
return OK;
}
顺序队列在出栈的时候，有两种实现方式：
1、当队头移出之后，再将后面的数据元素全部往前移动一个位置，这种方法的算法复杂度较高；
2、不将数据元素移动，而是将front指针移动，当一个数据元素出栈后，将front指向后一个数据元素。但是，当所有元素都出栈后，front和rear都指向了队尾，此时根据Push函数中的条件：if((Q->rear) == MAXSIZE) return ERROR; 无法再向此栈中添加元素，这种现象称为“假溢出”。
为了实现高效的队列，即高效的、没有“假溢出”情况。引出循环队列的概念。
循环队列定义：把队列的这种头尾相接的顺序存储结构称为循环队列。
重点：
1、循环队列如何判空和判满。当空队列的时候，front == rear；当满队列的时候front == rear；这种情况无法判断当前是空队列还是满队列。为了解决这个问题，将队列的最后一个位置空出来不存储数据，此时空队列判断方法仍然是front == rear，而满队列则是rear+1 == front，但由于循环，rear可能比front多出一圈，因为，判断满栈的条件是（rear+1）%MAXSIZE==front。
2、队列的长度问题。原本队列的长度为rear-front，但因为循环了可能出现rear比front小的情况，此时判断队列的长度就不能直接相减，能用的公式为(rear-front+MAXSIZE)%MAXSIZE。
循环队列的基本操作
Status InitQueue(SqQueue *Q){
Q->front = Q->rear = 0;
return OK;
}
Status ClearQueue(SqQueue *Q){
Q->front = Q->rear = 0;
return OK;
}
Status QueueEmpty(SqQueue Q){
if(Q.front == Q.rear) return YES;
return NO;
}
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
Status GetHead(SqQueue Q,QElemType *e){
if(QueueEmpty(Q)) return ERROR;
*e = Q.data[Q.front];
return OK;
}
Status EnQueue(SqQueue *Q,QElemType e){
if((Q->rear+1)%MAXSIZE == Q->front) return ERROR;
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return OK;
}
Status DeQueue(SqQueue *Q,QElemType *e){
if(QueueEmpty(*Q)) return ERROR;
*e = Q->data[Q->front];
Q->front = (Q->front+1)%MAXSIZE;
printf("出队的元素:%d\n",*e);
return 0;
}
Status QueueTraverse(SqQueue Q){
int i = Q.front;
while(i != Q.rear){
printf("%d ", Q.data[i]);
i = (i+1)%MAXSIZE;
}
printf("\n");
return OK;
}
总结：循环顺序队列，既提高了算法的效率，也解决了“假溢出”的问题。
链式队列
链式队列定义：队列的链式存储结构，其实也是线性表的单链表，只不过它只能尾进头出而已，我们简称链队列。
我们将队头的指针指向链队列的头结点，而队尾指针指向了尾结点。因此，空队列的时候，队头指针和队尾指针都指向了头结点。
链式队列的基本操作
Status InitQueue(LinkQueue *Q){
QNodePtr temp = (QNodePtr)malloc(sizeof(QNode));
temp->data = -1;
temp->next = NULL;
if(temp == NULL) return ERROR;
Q->front = Q->rear = temp;
return OK;
}
Status DestoryQueue(LinkQueue *Q){
while(Q->front != NULL){
QNodePtr temp = Q->front->next;
Q->front = Q->front->next;
free(temp);
}
return OK;
}
Status ClearQueue(LinkQueue *Q){
Q->rear = Q->front;
QNodePtr p = Q->front->next;
Q->front->next = NULL;
while(p != NULL){
QNodePtr temp = p;
p = p->next;
free(temp);
}
return OK;
}
Status QueueEmpty(LinkQueue Q){
if(Q.front == Q.rear) return YES;
return NO;
}
int QueueLength(LinkQueue Q){
QNodePtr p = Q.front;
int i = 0;
while(p->next != NULL){
i++;
p = p->next;
}
return i;
}
Status EnQueue(LinkQueue *Q,QElemType e){
if(Q == NULL) return ERROR;
QNodePtr temp = (QNodePtr)malloc(sizeof(QNode));
if(temp == NULL) return ERROR;
temp->data = e;
temp->next = NULL;
Q->rear->next = temp;
Q->rear = temp;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e){
if(Q->front == Q->rear) return ERROR;
QNodePtr temp = Q->front->next;
*e = temp->data;
Q->front->next = temp->next;
if(Q->rear == temp)
Q->rear = Q->front;
free(temp);
return OK;
}
Status GetHead(LinkQueue Q,QElemType *e){
if(Q.front == Q.rear) return ERROR;
*e = Q.front->next->data;
return OK;
}
Status QueueTraverse(LinkQueue Q){
QNodePtr p = Q.front->next;
while(p){
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
注意点：
1、链式队列有头结点的概念，所以清空队列的时候，只需要将数据元素清除，头结点不需要清除，而销毁队列时，需要连同头结点一块释放。
2、出栈操作，当栈里面只有一个数据元素时，出栈后需要将rear指向头结点。
