一、什么是队列
队列(Queue)是具有一定约束的线性表,它只能在 一端插入(入队,AddQ)而在 另一端删除(出队,DeleteQ)。它具有 先进先出(FIFO)的特性。
队列的抽象类型描述:
- 类型名称:队列(Quene)
- 数据对象集:一个有 0 个或多个元素的有穷线性表
- 操作集:长度为 MaxSize 的队列 Q ∈ Quene,队列元素 item ∈ ElementType
Queue CreateQuene(int MaxSzie); // 生成长度为MaxSize的空队列
int IsFullQ(Queue Q,int MaxSize); // 判断队列Q是否已满
void AddQ(Queue Q,ElementType item); // 将数据元素item插入队列Q中
int IsEmptyQ(Quenu Q); // 判断队列Q是否为空
ElementType DeleteQ(Queue Q); // 将队头数据元素从队列中删除并返回
二、队列的顺序存储实现
队列的顺序存储结构通用由一个一维数组和一个记录 队列头元素位置 的变量 front 以及一个记录 队列尾元素位置 的变量 rear 组成。
#define MaxSize // 存储数据元素的最大个数
struct QNode
{
ElementType Data[MaxSize];
int rear;
int front;
};
typedef struct QNode *Queue;
【1】、入队(AddQ)
void AddQ(Queue PtrQ,ElementType item)
{
if((PtrQ->rear+1) % MaxSize == PtrQ->front)
{
printf("队列已满\n");
return;
}
PtrQ->rear = (PtrQ->rear + 1) % MaxSize;
PtrQ->Data[PtrQ->rear] = item;
}
循环队列当存储空间全部使用时,read 等于 front,此时无法表示循环队列是空的还是满的,此时解决方法有两种:第一种是 使用额外的标记:Size 或者 tag域,Size 用来记录当前循环队列中元素的个数。第二种方式是 仅使用 n-1 个数组空间;
【2】、出队(DeleteQ)
ElementType DeleteQ(Queue PtrQ)
{
if(PtrQ->front == PtrQ->rear)
{
printf("队列空\n");
return ERROR;
}
else
{
PtrQ->front = (PtrQ->font + 1) % MaxSize;
return PtrQ->Data[PtrQ->front];
}
}
三、队列的链式存储实现
队列的链式存储结构可以用一个单链表实现。插入(入栈,AddQ)和 删除(出栈,DeleteQ)操作分别在链表的两头进行。队列头指针 front 指向 链表头,队列尾指针 rear 指向 链表尾。
typedef struct QNode *Queue;
struct Node
{
ElementType Data;
struct Node *Next;
};
struct QNode // 链队列结构
{
struct Node *rear; // 指向队尾结点
struct Node *front; // 指向队头结点
};
Queue PtrQ;
【1】、入队(AddQ)
不带头节点的链式队列入队操作:
void AddQ(Queue PtrQ,ElementType item)
{
struct Node *temCell;
temCell = (struct Node *)malloc(sizeof(struct Node));
temCell->Data = item;
tempCell->Next = NULL;
if(PtrQ->font == NULL) // 如果是第一个结点
{
PtrQ->rear = PtrQ->front = temCell; // 队列的头指针和尾指针都指向第一个结点
}
else
{
PtrQ->rear->Next = temCell; // 之前的链表的尾结点连接新结点,形成链
PtrQ->rear = temCell; // 队列的尾结点指向新结点
}
}
【2】、出队(DeleteQ)
不带头节点的链式队列出队操作:
ElementType DeleteQ(Queue PtrQ)
{
struct Node *FrontCell;
ElementType FrontElem;
if(PtrQ->front == NULL)
{
printf("队列已空\n");
return ERROR;
}
FrontCell = PtrQ->front;
if(PtrQ->front = PtrQ->rear) // 若队列只有一个元素
{
PtrQ->front = PtrQ->rear = NULL; // 删除后队列置为空
}
else
{
PtrQ->front = PtrQ->front->Next; // 队列头指针指向第二个元素
}
FrontElem = FrontCell->Data; // 获取原队列头指针指向的元素
free(FrontCell); // 释放被删除的结点空间
return FrontElem;
}
标签:struct,05,队列,PtrQ,Queue,front,rear
From: https://www.cnblogs.com/kurome/p/17248340.html