526互联

数据结构与算法----------3

发布时间 2023-12-08 20:04:35作者: lwj1239

队列

队列也是一种受限制的线性表，只能在一端进行插入，在另一端进行删除。

当然也有一种特殊的队列，名叫双端队列，也就是一段既可以插入也可以删除，在另一端也可以插入和删除。这就是双端队列。

队列的顺序实现(非环形数组)

代码实现

//队列的顺序实现(非环形数组)
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define ERROR -1

typedef int ELEMENT;

typedef struct queue {
	ELEMENT *data;//存放元素 
	int head;//[head, tail)
	int tail;
	int MaxSize;//记录队尾最多能到的位置因为不是环形数组 
}QNode, *Queue;

Queue CreateQueue(int n);//创建一个大小为n的队列 
bool isFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, ELEMENT item);//把元素item入队 
bool empty(Queue q);//判断队列是不是空 
ELEMENT deleteQ(Queue q);//出队 
ELEMENT head(Queue q);//取出队头的元素但不出队 
ELEMENT tail(Queue q);//取出队尾的元素 
int size(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列 

int main(int argc, char* argv[])
{
	Queue q = CreateQueue(5);
	
	addQ(q, 10);
	pr("size = %d\n", size(q));
	addQ(q, 7);
	pr("head = %d\n", head(q));
	pr("tail = %d\n", tail(q));
	deleteQ(q);
	pr("head = %d\n", head(q));
	pr("tail = %d\n", tail(q));
	
	FreeQueue(q);

	return 0;
}
Queue CreateQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小 
	
	return t;//返回队列 
}
bool empty(Queue q)
{
	return q -> head == q -> tail;//如果队头等于队尾，就为空，因为区间是[head, tail) 
}
bool isFull(Queue q)
{
	return q -> tail == q -> MaxSize;//如果队尾到了最大位置，那么不能入队了，就满了 
}
bool addQ(Queue q, ELEMENT item)
{
	if (isFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	
	return true;//能入队返回true 
}
ELEMENT deleteQ(Queue q)
{
	if (empty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head++];//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
ELEMENT head(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，但不出队 
}
ELEMENT tail(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> tail - 1];//队列不为空，返回队列尾的元素。因为是[head, tail)的区间，所以队尾元素在tail减一位置 
}
int size(Queue q)
{
	return q -> tail - q -> head;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

但这样空间利用率太差了，为了解决这个问题，我们采用环形数组，来解决这个问题。

队列的顺序实现(环形数组)

//队列的顺序实现(环形数组) 
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 2000001
#define ERROR -1 

typedef int ELEMENT;

typedef struct queue {
	ELEMENT *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

Queue CreateQueue(int n);//创建一个大小为n的队列 
bool isFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, ELEMENT item);//把元素item从队列尾部加入 
bool empty(Queue q);//判断队列是不是空 
ELEMENT deleteQ(Queue q);//把队列头的元素出队 
ELEMENT head(Queue q);//取出队头的元素但不出队 
ELEMENT tail(Queue q);//取出队尾的元素 
int size(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

int main(int argc, char* argv[])
{
	Queue q = CreateQueue(3);
	
	addQ(q, 10);
	addQ(q, 2);
	addQ(q, 1);
	
	pr("%d\n", deleteQ(q));//10
	pr("head = %d\ttail = %d\n", head(q), tail(q));
	addQ(q, 4);
	pr("head = %d\ttail = %d\n", head(q), tail(q));

	return 0;
}
Queue CreateQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool empty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, ELEMENT item)
{
	if (isFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
ELEMENT deleteQ(Queue q)
{
	if (empty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	ELEMENT ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
ELEMENT head(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
ELEMENT tail(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int size(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

这样虽然解决了空间效率低的问题，但还是存在着稀疏的问题，因为不知道用户会放几个数，而导致空间的浪费，为了解决这个问题我们需要用链式存储来解决。

队列的链式存储(链表)

//队列的的链式实现(链表) 
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 10
#define ERROR -1 

typedef int ELEMENT;

struct QNode{//元素的节点 
	ELEMENT data;
	struct QNode* next;
};

typedef struct QNode QNode;

typedef struct queue {//队列的结构 
	QNode* head;//指向链表头 
	QNode* tail;//指向链表尾 
	int size;//记录队列元素的个数 
}queue,*Queue;

Queue CreateQueue(void);//创建一个队列 
bool addQ(Queue q, ELEMENT item);//把元素item添加到队列 
bool empty(Queue q);//判断队列是不是空 
ELEMENT deleteQ(Queue q);//出队，把队列头从队列中删除 
int size(Queue q);//返回队列元素的个数 
ELEMENT head(Queue q);//返回队列头的元素，但不出队 
ELEMENT tail(Queue q);//返回队列尾的元素，但不出队 
void FreeQueue(Queue q);//释放队列空间 

int main(int argc, char* argv[])
{
	Queue q = CreateQueue();
	
	addQ(q, 1);
	pr("head = %d\ttail = %d\n", head(q), tail(q));
	pr("size = %d\n", size(q));
	deleteQ(q);
	pr("size = %d\n", size(q));
	addQ(q, 4);
	
	pr("head = %d\ttail = %d\n", head(q), tail(q));
	pr("size = %d\n", size(q));
	
	FreeQueue(q);
	
	return 0;
}
Queue CreateQueue(void)
{
	Queue q = (Queue)malloc(sizeof(queue));//开辟一个队列 
	
	q -> head = NULL;//初始化为空 
	q -> tail = NULL;//初始化为空 
	q -> size = 0;//初始化为0 
	
	return q;
}
bool addQ(Queue q, ELEMENT item)
{
	QNode* t = (QNode*)malloc(sizeof(QNode));//开辟一个元素节点 
	
	if (t == NULL) {//如果空间不够那么就不能入队 
		return false;
	}
	
	t -> data = item;//把元素放入节点 
	t -> next = NULL;//让这个节点的next指向空，不然链表就错了 
	
	if (empty(q)) {//如果队列为空 
		q -> head = t;//头指针指向这个元素 
		q -> tail = t;//尾指针也要指向这个元素，因为只有这一个元素 
	}
	else {
		q -> tail -> next = t; //队列不为空，就让尾指针指向新的节点 
		q -> tail = t;//更新队列尾 
	}
	
	q -> size++;//入队所以元素加一 
	
	return true;
}
bool empty(Queue q)
{
	return !q -> size;//元素个数是0，就是空队列，否者不是空队列 
}
ELEMENT deleteQ(Queue q)
{
	if (empty(q)) {//如果队列为空，没有元素自然也就不能出队，违法 
		return ERROR;
	}
	
	QNode* t = q -> head;//t指向队列头 
	if (q -> size == 1) {//如果只有一个元素 
		q -> tail = NULL;//让队列尾也指向空，因为只有一个元素，出队之后队列就没有元素了，所以要让尾指针也指向空 
	}
	ELEMENT ans = t -> data;//把要返回的元素给ans 
	
	q -> head = t -> next;//队列的头往后面走 
	
	free(t);//释放之前的队列头 
	
	q -> size--;//出队了所以元素减一 
	
	return ans;//返回之前队列头的元素 
}
int size(Queue q)
{
	return q -> size;//返回队列元素的个数 
}
ELEMENT head(Queue q)
{
	if (empty(q)) {//如果队列为空，违法 
		return ERROR;
	}
	
	return q -> head -> data;//有元素返回队列头的元素，但不出队 
}
ELEMENT tail(Queue q)
{
	if (empty(q)) {//如果队列为空，违法 
		return ERROR;
	}
	
	return q -> tail -> data;//有元素返回队列尾的元素，但不出队 
}
void FreeQueue(Queue q)
{
	if (empty(q)) {//如果队列已经没有元素了直接释放队列 
		free(q);
		return ;
	}
	
	QNode* t = NULL;//后指针 
	QNode* p = q -> head;//前指针指向队列头 
	
	while(p) {
		t = p;//指向p的节点 
		p = p -> next;//p去下一个节点 
		free(t);//释放t的节点，因为p已经去下一个节点了，所以不会使链表断 
	}
	
	free(q);//释放队列 
}

双端队列顺序实现(环形数组)

//双端队列顺序实现(数组) 
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 10
#define ERROR -1 

typedef int ELEMENT;

typedef struct queue {
	ELEMENT *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *deQue;

deQue CreateDeque(int n);//创建一个同时能容纳n个元素的双端队列 
bool isFull(deQue q);//判断双端队列满了没有 
bool empty(deQue q);//判断双端队列是不是空双端队列 
bool addHead(deQue q, ELEMENT item);//在双端队列的头添加元素 
bool addTail(deQue q, ELEMENT item);//在双端队列的尾添加元素 
ELEMENT deleteHead(deQue q);//删除双端队列头的元素 
ELEMENT deleteTail(deQue q);//删除双端队列尾的元素 
int size(deQue q);//返回双端队列元素的个数 
ELEMENT head(deQue q);//返回双端队列头的元素但不出队 
ELEMENT tail(deQue q);//返回双端队列尾的元素但不出队 
void FreeDeque(deQue q);//释放双端队列 

int main(int argc, char* argv[])
{
	deQue q = CreateDeque(3);
	
	addHead(q, 2);
	addTail(q, 4);
	addHead(q, 6);
	
	pr("Tail = %d\n", tail(q));
	pr("head = %d\n", head(q));
	
	return 0;
}
deQue CreateDeque(int n)
{
	deQue q = (deQue)malloc(sizeof(QNode));//创建一个双端队列 
	
	q -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//开辟一个大小为n的数组用来存放元素 
	q -> head = 0;//初始化队头为0 
	q -> tail = 0;//初始化队尾为0 
	q -> size = 0;//初始化双端队列元素个数为0 
	q -> MaxSize = n;//双端队列最多能存放的元素个数 
	
	return q;
}
bool isFull(deQue q)
{
	return q -> size == q -> MaxSize;//如果双端队列的元素个数等于最大能存放的元素个数，那么就满了 
}
bool empty(deQue q)
{
	return !q -> size;//如果双端队列中没有元素那么就是空双端队列 
}
bool addHead(deQue q, ELEMENT item)
{
	if (isFull(q)) {//如果双端队列满了，那么不能添加元素了，返回false 
		return false;
	}
	
	if (q -> head == 0) {//如果双端队列头在下标0位置 
		q -> data[q -> MaxSize - 1] = item;//把元素添加到数组的最后一个下标，因为0位置减一，是非法的下标，所以利用环形数组的思想让它在最后一个下标的位置 
		q -> head = q -> MaxSize - 1;//因为添加了一个新的元素在双端队列头，所以要更新双端队列头的位置 
		q -> size++;//添加了元素，所以双端队列的元素个数加一 
		return true;//成功添加返回true 
	}
	
	q -> data[--q -> head] = item;//如果双端队列头不是在下标0位置，那么直接在它的前一个位置添加元素就行了 
	q -> size++;//添加了元素，所以双端队列的元素个数加一
	
	return true;//成功添加返回true 
}
bool addTail(deQue q, ELEMENT item)
{
	if (isFull(q)) {//如果双端队列满了，就不能添加元素，返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//注意双端队列的区间定义是[head, tail)，所以是在双端队列尾添加元素，然后双端队列尾去后一个位置 
	q -> tail %= q -> MaxSize;//利用环形数组的思想，用模运算实现一个环 
	q -> size++;//添加了元素，所以双端队列的元素个数加一
	
	return true;
}
ELEMENT deleteHead(deQue q)
{
	if (empty(q)) {//如果双端队列为空，删除元素违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	ELEMENT ans = q -> data[q -> head++];//区间定义是[head, tail)，所以直接取出双端队列头位置的元素就行了，再让头位置去后一个位置 
	q -> head %= q -> MaxSize;//利用模运算实现环形数组 
	q -> size--;//元素出双端队列了，所以双端队列元素的个数减一 
	
	return ans;//返回之前双端队列的头元素 
}
ELEMENT deleteTail(deQue q)
{
	if (empty(q)) {//如果双端队列为空，删除元素违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	if (q -> tail == 0) {//如果双端队列尾在下标0位置，又因为是[head, tail)，所以双端队列尾元素实际上在下标MaxSize - 1位置，因为是环形数组 
		ELEMENT ans = q -> data[q -> MaxSize - 1];//把双端队列尾元素给ans 
		
		q -> size--;//双端队列尾出队了，所以元素个数减一 
		q -> tail = q -> MaxSize - 1;//更新双端队列尾的位置 
		
		return ans;
	}
	
	ELEMENT ans = q -> data[--q -> tail];//区间是[head, tail)，所以双端队列尾元素实际在tail的前一个位置，所以是--q -> tail 
	
	q -> size--;//双端队列尾元素出队，所以元素个数减一 
		
	return ans;
}
int size(deQue q)
{
	return q -> size;//返回双端队列元素的个数 
}
ELEMENT head(deQue q)
{
	if (empty(q)) {//如果双端队列中没有元素，那么操作违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	return q -> data[q -> head];//区间是[head, tail)，所以双端队列的头元素就在head上 
}
ELEMENT tail(deQue q)
{
	if (empty(q)) {//如果双端队列中没有元素，那么操作违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	return q -> tail != 0? q -> data[q -> tail - 1]: q -> data[q -> MaxSize - 1];//区间是[head, tail),所以双端队列尾元素，实际上在tail的前一个位置。
																				//但tail可能是0，减一就越界了，所以是在下标MaxSize - 1位置 
																				//如果不是0就直接返回减一位置的元素，就行了 
}
void FreeDeque(deQue q) 
{
	free(q -> data);//先释放存放元素的空间 
	free(q);//在释放双端队列的空间 
}

双端队列的链式实现(链表)

//双端队列链式实现(链表) 
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 10
#define ERROR -1 

typedef int ELEMENT;

struct QNode{//元素的节点 
	ELEMENT data;
	struct QNode* next;//指向后一个节点 
	struct QNode* prior;//指向前一个节点 
};

typedef struct QNode QNode;

typedef struct queue {//队列的结构 
	QNode* head;//指向链表头 
	QNode* tail;//指向链表尾 
	int size;//记录双端队列元素的个数 
}deque,*deQue;

deQue CreateDeque(void);//创建一个双端队列 
bool empty(deQue q);//判断双端队列是不是空 
bool addFront(deQue q, ELEMENT item);//在双端队列头添加元素 
bool addLast(deQue q, ELEMENT item);//在双端队列尾添加元素 
ELEMENT deleteFront(deQue q);//让双端队列的头元素出队 
ELEMENT deleteLast(deQue q);//删除双端队列尾的元素 
int size(deQue q);//返回双端队列元素的个数 
ELEMENT head(deQue q);//返回双端队列头的元素，但不出队 
ELEMENT tail(deQue q);//返回双端队列尾的元素，但不出队 
void FreeDeque(deQue q);//释放双端队列 

int main(int argc, char* argv[])
{
	deQue q = CreateDeque();
	
	addFront(q, 1);
	addLast(q, 2); 
	addFront(q, 3);
	
	pr("size = %d\n", size(q));
	pr("tail = %d\n", tail(q));
	pr("head = %d\n", head(q));
	
	FreeDeque(q);
	
	return 0;
}

deQue CreateDeque(void)
{
	deQue q = (deQue)malloc(sizeof(deque));//开辟一个双端队列 
	
	q -> head = NULL;//初始化为空 
	q -> tail = NULL;//初始化为空 
	q ->size = 0;//初始化大小为0 
	
	return q;
}
bool empty(deQue q)
{
	return !q -> size;//如果元素个数为0，代表双端队列为空，不为0代表双端队列不是空 
}
bool addFront(deQue q, ELEMENT item)
{
	QNode* t = (QNode*)malloc(sizeof(QNode));//开辟一个元素节点 

	if (t == NULL) {//如果空间不够，就不能添加，返回false 
		return false;
	}
	
	t -> data = item;//存放元素 
	t -> prior = NULL;//初始化为空 
	t -> next = NULL;//初始化为空 
	
	if (empty(q)) {//如果双端队列为空 
		q -> size++;//让双端队列的元素个数加一 
		q -> head = t;//让双端队列的头指针指向新开辟的节点 
		q -> tail = t;//让双端队列的尾指针指向新开辟的节点，因为它没有元素，所以头是它，尾也是它 
		return true;//添加成功返回true 
	}
	
	q -> head -> prior = t;//让双端队列的头指针指向新开辟的节点 
	t -> next = q -> head;//让新开辟的节点指向双端队列的头指针 
	q -> head = t;//更新双端队列的头指针 
	q -> size++;//让双端队列的元素个数加一 
	
	return true;
}
bool addLast(deQue q, ELEMENT item)
{
	QNode* t = (QNode*)malloc(sizeof(QNode));//开辟一个元素节点 

	if (t == NULL) {//如果空间不够，就不能添加，返回false 
		return false;
	}
	
	t -> data = item;//存放元素 
	t -> prior = NULL;//初始化为空
	t -> next = NULL;//初始化为空
	
	if (empty(q)) {//如果双端队列为空 
		q -> size++;//让双端队列的元素个数加一
		q -> head = t;//让双端队列的头指针指向新开辟的节点
		q -> tail = t;//让双端队列的尾指针指向新开辟的节点，因为它没有元素，所以头是它，尾也是它
		return true;//添加成功返回true
	}
	
	q -> tail -> next = t;//让双端队列的尾指针指向新开辟的节点 
	t -> prior = q -> tail;//让新开辟的节点的前指针指向双端队列的尾 
	q -> tail = t;//更新双端队列得尾指针 
	q -> size++;//让双端队列的元素个数加一
	
	return true;
}
ELEMENT deleteFront(deQue q)
{
	QNode* t = q -> head;//用一个临时指针指向双端队列的头 
	
	if (empty(q)) {//如果双端队列为空，操作违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	if (size(q) == 1) {//如果双端队列的元素个数只有一个的话 
		ELEMENT ans = t -> data;//取出双端队列头的元素 
		
		q -> head = NULL;//让双端队列的头指向空 
		q -> tail = NULL;//让双端队列的尾指向空，因为只有一个元素，所以删掉之后，双端队列就没有元素了，所以让尾指针也指向空 
		q -> size--;//让双端队列的元素个数减一 
		
		free(t);//释放双端队列头的节点 
		
		return ans;//返回双端队列头节点的元素 
	}
	
	ELEMENT ans = t -> data;//取出双端队列头的元素 
	q -> head = t -> next;//让双端队列的头指针指向下一个节点
	q -> head -> prior = NULL;//让双端队列新的头的前一个指针指向空，让前一个节点，在链表中断开联系 
	q -> size--;//让双端队列的元素个数减一 

	free(t);//释放双端队列之前头的节点 
	
	return ans;//返回双端队列头节点的元素
}
ELEMENT deleteLast(deQue q)
{
	QNode* t = q -> tail;//指向双端队列尾的节点 
	
	if (empty(q)) {//如果双端队列为空，操作违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	if (size(q) == 1) {//如果双端队列中的元素个数只有一个 
		ELEMENT ans = t -> data;//取出双端队列尾的元素 
		
		q -> head = NULL;//让双端队列的头指针指向空，因为只有一个元素，所以这个元素既是头也是尾。因此要让头指针也指向空 
		q -> tail = NULL;//让双端队列的头指针指向空 
		q -> size--;//让双端队列的元素个数减一
		
		free(t);//释放双端队列尾的节点
		
		return ans;//返回双端队列尾节点的元素 
	}
	
	ELEMENT ans = t -> data;//取出双端队列尾的元素 
	q -> tail = t -> prior;//让双端队列的尾指针指向双端队列尾节点的前一个节点
	q -> tail -> next = NULL;//让双端队列的尾节点的前一个节点的next指针指向空，让双端队列的尾节点从链表中断开联系  
	q -> size--;//让双端队列的元素个数减一
	
	free(t);//释放双端队列的尾节点 
	
	return ans;//返回双端队列之前尾节点的元素 
}
int size(deQue q)
{
	return q -> size;//返回双端队列的元素个数 
}
ELEMENT head(deQue q)
{
	if (empty(q)) {//如果双端队列为空，操作违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	return q -> head -> data;//返回双端队列的头节点元素 
}
ELEMENT tail(deQue q)
{
	if (empty(q)) {//如果双端队列为空，操作违法，返回一个特定值ERROR 
		return ERROR;
	}
	
	return q -> tail -> data;//返回双端队列的尾节点元素 
}
void FreeDeque(deQue q)
{
	if (empty(q)) {//如果双端队列为空，直接释放双端队列的空间 
		free(q);
		return ;
	}
	
	QNode* t = NULL;//开辟一个临时指针 
	QNode* p = q -> head;//指向双端队列的头节点 
	
	while(p)  {//释放双端队列的元素空间 
		t = p;
		p = p -> next;
		free(t) ;
	}
	
	free(q);//释放双端队列的空间 
}