队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
特点：先进先出
循环队列
循环队列.png
队满.png
工作流程
- 当初始化队列为空时，front = rear = 0；
- 入队，rear+1，指向队尾的下一个存储单元，为了实现循环利用取模运算：rear = (rear+1) % max;
- 出队，front+1，指向下一个队首，实现循环：front = (front+1) % max;
- 判断队满，(Q.rear+1) % Q.max == Q.front。
疑问：为什么留一个存储单元就判断队列满了？
如果不留存储单元，队列 rear 指向的下一个位置是队首 front 的指向，即 front = rear。此时便不好判断队列是空的还是满的，所以我们可以牺牲一个存储单元，用来保持队尾和队首的距离，来解决队满与否的问题。
代码实现
定义
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
/* 队列结构 */
typedef struct {
ElemType *data;
int front; /* 记录队首元素位置 */
int rear; /* 记录对尾元素位置 */
int max; /* 记录开辟内存空间的大小 */
}SqQueue;
初始化一个空队列
Status InitQueue(SqQueue *Q, int n) {
Q->data = malloc(sizeof(ElemType) * n);
if (Q->data == NULL) return ERROR;
Q->max = n;
Q->front = Q->rear = 0;
return OK;
}
获得元素个数
int GetLength(SqQueue Q) {
return (Q.rear - Q.front + Q.max) % Q.max;
}
判断是不是空
Status QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear) {
return OK;
}
return ERROR;
}
队满
Status QueueFull(SqQueue Q) {
if ((Q.rear+1) % Q.max == Q.front) {
return OK;
}
return ERROR;
}
获得队首元素
Status GetFront(SqQueue Q, ElemType *e) {
if (QueueEmpty(Q) == OK) {
return ERROR;
}
*e = Q.data[Q.front];
return OK;
}
入队
Status EnQueue(SqQueue *Q, ElemType e) {
if (QueueFull(*Q)) return ERROR;
Q->data[Q->rear] = e;
// 队尾向后移动，取模运算，超出队尾，实现循环继续从队首开始
Q->rear = (Q->rear+1) % Q->max;
return OK;
}
出队
Status DeQueue(SqQueue *Q, ElemType *e) {
if (QueueEmpty(*Q) == OK) return ERROR;
*e = Q->data[Q->front];
// 队首位置向后移动一位
Q->front = (Q->front+1) % Q->max;
return OK;
}
遍历输出
Status QueuePrint(SqQueue *Q) {
/* 从队首开时输出，直到对尾 */
int i = Q->front;
while (i != Q->rear) {
printf("%d ",Q->data[I]);
i = (i+1) % Q->max;
}
printf("\n");
return ERROR;
}
链式队列
物理结构为链式存储结构的队列，对内存空间的利用率更高。
链式队列.png
与循环队列的区别
- 无需判断队列是否满了；
- 在内存空间中是不连续的，而循环对列是开辟连续的内存空间；
- 链式队列出队或清空队列时需要释放内存空间。
代码实现
定义
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
typedef struct QueueNode {
ElemType data;
struct QueueNode *next;
} QueueNode, *QueueNodePtr;
typedef struct {
QueueNodePtr front;
QueueNodePtr rear;
} LinkQueue;
初始化
Status InitQueue(LinkQueue *Q) {
// 初始队列为空,只有头节点，不是有效数据的节点
*Q->front = *Q->rear = (QueueNodePtr)malloc(sizeof(QueueNode));
if (*Q->front == NULL) return ERROR;
// 头节点的后面为空
*Q->front->next = NULL;
return OK;
}
判断队列为空
当队列为空时，恰入上图初始化的状态，只剩一个头节点，此时 Q.front == Q.rear
Status QueueEmpty(LinkQueue Q) {
if (Q.front == Q.rear) return TRUE;
return FALSE;
}
入列
入队.png
入列的操作，是将新元素，追加到rear指向的队尾之后，rear->next = 新元素，再将rear指向新元素，此时，新元素成为队尾。
Status EnQueue(LinkQueue *Q, ElemType e) {
QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));
if (p == NULL) return ERROR;
p->data = e;
p->next = NULL;
// 追加到队尾
*Q->rear->next = p;
// 标记成队尾
*Q->rear = p;
return OK;
}
出列
出队.png
出队列操作，是将首元节点从链队删除。
Status DeQueue(LinkQueue *Q, ElemType *e) {
if (QueueEmpty(*Q)) return ERROR;
QueueNodePtr head;
// 找到要删除的节点
head = *Q->front->next;
// 回调到函数外
*e = head->data;
// 更改头节点
*Q->front->next = head->next;
// 如果删到了队尾最后一个元素
if (*Q->rear == head)
*Q->rear = *Q->front;
// 删除临时指针指向的头节点
free(head);
return OK;
}
清空
Status ClearQueue(LinkQueue *Q) {
if (*Q->front->next == NULL) return ERROR;
QueueNodePtr temp, p; // 首元节点
*Q->rear = *Q->front;
p = *Q->front->next;
*Q->front->next = NULL;
// 此时只有temp指向首元节点
while (p) {
temp = p;
p = p->next;
free(temp);
}
return OK;
}
销毁
销毁操作，和清空不一样，清空仅仅删除除头节点以外的所有节点，清空后还可以再入队。但是销毁已经彻底不使用，需要连头节点也一并free掉，所以代码中是从front开始，而非front->next。
Status DestoryQueue(LinkQueue *Q) {
if (*Q->front->next == NULL) return ERROR;
// 头节点也是个malloc开辟的，也需要释放
while (*Q->front) {
*Q->rear = *Q->front->next;
free(*Q->front);
*Q->front = *Q->rear;
}
return OK;
}
获取队首
不更改队列，不破坏队列现有结构，仅查找。
Status GetHead(LinkQueue Q, ElemType *e) {
if (QueueEmpty(*Q)) return ERROR;
*e = Q.front->next->data;
return OK;
}
网友评论