队列特性
1.限定只能在表的一端进行插入和在另一端进行删除操作的线性表。所以，队列的物理结构是线性的
2.队列是先进先出的
队列的顺序实现
队列的定义
#define MAXSIZE 100
typedef int Status;
typedef int ElementType;
#include <stdio.h>
typedef struct {
ElementType data[MAXSIZE];
ElementType front;//队列的头
ElementType rear;//队列的尾
}LineQueue;
思索问题
先看图
队列
如果不停操作，会变成图d这种情况，在队尾指针已满的情况下，队头有空的位置，此时，你如法再次插入，造成了假溢出。
思考一：你可能想到，保持对头位置不变，移动元素，但这样会消耗很多性能
思考二：队头不在第一个位置，队尾已满，此时队尾从第一个位置开始，那么，如何判断队列满了呢？
总之，可能会有很多解决方法，但是，循环队列的实现，可以完美解决。如果没有特别说明，队列的顺序实现就是循环队列
image.png
队列的初始化
//初始化
Status initLineQueue(LineQueue *queue){
queue->front = queue->rear = 0;
return OK;
}
入队
Status EnLineQueue(LineQueue *queue,ElementType e){
if (queue->front == (queue->rear + 1)%MAXSIZE)
return ERROR;
//入队元素插入队尾
queue->data[queue->rear] = e;
//移动队尾指针
queue->rear = (queue->rear+1)%MAXSIZE;
return OK;
}
出队
//出队
Status deLineQueue(LineQueue *queue,ElementType *e){
if (queue->front == queue->rear)
return ERROR;
//返回出对元素
*e = queue->data[queue->front];
//移动队头指针
queue->front = (queue->front+1)%MAXSIZE;
return OK;
}
获取队头
//获取队头
Status getTopFromLineQueue(LineQueue queue, ElementType *e){
if (queue.front == queue.rear)
return ERROR;
*e = queue.data[queue.front];
return OK;
}
清除队列
//清除队列
Status clearLineQueue(LineQueue *queue){
queue->front = queue->rear = 0;
return OK;
}
队列长度
//队列长度
Status lineQueueLength(LineQueue queue){
return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}
队列是否为空
//队列是否为空
Status lineQueueIsEmpty(LineQueue queue){
//队头与队尾相等，表示队列为空
if (queue.front == queue.rear)
return TRUE;
return FALSE;
}
队列是否为满
//队列是否为满
Status lineQueueIsFull(LineQueue queue){
//队尾➕1,取总数的模与队头相等，表示队列已满
if (queue.front == (queue.rear+1)%MAXSIZE)
return TRUE;
return FALSE;
}
队列的链式实现
链式队列的定义
//队列链式结构的节点
typedef struct QueueNode {
ElementType data;
struct QueueNode *next;
}QueueNode, *LinkQueueNode;
//队列链式结构
typedef struct {
LinkQueueNode front;//队列的头
LinkQueueNode rear;//队列的尾
int length;//元素个数，可有可无
}LinkQueue;
初始化
//初始化
Status initLinkQueue(LinkQueue *queue){
//链式队列头尾指针创建
queue->front = queue->rear = malloc(sizeof(QueueNode));
//头尾指针初始指向NULL
queue->front->next = NULL;
//设置队列长度为0
queue->length = 0;
return OK;
}
链式队列元素入队
//入队
Status EnLinkQueue(LinkQueue *queue,ElementType e){
//队尾指针不存在，直接返回错误
if (!queue->rear)
return ERROR;
//创建队列元素
LinkQueueNode temp = malloc(sizeof(QueueNode));
if (!temp)//节点不存在
return ERROR;
temp->data = e;
temp->next = NULL;
//入队元素插入队尾
queue->rear->next = temp;
//移动队尾指针
queue->rear = temp;
//元素个数加1
queue->length++;
return OK;
}
链式队列出队
//出队
Status deLinkQueue(LinkQueue *queue,ElementType *e){
//对头节点不存在，直接报错
if (!queue->front)
return ERROR;
//队列为空，直接报错
if(queue->front == queue->rear)
return ERROR;
//记录该节点
LinkQueueNode temp = queue->front->next;
//返回出对元素
*e = temp->data;
//移动队头指针
queue->front->next = temp->next;
//释放该节点
free(temp);
//元素个数减1
queue->length--;
//如果删除的是最后一个节点，应将队尾指向队头
if (queue->rear == temp)
queue->rear = queue->front;
return OK;
}
获取链式队列队头元素
//获取链式队列队头元素
Status getTopFromLinkQueue(LinkQueue queue, ElementType *e){
//对头节点不存在，直接报错
if (!queue.front)
return ERROR;
//队列为空，直接报错
if(queue.front == queue.rear)
return ERROR;
*e = queue.front->next->data;
return OK;
}
链式队列清空
//清空队列
Status clearLinkQueue(LinkQueue *queue){
//记录队头指针
LinkQueueNode p = queue->front->next;
//队尾与队头指针相同，后继指向NULL
queue->rear = queue->front;
queue->front->next = NULL;
//删除队列元素
while (p) {
LinkQueueNode q = p;
free(p);
p = q->next;
}
return OK;
}
链式队列销毁
//销毁队列
Status destroyLinkQueue(LinkQueue *queue){
//删除队列元素，包括头尾指针
while (queue->front) {
queue->rear = queue->front->next;
free(queue->front);
queue->front = queue->rear;
}
return OK;
}
链式队列长度
//链式队列长度
Status linkQueueLength(LinkQueue queue){
//如果结构中设计了长度，直接获取
//return queue.length;
//遍历队列，统计个数
int length = 0;
while (queue.front && queue.front != queue.rear) {
length++;
queue.front = queue.front->next;
}
return length;
}
链式队列是否为空
//链式队列是否为空
Status linkQueueIsEmpty(LinkQueue queue){
//队头与队尾相等，表示队列为空
if (queue.front == queue.rear)
return TRUE;
return FALSE;
}
网友评论