【数据结构】队列-顺序队列、循环队列、链队、双端队列

Myth丶恋晨 2021-11-22 10:26 467阅读 0赞

### 定义 ###

队列是只允许**在一端进行插入**，而**在另一端进行删除**的线性表。  
**队头（Front）**：允许删除的一端，又称为队首。  
**队尾（Rear）**： 允许插入的一端。

先进入队列的元素必然先离开队列，即先进先出（First In First Out）简称FIFO。

\*\*对比：\*\*栈中元素后进去的必然先出来，即后进先出LIFO（Last In First Out）。

### 顺序队列 ###

用数组来实现队列，可以将队首放在数组下标为0的位置。

> 不要求从数组首位开始存储队列。也就是说队首不一定要在数组下标为0的位置。那如何表示队首呢？

#define MaxSize 50 //定义队列中元素的最大个数
    typedef struct{
    ElemType data[MaxSize]; //存放队列元素yichu
    int front，rear; //队头指针和队尾指针
    } SqQueue;

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，井附设两个指针 front和 rear 分别指示队头元素和队尾元素的位置。设队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。

初始状态（队空条件）： Q.front==Q.rear=0 。  
进队操作：队不满时，先送值到队尾元素 ， 再将队尾指针加1  
出队操作：队不空时，先取队头元素值，再将队头指针加1

当rear到达数组末端，会出现“假溢出”

### 循环队列 ###

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环 ，称为循环队列 。当队首指针 Q.front=MaxSize-1 后，再前进一个位置就自动到 0，这可以利用除法取余运算（%）来实现 。  
初始时： Q.front=Q.rear=O  
队首指针进 1: Q.front=(Q.front+1)%MaxSize  
队尾指针进 1: Q.rear=(Q.rear+l)%MaxSize  
队列长度：（Q.rear+MaxSize-Q.front)%MaxSize

> 那么，循环队列队全和队满的判断条件是什么呢？ 显然，队空的条件是 Q.front=Q.rear。如果入队元素的速度快于出队元素的速度 ， 队尾指针很快就赶上了队首指针，如图d1 所示，此时可以看出队满时也有 Q.front=Q.rear。 为了区分队空还是队满的情况， 下面给出常用的一种处理方式：

牺牲一个单元来区分队空和队满， 入队时少用 一个队列单元，这是一种较为普遍的做法 ，约定以 “队头指针在队尾指针的下一位置作为队满的标志”，如图（d2）所示：  
队满条件为：(Q.rear+1)%MaxSize == Q.front  
队空条件仍为： Q.front ==Q.rear  
队列中元素的个数：（Q .rear-Q.front+MaxSize)% MaxSize  
![循环队列出入队示意图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

### 循环队列的操作 ###

#### 1.初始化 ####

void InitQueue(&Q){
    	Q.rear=Q.front=0;	//初始化队首、队尾指针
    }

#### 2.判队空 ####

bool isEmpty(Q){
    	if(Q.rear==Q.front)		//队空条件
    		return true;
    	else
    		return false;
    }

#### 3.入队 ####

bool EnQueue(SqQueue &Q,ElemType x) {
    	if ((Q.rear+1)%MaxSize==Q.front) 	//队满
    		return false; 
    	Q.data[Q.rear]=x;
    	Q.rear=(Q.rear+1)%MaxSize;
    	return true;						//队尾指针加 1 取模
    }

#### 4.出队 ####

bool DeQueue(SqQueue &Q,ElemType &x) {
    	if(Q.rear==Q.front) 				//队空，报错
    		return false;
    	x=Q.data[Q.front];
    	Q.front=(Q.front+1)%MaxSize;		//队头指针加 1 取模
    	return true;
    }

### 链式队列 ###

队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素。  
为了方便操作，我们分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点。

typedef struct{ 				//链式队列结点
    	ElemType data;
    	struct LinkNode *next;
    }LinkNode;
    
    typedef struct{ 				//链式队列
    	LinkNode *front,*rear;  	//队头和队尾指针
    }LinkQueue;

### 链式队列的操作 ###

#### 1.入队 ####

我们知道队列只能从队尾插入元素，队头删除元素。于是入队就是在队尾指针进行插入结点操作。链队的插入操作和单链表的插入操作是一致的。  
![在这里插入图片描述][20190724220207141.png]

void EnQueue(LinkQueue &Q，ElemType x){
    	s=(LinkNode *)malloc(sizeof(LinkNode));
    	s->data=x;
    	s->next=NULL;
    	Q.rear->next=s;
    	Q.rear=s;
    }

#### 2.出队 ####

出队就是头结点的后继结点出队，然后将头结点的后继改为它后面的结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

bool DeQueue(LinkQueue &Q,ElemType &x){
    	if(Q.front==Q.rear) 
    		return false;     //空队
    	p=Q.front->next;
    	x=p->data;
    	Q.front->next=p->next;
    	if(Q.rear==p) 
    		Q.rear=Q.front;   //若原队列中只有一个结点，删除后变空
    	free(p);
    	return true;
    }

### 双端队列 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]

#### 参考资料 ####

王道数据结构

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211122/92fcefc27bd44766bcb3a5e49eadec45.png
[20190724220207141.png]: /images/20211122/eb39d13dff964b03ba1a6b1b22972699.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211122/3aa9aa466056457092d463b7a316f051.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: /images/20211122/0492b05516ce4862beae9f1e7383d14c.png