[数据结构与算法] 3.3 队列

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 3.3 队列 -> 正文阅读

[数据结构与算法]3.3 队列

3.3 队列

3.3.1 队列的基本概念

队列(Queue)：队列是只允许在一端进行插入，在另一端进行删除的线性表，简称队
操作特性：FIFO
队头(Front)：允许删除的一端
队尾(Rear)：允许插入的一端
入队：向队列中插入元素
出队：从队列中删除元素
基本操作
- InitQueue(&Q)：初始化队列，构造一个空队列
- DestroyQueue(&Q)：销毁一个队列并释放队列所占用的存储空间
- EnQueue(&Q, x)：入队，若队列未满，则将x加入，使之成为新队尾
- DeQueue(&Q, &x)：出队，若队列非空，删除队头元素，并用x返回
- GetHead(Q, &x)：若队列非空，获取队头元素并用x返回

3.4 队列的顺序存储结构

3.4.1 队列的顺序存储

队列的顺序实现：分配一块连续的存储单元存放队列的元素，并附设两个指针：队头指针(front)指向队头元素，队尾指针(rear)指向队尾元素的下一个位置

队列的顺序存储类型描述

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;

初始状态/队空条件：Q.front == Q.rear == 0

void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;
}

入队操作：队不满时，先送值到队尾元素，队尾指针+1

bool EnQueue(SqQueue &Q, ElemType x){
	// 这种判断是错误的
	if(Q.rear==MaxSize) return false;

	Q.data[Q.rear]=x;
	Q.rear++;
	return true;
}

出队操作：队非空时，取出队头元素，队头指针+1

bool DeQueue(SqQueue &Q, ElemType &x){
	// 这种判断是错误的
	if(Q.rear==Q.front) return false;

	x=Q.data[Q.front];
	Q.front++;
	return true;
}

假溢出：如下图所示，由于进行多次出队操作会导致Q.front不断+1，因此Q.front会不断向Q.rear靠近，然后Q.front前面的元素并没有被真正删除，实际上仍然占用着队列空间而却没有被使用，因此Q.front==Q.rear不能作为队满的判断条件

在这里插入图片描述

循环队列：为了避免队列出现假溢出的情况，把顺序队列臆造为一个环状的空间，即把顺序队列元素的表从逻辑上视为一个环，称为循环队列
- 实现原理：利用取余运算，在队首/尾指针到达MaxSize-1位置后，再前进一个位置就自动到0
- 队首指针进1：Q.front=(Q.front+1)%MaxSize
- 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
- 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
循环队列判满\空条件
- 牺牲一个单元来区分对空和队满：队头指针为队尾指针的下一位置则为队满
  - 队满：Q.front==(Q.rear+1)%MaxSize
  - 队空：Q.front==Q.rear
- 增加表示队列长度的数据成员：
  - 队满：Q.size==MaxSize
  - 对空：Q.size==0
- 队列中增加tag数据成员
  - 最近一次执行删除操作，则tag=0：若因删除导致Q.front==Q.rear，则队空
  - 最近一次执行插入操作，则tag=1：若因插入导致Q.front==Q.rear，则队满

3.4.2 循环队列的基本操作

初始化

void InitQueue(SqQueue &Q){
	Q.rear=Q.front=0;
}

判队满

bool isFull(SqQueue Q){
	// 牺牲法
	if(Q.front==(Q.rear+1)%MaxSize)  return true;
	else return false;

	// 设Q.size
	if(Q.size==MaxSize) return true;
	else return false;

	// 设Q.tag
	if(Q.front==Q.rear && tag==1) return true;
	else return false; 
}

判队空

bool isEmpty(SqQueue Q){
	if(Q.front==Q.rear) return true;
	else return false;
}

入队

bool EnQueue(SqQueue &Q, ElemType e){
	if(!isFull(Q)) return false;

	Q.data[Q.rear]=e
	Q.rear=(Q.rear+1)%MaxSize;
	return true;
}

出队

bool DeQueue(SqQueue &Q, ElemType &e){
	if(!isEmpty(Q)) return false;

	e=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;

	return true;
}

3.5 队列的链式存储结构

3.5.1 队列的链式存储

链队列：队列的链式表示，它实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点
适用：数据元素变动大，数据元素不确定

队列的链式存储类型描述

// 结点
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;

// 链式队列
typedef struct{
	LinkNode *front, *rear;
}LinkQueue;

初始化

// 带头结点
void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next=NULL;
}

// 不带头结点
void InitQueue(LinkQueue &Q){
	Q.front=NULL;
	Q.rear=NULL;
}

3.5.3 链式队列的基本操作

入队

// 带头结点
void EnQueue(LinkQueue &Q, ElemType x){
	LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=x;
	s->next=NULL;
	Q.rear->next=s
	Q.rear=s;
}

// 不带头结点
void EnQueue(LinkQueue &Q, ElemType x){
	LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=x;
	s->next=NULL;
	if(Q.front==NULL){
		Q.front=s;
		Q.rear=s;
	}
	else{
		Q.rear->next=s;
		Q.rear=s;
	}
}

出队

// 带头结点
void DeQueue(LinkQueue &Q, ELemType &x){
	if(Q.front->next==NULL) return false;

	LinkNode *p=Q.front->next;
	x=p->data;
	Q.front->next=p->next;
	if(Q.rear==p){
		Q.rear=Q.front;
	}
	free(p);
}

// 不带头结点
void DeQueue(LinkQueue &Q, ELemType &x){
	if(Q.front==NULL) return false;
	LinkNode *p=Q.front;
	x=p->data;
	Q.front=p->next;
	if(Q.rear==p){
		Q.rear=NULL;
		Q.front=NULL;
	}
	free(p);
}