首页 > 编程语言 >数据结构与算法----------3

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

时间：2023-12-08 20:12:30浏览次数：36  
标签：head return 队列 双端 元素 tail 算法 ---------- 数据结构

队列

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

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

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

代码实现

//队列的顺序实现(非环形数组)
#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);//释放双端队列的空间 
}

 

标签：head,return,队列,双端,元素,tail,算法,----------,数据结构
From： https://www.cnblogs.com/lwj1239/p/17888886.html

相关文章

  • P1541-DP【绿】
    刚开始理解错题意了，题中说“玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片”指的是不能用同一张卡片，我给理解成不能连续用同一种卡片了。后来想想其实题目中的说法歧义不大，是我粗心才导致看错的。最终我看错的导致了题目难度更高一些，偏偏写完了更高难度的题之......
  • 线段树
    首先是建树我们先构建整棵树的框架 structnode{intl,r;stringdata;}g[N*4];//不一定非要构建结构体，看题目需求，如果不涉及左右范围的话就可以直接构造数组 //n表示的是树上每个结点的数值，比如说第一个结点为1，那莫第一个结点的左子树为2，右子树为3//l(是......
  • 二分——acwing算法基础课笔记
    个人笔记，欢迎补充、指正。此次完全以个人理解来写。整数二分 整数二分有两种，分别是找左边界和找右边界。 寻找符合要求的左边界：绿色点intbsearch_1(intl,intr){while(l<r){intmid=l+r>>1;//对应下界，最左if(check(mid))r=......
  • 财贸双全清除系统冗余数据
    管家婆财贸双全清除冗余数据deletefromt_cw_dlyndxwheredraft<>2deletefromt_cw_dlyndxwherevchcodenotin(selectvchcodefromt_cw_dly)TRUNCATETABLEt_CW_bakdlyTRUNCATETABLEt_cw_bakdlysup--TRUNCATETABLET_CW_Dlysup--(里面是支付方式，财务版本里面最......
  • 《钢岚》今日首发，成为首款基于HarmonyOS NEXT开发的战棋新游
    今日，紫龙游戏旗下BlackJack工作室全新战棋旗舰作品《钢岚》在华为游戏中心首发上线，并宣布《钢岚》完成鸿蒙原生应用开发，成为基于HarmonyOSNEXT开发的首款战棋新游，不但进一步丰富了鸿蒙生态战棋品类游戏内容，也是鸿蒙生态游戏内容建设的重要进展，为鸿蒙生态注入更多新鲜血液。作为......
  • Linux内核开发流程指南 【ChatGPT】
    原文：https://www.kernel.org/doc/html/v6.6/process/development-process.htmlLinux内核开发流程指南目录：介绍1.1.执行摘要1.2.本文内容1.3.鸣谢1.4.将代码纳入主线的重要性1.5.许可证开发流程的运作方式2.1.大局观2.2.补丁的生命周期2.3.补丁如何进入内核2......
  • Linux内核开发流程指南 - 介绍【ChatGPT】
    https://www.kernel.org/doc/html/v6.6/process/1.Intro.html简介1.1.执行摘要本节的其余部分涵盖了内核开发过程的范围以及开发人员及其雇主可能遇到的各种挫折。有许多原因说明为什么内核代码应该合并到官方（“主线”）内核中，包括自动提供给用户、社区以多种形式提供支持以及......
  • 【2023-12-08】抗压能力
    20:00人这一辈子最容易犯的错误有两条，一曰以己贬人，二曰以己度人。第一条就是过高估计了自己，而过低估计了旁人。第二条以为自己的好恶就必然是别人的好恶，自己的标准就是别人的标准。                              ......
  • 容器函数
    #include<bits/stdc++.h>usingnamespacestd;intmain(){//第三种 intb1[]={1,2,3,4,5}; vector<int>b(b1,b1+sizeof(b1)/sizeof(int)); inta1[]={1,2}; vector<int>a(a1,a1+sizeof(a1)/sizeof(int)); b.insert(b.begin(),a.begin(),a.end())......
  • VECTOR INSERT()
    #include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>a(20);a.push_back(1);intarr[]={1,2,3,4,5};vector<int>b(arr,arr+sizeof(arr)/sizeof(int));intar[]={7,8,9,10,11};vecto......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99