双端队列

71 阅读 0 评论 47 点赞

我是靠谱客的博主温暖外套，最近开发中收集的这篇文章主要介绍双端队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

rear++: 出队， front++

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

双端队列 (可以理解为中间站了一个人，push和pop就在他左边进行，而inject和eject在他右边进行)
注意：双端队列使用了循环队列。判断满不满的条件是多开一个空间，即判断rear与front的关系。
我们rear指针指向元素的下一个空位置，front指向元素

push 将元素插入表头 front- -
pop 删除头部元素 front++
inject 将元素插入到表尾 rear++
eject 删除尾部元素 rear- -
初始化时，rear=front=0;
有- - 操作，可能会出现负值，所以需要+size在取余的操作

#include<stdio.h>
#include<stdlib.h>
typedef struct QNode{
	int *Data;
	int Front,Rear;
	int MaxSize;// 队列最大容量
}QNode,*Deque;
Deque CreateDeque( int MaxSize )
{   /* 注意：为区分空队列和满队列，需要多开辟一个空间 */
    Deque D = (Deque)malloc(sizeof(struct QNode));
    MaxSize++;
    D->Data = (int *)malloc(MaxSize * sizeof(int));
    D->Front = D->Rear = 0;
    D->MaxSize = MaxSize;
    return D;
}
bool Push( int X, Deque D )
{
	if((D->Rear+1)%D->MaxSize==D->Front) return false;//空间满了，我们有一个空间不用
	D->Front--;//push就是往左边插入，所以- -
	D->Front=(D->Front+D->MaxSize)%D->MaxSize;//- -之后万一出界呢？所以要取余
	D->Data[D->Front]=X;//解决了出界问题后，我们就可以把这个元素放到这里了
	return true; 
} 
int Pop( Deque D )
{
	if(D->Front==D->Rear) return 0;//队列空 
	int x=D->Data[D->Front];//pop是删除头部元素，即front所在位置的元素
	++D->Front;//删除了，就要+ +
	D->Front=D->Front%D->MaxSize;//防止他出界
	return x;
}
bool Inject( int X, Deque D )//插入结点 
{
	if((D->Rear+1)%D->MaxSize==D->Front) return false;//空间满
	D->Data[D->Rear]=X;//rear是尾部元素下一个空间，所以把新元素放到这里就行
	D->Rear++;//rear还要指向尾部的下一个空间
	D->Rear=D->Rear%D->MaxSize; //防止他出界
	return true;
}
int Eject( Deque D )//删除节点 并返回 
{
	if(D->Front==D->Rear) return 0;//队列空 
	D->Rear--;//eject是删除尾部元素，由于rear是尾部元素下一个空间，所以- -
	D->Rear=(D->Rear+D->MaxSize)%D->MaxSize;//防止出界
	int x=D->Data[D->Rear];//返回尾部元素，此时rear指向，我们可以认为是空位置
	return x;
}
bool  IsEmpty(Deque D)
{
	if(D->Front==D->Rear)
	return true;
	return false;
}
bool IsFull(Deque D)
{
	if(D->Front+D->Rear==D->MaxSize-1)
	return true;
	return false;
}
//void show(Deque D)
//{
//	int i;
//	for(i=(D->Front+1)%D->MaxSize;i<=D->Rear;i++)
//	printf("%d ",D->Data[i]);
//	
//}
int main(){
	int x,n;
	QNode Q,*D;
	 
	scanf("%d",&n);
	D=CreateDeque(n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x);
		Push(x,D);
	}
	int y=Pop(D);
	printf("%dn",y);
	printf("插入元素：");
	scanf("%d",&x);
	Inject(x,D);
//	printf("显示队列元素n");
//	show(&Q);
	printf("删除队尾元素n");
	Eject(D);
	while(!IsEmpty(D))
	{
		y=Pop(D);
		printf("%d ",y);
	}
//	printf("显示队列元素：n");
//	show(D);
	return 0;
}