数据结构与算法（八）——双端队列

目录

一、前情提要

         二、双端队列介绍

（一）双端队列的顺序存储

（二）双端队列的链式存储

三、代码实现

（一）双端队列的顺序存储

（二）双端队列的链式存储

一、前情提要

         上篇文章讲了队列的两种形式，一种是队列的顺序结构，称作循环队列。另一种时队列的链式结构，称作链队列。这两种形式都遵循着一个原则，先进先出的原则，从队尾入队，队头出队。但是还存在一种数据结构“双端队列”，它包含了栈和队列的所有特性。本篇文章将会给出所有操作的代码，并标注详细注释。

二、双端队列介绍

          双端队列（Double-ended Queue，简称Deque）是一种具有队列和栈特性的数据结构，可以在队列的两端进行插入和删除操作。双端队列允许从前端和后端同时进行插入和删除操作，因此可以称为“两端都可以进出的队列”。

           双端队列有以下几个特点：

           1、可以在队列的头部和尾部进行插入和删除的操作。

           2、元素的插入和删除操作可以分别称作入队和出队操作。

           3、可以进行先进先出（FIFO）和先进后出（LIFO）两种操作方式。

           4、可以实现栈和队列以及其他需要在两端进行插入和删除操作的场景。

           双端队列如图示：

（一）双端队列的顺序存储

      

//假设数组为a[N]
//头尾指针都指向下标为0处
 
//左插入值为k1
//在下标为0处
  a[l]=k1;
  l--;
 
//当右插入值为k2
  r++;
  a[r]=k2;

//假设数组为a[N]
//先开始头尾指针指向数组下标为0处
 
 
//左插入值为k1
//在下标为0处
  l--;
  a[l]=k1;
 
//右插入值为k2
  a[r]=k2;
  r++;

     双端队列的链式存储可以理解为，是基于不带头结点的双向链表。

     此时我们会设置一个mid结点，头尾指针都会指向这个结点。

     那么还会有个问题值得思考。这个mid结点到底存不存数据呢？

     可能有人说存不存无所谓。我们先画个图，模拟一个场景。

    咱假设mid结点不存数据，此时从左边入队了两个元素，右边入队了两个元素。

    重点来了！如果此时我们要从左边出队三个元素，那该咋办呢？

    很明显我们要跳过mid结点去删除数据为3的结点，这样的话我们就得写个if语句特判一下。麻不麻烦暂且不说，很容易忽略掉。

     所以我们在mid结点处，要存入数据。跟上面的顺序存储一样，可以先开始存从左边入队的元素，也可以先开始存从右边入队的元素。在这里写代码统一规定，储存右边入队的元素。、

      因为是双向链表，所以入队的时候就是个简单的尾插代码，之前也有写过。

三、代码实现

       因为很多操作之前都写过了，所以注释就不再重复了，如果看不懂的就回去看对应双向链表的知识。

（一）双端队列的顺序存储

#include <stdio.h>
#include <stdlib.h>
 
#define QSize 10
 
int* Queue;
int Left,Right;
int MaxSize;
int Size;
 
void InitQueue()
{
	Queue=(int*)malloc(QSize*sizeof(int));
	MaxSize= QSize;
	Size=0;
	Left=Right=0;
}
 
void Left_Insert(int Date)
{
	if(Size==MaxSize)
	{
		printf("空间已满");
		return;
	}
	else
	{
		Left=(Left-1+QSize)%QSize;//如果看不懂，去看循环队列那篇 
		Queue[Left]=Date;
		Size++;
	}
}
 
void Right_Insert(int Date)
{
	if(Size==MaxSize)
	{
		printf("空间已满");
		return;
	}
	else
	{
		Queue[Right]=Date;
		Right=(Right+1)%QSize;
		Size++; 
	}
}
 
void Left_Remove()
{
	if(Size==0)
	{
		printf("队列为空");
		return;
	}
	else
	{
		Left=(Left+1)%QSize;
		Size--;
	} 
}
 
void Right_Remove()
{
	if(Size==0)
	{
		printf("队列为空");
		return;
	}
	else
	{
		Right=(Right-1+QSize)%QSize;
		Size--;
	}
}
 
void Show()
{
	if(Size==0) printf("队列为空");
	else 
	{
		int flag=Left;
		while(flag!=Right)
		{
			printf("%d ",Queue[flag]);
			flag=(flag+1)%QSize;
		} 
		printf("\n");
	}
}
int main()
{
	InitQueue();
	Left_Insert(1);
	Left_Insert(2);
	Left_Insert(3);
	Left_Insert(4);
	Right_Insert(5);
	Right_Insert(6);
	
	Show();
	
	Left_Remove();
	Right_Remove();
	Show();
	
	return 0;
} 

（二）双端队列的链式存储

#include <stdio.h>
#include <stdlib.h>
 
#define MaxSize 10
 
typedef struct LinkQueue
{
	int Data;
	struct LinkQueue* Pre;
	struct LinkQueue* Next;
}Node;
 
Node* Right;//创建左右指针 
Node* Left;
 
void InitQueue()
{
	Right=Left=(Node*)malloc(sizeof(Node));
	Left->Next=Left->Pre=NULL;
}
 
void Left_Insert(int Data)
{
	Node* P=(Node*)malloc(sizeof(Node));
	if(P==NULL) 
	{
		printf("申请内存失败");
		return;
	}
	P->Data=Data;
	
	P->Pre=NULL;     //尾插 
	P->Next=Left;
	Left->Pre=P;
	Left=P;
}
 
void Right_Insert(int Data)
{
	Node* P=(Node*)malloc(sizeof(Node));
	if(P==NULL)
	{
		printf("申请内存失败");
		return;
	}
	Right->Data=Data;
	
	Right->Next=P;  //尾插 
	P->Pre=Right;
	P->Next=NULL;
	Right=P;
} 
 
void Left_Remove() 
{
	if(Left==NULL||Left==Right)
	{
		printf("队列为空");
		return;
	}
	Node* P=Left;
	Left=Left->Next;
	Left->Pre=NULL;
	free(P);
} 
 
void Right_Remove()
{
	//注意删的是right->pre ,right->pre才是真正的最后一个
    //实际操作时只需要把right删掉，即可 
	if(Left==NULL||Left==Right)
	{
		printf("队列为空");
		return;
	}
	Node* P=Right;
	Right=Right->Pre;
	Right->Next=NULL;
	free(P);
}
 
void Show()
{
	if(Left==NULL||Left==Right)
	{
		printf("此表为空");
		return;
	}
	
	for(Node* i=Left;i!=Right;i=i->Next)
	{
		printf("%d ",i->Data);
	}
	printf("\n");
}
int main()
{
	InitQueue();
	
	Left_Insert(1);
	Left_Insert(2);
	Left_Insert(3);
	Left_Insert(4);
	Left_Insert(5);
	Right_Insert(6);
	Right_Insert(7);
	
	Show();
	
	Left_Remove();
	Right_Remove();
	Show();
	
	return 0;
}