本次笔记内容:
2.3.1 队列及顺序存储实现
2.3.2 队列的链式存储实现
文章目录
什么是队列队列的顺序存储实现循环队列队列的链式存储实现什么是队列
队列(Queue):具有一定操作约束的线性表。
插入和删除操作:只能在一段插入,而在另一端删除。
数据插入:入队列(AddQ)
数据删除:出队列(DeleteQ)
先来先服务,先进先出:FIFO
队列的顺序存储实现
队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
#define MaxSize <储存数据元素的最大个数>struct QNode{ElementType Data[MaxSize];int rear;int front;};typedef struct QNode *Queue;
循环队列
无法区分队列状态的根本原因在于,front和rear的距离只有n种,而实际情况有n+1种。
解决方案:
使用额外标记:Size或者tag域;仅使用n-1个数组空间
使用第二种方案,实现队列。
(1)入队列
void AddQ(Queue PtrQ, ElementType item){if ((PtrQ->rear + 1) % MaxSize == PtrQ->front){printf("队列满");return;}PtrQ->rear = (PtrQ->rear + 1) % MaxSize;PtrQ->Data[PtrQ->rear] = item;}
(2)出队列
ElementType DeleteQ(Queue PtrQ){if (PtrQ->front == PtrQ->rear){printf("队列空");return ERROR;}else{PtrQ->front = (PtrQ->front + 1) % MaxSize;return PtrQ->Data[PtrQ->front];}}
队列的链式存储实现
列表设计时,应注意不能将front设置在-1位置(因为没有)。
struct Node{ElementType Data;struct Node *Next;};struct QNode{/*链队列结构*/struct Node *rear; /*指向队尾结点*/struct Node *front; /*指向队头结点*/};typedef struct QNode *Queue;Queue PtrQ;
出队操作
ElementType DeleteQ(Queue PtrQ){struct Node *FrontCell;ElementType FrontElem;if (PtrQ->front == NULL){printf("队列空");return ERROR;}FrontCell = PtrQ->front;if (PtrQ->front == PtrQ->rear) /*若队列只有一个元素*/PtrQ->front = PtrQ->rear = NULL; /*删除后队列置为空*/elsePtrQ->front = PtrQ->front->Next;FrontElem = FrontCell->Data;free(FrontCell); /*释放被删除结点空间*/return FrontElem;}