这是数据结构的第4篇文章
我们上次了解到了单链表,双向链表,循环链表的特点和他们的代码表达。
那么再简单地回顾一下,链表是一种数据的存储方式,保存数据在内存中不连续,用指针进行访问。
那么今天讲的队列和链表又有什么关系呢?
队列是一种数据结构,它也是一种线性表,也因此可以用链表进行存储。
队列
队列并不难,在我们生活中也十分常见,就是简单的排队打饭。
排在队伍第一位的学生(表头)最先开始打饭,当他打完饭,就会从队伍中离开(出队),而第二个人也就往前走成为了第一个人。来的比较晚的同学就会排在队伍的最后面(表尾),这个过程也成为入队。
不难发现队列的特性:先进先出。
并且,队列的操作只能对队头和队尾进行操作。
结构定义
在这里就使用链表来完成队列这个数据结构好了。那么该怎么定义这个结构呢?
首先我们要能对队头和队尾进行操作,因此必然存在队头节点和队尾节点。然后考虑到我们需要统计到队列的长度,也就是节点的个数。
typedef struct node
{
void* data; //数据域指针
struct node *next; //指向当前结点的下一结点
} Node;
typedef struct Lqueue
{
Node *front; //队头
Node *rear; //队尾
size_t data_size; //数据域内存大小
} LQueue
初始化队列
初始化队列并不难,初始化一个队列,要确定:头节点、尾节点和队列长度。
先把头尾节点的数据设置为0(也就是暂无赋值),并且指定好存储在队列中的元素类型。
初始化时,rear = front=0,当队列不为空时,front指向队列中的第一个元素,rear指向队列中最后一个元素的下一个位置,当队列满时 rear=front,但不一定是位置0。
void InitAQueue(AQueue *Q,size_t data_size) //初始化循环队列
{
Q->data[MAXQUEUE];
Q->front = 0;
Q->rear = 0;
Q->data_size = data_size;
printf("队列创建成功!\n");
}
判断队列
插入后rear+1,删除后front+1,但是,无论是删除还是插入,一旦rear或front加一超过了所分配的空间,则让指针指向这片空间的起始位置;设所分配的空间为Maxsize,一旦rear+1,或front+1 =Maxsize, 则rear或front指向起始位置;如上图,当front和rear都在位置3事,此时如果想要插入,则判断3+1=4 与Maxsize 4的关系,相等,则rear=0,这个可以通过取余实现rear=(rear+1)%Maxsize;
因此,循环序列判空的方法是rear = front; 判满的方法是 (rear+1)%Maxsize ==front;
因此,循环序列判空的方法是rear = front; 判满的方法是 (rear+1)%Maxsize ==front;
Status IsEmptyAQueue(AQueue *Q) //判断循环队列是否为空
{
if(Q->front == Q->rear)
{
printf("队列为空!\n");
return TRUE;
}
else
{
printf("队列不为空!\n");
return FLASE;
}
}
入队
进队列步骤:
1.判断队列是否满,即,rear+1是否等于front,若等于则队列已满,不允许进入;
2. 若不满,则将值保存至rear+1的位置 , 若front =0, rear =3,这是位置3为空,但是判断的3+1 =4,则rear=(rear+1)%4 =0,则rear = front,显示队列已满,所以不能再插入,而其实还有一个空位。
Status EnAQueue(AQueue *Q, void *data) //入循环队列
{
fflush(stdin);
if((Q->rear+1) % MAXQUEUE == Q->front)
{
printf("队列已经满了!\n");
return FLASE;
}
void *addTarget = (Q->data) + (Q->rear)%MAXQUEUE * (Q->data_size);
memcpy(addTarget,data,Q->data_size);
++(Q->rear);
++(Q->len);
printf("(数字也是字符的一种)插入成功!\n");
return TRUE;
}
出队
判断队列是否为空,若为空,则出队失败,否则只需将首节点移向下一个位置。
Status DeAQueue(AQueue *Q) //出循环队列
{
if(Q->front == Q->rear)
{
printf("队列为空!\n");
return FLASE;
}
else
{
Q->front = (Q->front + 1) % MAXQUEUE;
printf("队列头元素出队列成功!\n");
return TRUE;
}
}
清空队列
使用一个临时指针首先指向头节点,然后遍历整个队列,一边遍历一边free掉节点即可,就像清空链表地操作一样。
void ClearQueue(PQueue queue) {
PNODE P = queue->Front->Next; // 临时指针
PNODE Q = NULL; // 临时指针
queue->Rear = queue->Front; // 使队尾指针指向头节点
queue->Front->Next = NULL;
// 从首节点开始清空
while (P != NULL) {
Q = P;
P = P->Next;
free(Q);
}
printf("清空队列成功...\n");