队列

1. 梗概

1. 一端进
   1. 进的那端叫队尾
2. 另一端出
   1. 队头

2. 结构梗概

0.1. 循环队列

2.1.1.1. 有两个指针

1. rear指针
   1. 指向队尾
2. front指针
   1. 指向队头

2.1.1.2. 循环利用空间的设计:

rear指针和front指针在队列中循环移动: 以rear为例, front同理:

1. 当rear到达最顶端时, rear重新指向底端
   1. 即以MAXSIZE作为一个周期
      1. 周期，自然就想到取余运算符mod
         1. 即rear和front增加时用以下语句 指针=(指针+1)%MAXSIZE

2.1.1.3. 2. 循环队列中区分满与空

有两种方法:

2.1.1.3.1. 损失一个元素空间来区分两种情况(推荐)

2.1.1.3.1.1. 梗概:

1. front屁股后面的空间不能存储
2. 当rear追到front屁股后的空间时, 就停止
3. 此时满的条件为 (real+1) mod MAXSIZE == front
   1. 而空的条件依然是rear==front

2.1.1.3.1.2. 缺点:

4. 损失一个空间

2.1.1.3.2. 增设一个标志量, 区别空和满

0.2. 链队列(常用⭐)

大体采用链表结构(类似线性链表), 并对链表进行再一层包装作为队列

2.1.2.1. 结构:

1. 采用带头结点的链表结构
2. 有头指针front、尾指针rear
   1. front指向头结点, 头结点的下一个结点为队头
      1. 保持静止
   2. rear始终指向最后一个节点, 表示队尾
      1. 入队后rear要更改指向
3. rear和front都指向头结点表示空队列

3. 操作梗概:

1. 插入数据
   1. 插入到rear指的位置
   2. rear+1
2. 删除数据
   1. 删除front指的位置
   2. front+1
3. 判断是否为空
4. 判定是否为满

4. 在c语言中的实现：

1. 有两种实现方式

1. 循环(顺序)队列
2. 链队列(常用)

2. 链队列的实现:

2.1. 链队列定义:

typedef struct Node{//通用链表结构
	QueueElementType data;
	struct Node *next;
}LinkQueueNode;
typedef struct{
	LinkQueueNode *front;//利用节点的指针域
	LinkQueueNode *rear;
}LinkQueue;//封装链表为链队列，只留下队列的两个接口

2.2. 初始化链队列:

int InitQueue(LinkQueue *Q){
	Q->front=(LinkQueueNode*)calloc(1,sizeof(LinkQueueNode));//创建头结点
	if(Q->front!=NULL){//空间请求成功
		Q->rear=Q->front;//置空链队列
		Q->front->next=NULL;//置空链表
		return 1;
	}
	return 0;
}

2.3. 链队列入队:

int EnterQueue(LinkQueue *Q, QueueElementType x){
	LinkQueueNode * NewNode;
    /*申请空间*/
	NewNode = (LinkQueueNode *)calloc(1,sizeof(LinkQueueNode));
	if(NewNode!=NULL){//判断申请结果
		NewNode->data=x;
		NewNode->next=NULL;//作为最后一个节点
		Q->rear->next=NewNode;//接到队尾后
		Q->rear=NewNode;//队尾指针重新指向最后的节点
		return 1;
	}
	return 0;
}

2.4. 链队列出队:

 int DeleteQueue(LinkQueue *Q, QueueElementType *x){
    LinkQueueNode *p;
    if(Q->front==Q->rear)//判断为空
 	   return 0;
    p=Q->front->next;//指代队头元素,方便操作
    Q->front->next=p->next;//头结点跳过队头, 连上队头的后继
    if(Q->rear==p)//若队中只有一个元素p,需手动置空链队列
 	   Q->rear=Q->front;
    *x=p->data;
    free(p);
    retrun 1;
 }

3. 循环队列的实现:

3.1. 类型定义:

typedef int QueueElementType;
#define SeqQueue_MAXSIZE 64
typedef struct{
	QueueElementType element[SeqQueue_MAXSIZE];
	int front; //队头指针
	int rear; //队尾指针
}SeqQueue;

3.2. 判空:

int SeqQueue_IsEmpty(SeqQueue *Q){
//空为1,否则为0
	if(Q->front=Q->rear)return 1;
	return 0;
}

3.3. 初始化操作:

void InitQueue(SeqQueue *Q){
	Q->front=Q->rear=0; //初始化为一个空的循环队列
}

3.4. 入队操作:

int EnterQueue(SeqQueue *Q,QueueElementType x){
	if ((Q->rear+1)%SeqQueue_MAXSIZE==Q->front) //判断尾指针在循环队列中相差一个，为满
		return 0;
	Q->element[Q->rear]=x; //队尾插入
	Q->rear=(Q->rear+1)%SeqQueue_MAXSIZE; //周期性累加
	return 1;		
}

3.5. 出队操作:

int DeleteQueue(SeqQueue *Q, QueueElementType *x){
	if (Q->front==Q->rear) //判断队列为空
		return 0;
	*x=Q->element[Q->front]; //用传入的地址存储出队的元素
	Q->front=(Q->rear+1)%SeqQueue_MAXSIZE; //循环累加
	return 1;
}

5. 在typescript(ts)中的实现:

js JavaScript

1. 梗概:

用数组作为队列, 数组对象具有push()和shift()方法

2. [use::push()]

3. [use::shift()]:

4. 读取队头:

数组[0]

5. 读取队尾:

数组[数组.length-1]