双向队列（deque)

故名思意，就是不论从那边看都是一个队列。(我觉得像是两个栈，栈底拼在一起)，两端都能进行插入和删除。
双向队列也是基于线性表的，因此数组和链表都可以实现它，在此我就仅用链表实现一下。

typedef int ELemType; //用int来模拟数据项类型

typedef struct Node//数据节点
{
	ELemType data;
	struct Node* pre;
	struct Node* next;
}*DuList;

typedef struct
{
	int size;
	DuList front;
	DuList back;
}Deque;

大小

int Size_Deque(Deque* D)
{
	assert(D != NULL);
	return D->size;
}

初始化

bool Init_Deque(Deque* D)
{
	assert(D != NULL);
	D->size = 0;
	D->front = NULL;
	D->back = NULL;
	return true;
}

清空

bool Clear_Deque(Deque* D)
{
	assert(D != NULL);
	while (!IsEmpty_Deque(D))
	{
		Pop_Front_Deque(D);
	}
	return true;
}

判空

bool  IsEmpty_Deque(Deque* D)
{
	assert(D != NULL);
	return D->size == 0;
}

尾出

bool Pop_Back_Deque(Deque* D)
{
	assert(D != NULL);
	if (IsEmpty_Deque(D))
	{

	}
	else if (Size_Deque(D) == 1)
	{
		D->size = 0;
		free(D->front);
		D->back = NULL;
		D->front = NULL;
	}
	else
	{
		D->size = D->size - 1;
		DuList p = D->back->pre;
		free(D->back);
		D->back = p;
	}
	return true;
}

头出

bool Pop_Front_Deque(Deque* D)
{
	assert(D != NULL);
	if (IsEmpty_Deque(D))
	{

	}
	else if (Size_Deque(D) == 1)
	{
		D->size = 0;
		free(D->front);
		D->back = NULL;
		D->front = NULL;
	}
	else
	{
		D->size = D->size - 1;
		DuList p = D->front->next;
		free(D->front);
		D->front = p;
	}
	return true;
}

尾入

bool Push_Back_Deque(Deque* D, ELemType e)
{
	assert(D != NULL);
	DuList p = (DuList)malloc(sizeof(Node));
	if (p == NULL)
	{
		return false;
	}
	else if (D->size == 0)
	{
		p->data = e;
		p->next = NULL;
		p->pre = NULL;
		D->size = 1;
		D->back = p;
		D->front = p;
		return true;
	}
	else
	{
		p->data = e;
		p->next = NULL;
		p->pre = D->back;
		D->back->next = p;
		D->back = p;
		D->size += 1;
		return true;
	}
}

头入

bool Push_Front_Deque(Deque* D, ELemType e)
{
	assert(D != NULL);
	DuList p = (DuList)malloc(sizeof(Node));
	if (p == NULL)
	{
		return false;
	}
	else if (D->size == 0)
	{
		p->data = e;
		p->next = NULL;
		p->pre = NULL;
		D->size = 1;
		D->back = p;
		D->front = p;
		return true;
	}
	else
	{
		p->data = e;
		p->pre = NULL;
		p->next = D->front;
		D->front->pre = p;
		D->front = p;
		D->size += 1;
		return true;
	}
}

获取头

ELemType Front_Deque(Deque* D)
{
	assert(D != NULL);
	if (IsEmpty_Deque(D))
	{
		printf("Deque is Empty\n");
		return -1;
	}
	else
	{
		return D->front->data;
	}
}

获取尾

ELemType Back_Deque(Deque* D)
{
	assert(D != NULL);
	if (IsEmpty_Deque(D))
	{
		printf("Deque is Empty\n");
		return -1;
	}
	else
	{
		return D->back->data;
	}
}