一、队列
队列是一种限定性的线性表，只能在队尾进行插入，在队头删除操作。先进先出的线性表。
二、顺序队列
上图所示，入队和出队的操作中，头、尾指针只增加不减小，导致被删除元素的空间永远无法重新利用。尽管数组中的元素个数远远小于数组大小，但由于尾指针已经指向向量空间的上限，导致不能进行入队操作，这种现象称为“假溢出”现象。
为了解决“假溢出”的问题，我们往往在定义一个顺序队列时，定义的是一个循环队列，即：将队列分配的空间看成是一个首尾相接的圆环。如下图所示：
循环队列为空时，对头指针和队尾指针的位置是相同的，为了解决循环队列无法区分队空和队满的情况，让循环队列中队尾指针永远指向一个空白区域：
1. 顺序队列的结构体设计
#define MAXSIZE 10//线性表长度的最大值
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int Status;//状态值
typedef int ElemType;//结点的数据类型，视实际情况而定。在此以int为例。
typedef struct SqQueue{
ElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
2.初始化一个空队列
Status InitSqQueue(SqQueue *Q){
Q->front = Q->rear = 0;
return OK;
}
3.清空队列
Status ClearSqQueue(SqQueue *Q) {
Q->rear = Q->front = 0;
return OK;
}
4.队列是否为空
//判断循环队列是否为空
int isSqQueueClear(SqQueue Q) {
if (Q.rear == Q.front) {
return 1;
}else {
return 0;
}
}
5.获取队列的长度
int GetSqQueueLength(SqQueue Q) {
int length = Q.rear-Q.front;
return length;
}
6.出队
Status PopSqQueue(SqQueue *Q, ElemType *e) {
//队列为空不能出队
if (Q->front == Q->front) {
return ERROR;
}
//返回出队元素
*e = Q->data[Q->front];
Q->front = (Q->front+1)%MAXSIZE;
return OK;
}
7.入队
Status PushSqQueue(SqQueue *Q, ElemType e) {
//队满不能入队
if ((Q->rear+1)%MAXSIZE == Q->front) {
return ERROR;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return OK;
}
8.遍历
void TraverseSqQueue(SqQueue Q) {
int i = Q.front;
while (i != Q.rear) {
printf("%d ",Q.data[i]);
i = (i+1)%MAXSIZE;
}
printf("\n");
}
二、链式队列
1. 链式队列的结构体设计
//结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *NodePtr;
//队列链表
typedef struct LinkQueue{
NodePtr front;
NodePtr rear;
}LinkQueue;
2.初始化一个空队列
Status InitLinkQueue(LinkQueue *Q){
Q->rear = Q->front = (NodePtr)malloc(sizeof(Node));
if (Q->front == NULL) {
return ERROR;
}
Q->front->next = NULL;
return OK;
}
3.清空队列
//清空队列
Status ClearLinkQueue(LinkQueue *Q){
NodePtr p,q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p) {
q=p;
p=p->next;
free(q);
}
return OK;
}
4.队列是否为空
int IsEmpty(LinkQueue Q){
if (Q.front->next == Q.rear->next) {
return 1;
}
return 0;
}
5.获取队列的长度
int LinkQueueLength(LinkQueue Q){
int i = 0;
NodePtr p = Q.front;
while (p != Q.rear) {
i++;
p = p->next;
}
return i;
}
6.出队
Status PopLinkQueue(LinkQueue *Q){
if (Q->front == Q->rear) {
return ERROR;
}
NodePtr temp = Q->front->next;
Q->front->next = temp->next;
free(temp);
return OK;
}
7.入队
Status PushLinkQueue(LinkQueue *Q, ElemType e) {
NodePtr p = (NodePtr)malloc(sizeof(Node));
if (p == NULL) {
return ERROR;
}
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = Q->rear->next;
return OK;
}
8.遍历
void TranverseLinkQueue(LinkQueue Q){
NodePtr p = Q.front->next;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
9.销毁队列
//销毁队列
Status DeletLinkQueue(LinkQueue *Q){
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
