首页 > 编程语言 >408 数据结构队列算法

408 数据结构队列算法

时间:2024-07-28 20:17:11浏览次数:16  
标签:结点 return 队列 ElemType front 数据结构 rear 408

第三章 队列

3.1顺序队列

#define MAXSIZE 64
typedef int ElemType;
typedef struct {
	ElemType data[MAXSIZE];
	int front;	//队头指针
	int rear;	//队尾指针
	int size;	//队列大小
}SeQueue;

//初始化队列
void initQueue(SeQueue& Q) {
	//对数据元素进行初始化,防止出现脏数据
	for (int i = 0; i < MAXSIZE; i++) {
		Q.data[i] = 0;
	}
	Q.front = 0;	//初始化队头指针指向0索引
	Q.rear = 0;		//队尾指针也指向0索引
	Q.size = 0;		//队列大小为0
}

//判断队列是否为空
bool isEmpty(SeQueue Q) {
	//return Q.front == Q.rear;	//如果front和rear指向同一个位置则队列为空
	return Q.size == 0;			//或直接用size是不是0来判断
}

//元素x入队
void enQueue(SeQueue& Q, ElemType x) {
	Q.data[Q.rear++] = x;	//在尾指针位置插入元素x后将尾指针后移(尾指针始终指向待入队元素的位置)
	Q.size++;	//位置队列长度
}

//队头元素出队,并返回
ElemType deQueue(SeQueue& Q) {
	if (!isEmpty(Q)) {		//如果队列不为空
		Q.size--;			//队列长度-1
		return Q.data[Q.front++];	//返回队头元素后将队头指针后移
	}
	return -999;		//如果队列为空返回-999代表空
}

//获取队首元素
ElemType getHead(SeQueue Q) {
	if (isEmpty(Q)) {		//如果队列不为空,直接返回队头元素否则返回-999
		return Q.data[Q.front];
	}
	return -999;
}

//获取队列长度
int getSize(SeQueue Q) {
	//return Q.size;		//直接返回Q.size即队列长度
	return Q.rear - Q.front;	//队尾指针位置-队头指针位置也为队列长度
}

//打印队列
void printQueue(SeQueue Q) {
	if (isEmpty(Q)) {
		return;
	}
	for (int i = Q.front; i < Q.rear; i++) {	//队头开始遍历
		printf("%d ", Q.data[i]);
	}
	printf("\n");
	printf("Q.front = %d ,Q.rear = %d,Q.size = %d\n", Q.front, Q.rear, Q.size);
}

3.2循环队列

#define MAXSIZE 8
typedef int ElemType;
typedef struct {
	ElemType data[MAXSIZE];
	int front;	//队头指针
	int rear;	//队尾指针
	int size;	//队列大小
}Queue;
/*
*用size判断队列空队列满可以避免一个空间的浪费,如果不使用size的话,至少要浪费一个空间来区分队满和队空
*/
//初始化队列
void initQueue(Queue& Q) {
	//对数据元素进行初始化,防止出现脏数据
	for (int i = 0; i < MAXSIZE; i++) {
		Q.data[i] = 0;
	}
	Q.front = 0;	//初始化队头指针指向0索引
	Q.rear = 0;		//队尾指针也指向0索引
	Q.size = 0;		//队列大小为0
}

//判断队列是否已满

bool isFull(Queue Q) {
	return (Q.rear + 1) % MAXSIZE == Q.front;
	//return Q.size == MAXSIZE;
}

//判断队列是否为空
bool isEmpty(Queue Q) {
		return Q.front == Q.rear;
	//return Q.size == 0;
}

//元素x入队
void enQueue(Queue& Q, ElemType x) {
	if (isFull(Q)) {
		return;
	}
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MAXSIZE;	
	Q.size++;
}

//队头元素出队,并返回
ElemType deQueue(Queue& Q) {
	if (isEmpty(Q)) {
		return -999;
	}
	ElemType x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MAXSIZE;
	Q.size--;
	return x;
}

//获取队首元素
ElemType getHead(Queue Q) {
	return Q.data[Q.front];
}

//获取队列长度
int getSize(Queue Q) {
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
	//return Q.size;
}

//打印队列元素
void printQueue(Queue Q) {
	if (isEmpty(Q)) {
		return;
	}
	int len = getSize(Q);
	int i = Q.front;
	while (len > 0) {
		printf("%d ", Q.data[i]);
		i++;
		if (i >= MAXSIZE) {
			i = 0;
		}
		len--;
	}
	printf("\n");
}

3.3链队列

typedef int ElemType;
//结点结构
typedef struct LNode {
	ElemType data;
	LNode* next;
}LNode;

//队列结构
typedef struct {
	LNode* front;	//队列的队头指针
	LNode* rear;	//队列的队尾指针
	int size;		//队列大小
}LinkedQueue;

//初始化队列
void initQueue(LinkedQueue& Q) {
	Q.front = NULL;
	Q.rear = NULL;
	Q.size = 0;
}

//判断队列是否为空
bool isEmpty(LinkedQueue Q) {
	if (Q.front == NULL && Q.rear == NULL) {
		return true;
	}
	else {
		return false;
	}
}

//元素x入队
void enQueue(LinkedQueue& Q, ElemType x) {
	LNode* node = (LNode *)malloc(sizeof(LNode));
	node->data = x;
	node->next = NULL;
	//如果是入队的第一个元素
	if (Q.front == NULL && Q.rear == NULL) {
		Q.front = node;
		Q.rear = node;
	}
	else {
		Q.rear->next = node;	//最后一个结点的next指向新结点元素
		Q.rear = node;			//rear指向新结点
	}
	Q.size++;				//队列长度+1
}

//队头元素出队,并返回
ElemType deQueue(LinkedQueue& Q) {
	if (isEmpty(Q)) {
		return -999;
	}
	LNode* removed = Q.front;	//记录队头(即被删除元素结点以便释放空间)
	ElemType x = removed->data;	//接收队头元素以便返回
	Q.front = Q.front->next;	//队头后移
	//如果已经出队直到没元素了,别忘了也让Q.rear = null
	if (Q.front == NULL) {
		 Q.rear = Q.front;
	}
	free(removed);	//释放删除结点空间
	Q.size--;		//队列长度-1
	return x;
}

//获取队首元素
ElemType getHead(LinkedQueue Q) {
	if (isEmpty(Q)) {
		return -999;
	}
	return Q.front->data;
}

//获取队列长度
int getSize(LinkedQueue Q) {
	return Q.size;
}

//打印队列元素
void printQueue(LinkedQueue Q) {
	LNode* p = Q.front;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

3.4双端队列(带头双链表实现)

//用双链表(带头结点)实现双端队列
typedef int ElemType;

typedef struct DNode {
	ElemType data;		//数据域
	DNode* prior;		//指向前驱结点的指针域
	DNode* next;		//指向后继结点的指针域
}DNode;

typedef struct {
	DNode* front;	//队头指针
	DNode* rear;	//队尾指针
	int size;		//队列长度
}DeQueue;

//初始化双端队列
void initDeQueue(DeQueue& Q) {
	DNode* head = (DNode*)malloc(sizeof(DNode));	//申请头结点
	//初始化头结点
	head->next = NULL;		
	head->prior = NULL;
	Q.front = head;	//队列的头指针和尾指针都指向头结点
	Q.rear = head;
	Q.size = 0;		//队列大小初始化为0
}

//判断队列是否为空
bool isEmpty(DeQueue Q) {
	return Q.size == 0;	
}

//向队头添加元素e
void pushHead(DeQueue& Q, ElemType e) {
	DNode* node = (DNode*)malloc(sizeof(DNode));	//申请结点空间
	node->data = e;	//为新元素结点赋值
	node->next = NULL;	//新结点结点前序后继初始化指向空
	node->prior = NULL;
	if (Q.front == Q.rear) {	//如果此时队列还无元素,插入第一个元素时
		node->prior = Q.front;		//新结点的前序是头结点
		Q.front->next = node;		//头结点的后继是当前新结点
		Q.rear = node;				//队尾来到新结点的位置
	}
	//如果入队的元素不是第一个
	else {				
		node->next = Q.front->next;	//当前结点的后继是头结点的后继
		Q.front->next->prior = node;	//头结点的后继的前序是当前节点
		Q.front->next = node;		//头结点的后继是当前结点
		node->prior = Q.front;		//当前结点的前序是头结点
	}
	Q.size++;			//队列长度+1
}

//从队头移除元素并返回
ElemType popHead(DeQueue& Q) {
	if (isEmpty(Q)) {		//如果队列为空返回-999代表空
		return -999;	
	}
	DNode* removed = Q.front->next;		//记录被删除结点
	ElemType x = removed->data;			//记录被删除结点的元素值
	if (removed->next == NULL) {		//如果队列只有一个元素了
		Q.front->next = NULL;			//直接让头结点的next指向NULL
		Q.rear = Q.front;				//队列的尾指针指向头结点表示队列已经为空了
	}
	else {
		Q.front->next = removed->next;	//头结点的后继指向被删除结点的后继
		removed->next->prior = Q.front;	//被删除结点的后继的前序指向头结点
	}
	free(removed);	//释放空间队列长度-1
	Q.size--;
	return x;
}

//向队尾添加元素e
void pushTail(DeQueue& Q, ElemType e) {
	DNode* node = (DNode*)malloc(sizeof(DNode));	//申请新结点空间
	node->data = e;		//给新结点赋值
	node->next = NULL;	//新结点的next先指向空
	Q.rear->next = node;	//队尾指针的next指向新结点
	node->prior = Q.rear;	//新结点的prior指向尾指针结点
	Q.rear = node;			//尾指针来到新结点位置
	Q.size++;	//队列长+1
}

//从队尾删除元素并返回
ElemType popTail(DeQueue& Q) {
	if (isEmpty(Q)) {
		return -999;
	}
	DNode* removed = Q.rear;	//记录被删除结点
	ElemType x = removed->data;	//记录被删除结点的元素值
	Q.rear->prior->next = NULL;	//队尾指针结点的前序的后继指向空,即倒数第二个结点的next指向空
	Q.rear = Q.rear->prior;	//队尾指针来到倒数第二个结点处
	free(removed);		//释放最后一个结点空间
	Q.size--;
	return x;
}

//获取队头元素
ElemType peekHead(DeQueue Q) {
	if (isEmpty(Q)) {
		return -999;
	}
	return Q.front->next->data;	//第一个元素是头结点的next
}

//获取队尾元素
ElemType peekTail(DeQueue Q) {
	if (isEmpty(Q)) {
		return -999;
	}
	return Q.rear->data;
}

//从前往后打印队列元素
void printDeQueuefromHead(DeQueue Q) {
	if (isEmpty(Q)) {
		return;
	}
	DNode* p = Q.front->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//从后往前打印队列元素
void printDeQueuefromTail(DeQueue Q) {
	if (isEmpty(Q)) {
		return;
	}
	DNode* p = Q.rear;
	while (p!=Q.front) {
		printf("%d ", p->data);
		p = p->prior;
	}
	printf("\n");
}

//获取队列长度
int getSize(DeQueue Q) {
	return Q.size;
}

3.5栈和队列的相关题目

01.设单链表的表头指针为L,结点结构由data和next两个域构成,其中data域为字符型。
试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称。

bool isSymmetry(LinkedList L) {
	int len = length(L) / 2;	//计算表长的一半,将一半元素入栈
	LNode* p = L;
	SqStack S;
	initStack(S);
	while (len > 0) {	//将一半元素入栈
		push(S, p->data);
		p = p->next;
		len--;
	}
	if (length(L) % 2 == 1) {	//如果表长为奇数,跳过最中间的一个
		p = p->next;
	}
	while (p) {
		if (pop(S) != p->data) {	//从右半边的第一个开始和栈中元素依次比较
			return false;		//如果有一个不满足栈顶元素和当前元素值相等返回false
		}
		p = p->next;
	}
	return true;
}

02.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操
作序列可表示为仅由I和O组成的序列,可以操作的序列称为合法序列,否则称为
非法序列。
1)下面所示的序列中哪些是合法的?
A. IOIIOIOO
B. IOOIOIIO.
C. IIIOIOIO
D. IIIOOIO0
2)通过对1) 的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回
true,否则返回false (假定被判定的操作序列已存入一维数组中)。
*/

bool isLegal(SqList L) {
	SqStack S;
	initStack(S);
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == 0) {	//用0表示O,1表示I。如果要出栈先看是不是空栈
			if (isEmpty(S)) {	//是空栈返回false
				return false;	
			}
			else {		//不是空栈直接把栈顶元素出站
				pop(S);
			}
		}
		else {		//入栈元素(随便入个元素模拟即可)
			push(S, -1);
		}
	}
	return isEmpty(S);	//最后如果栈为空证明合法。否则不合法
}

03.若希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0
或1来区分队头指针front和队尾指针rear相同时的队列状态是“空”还是“满”。
试编写与此结构相应的入队和出队算法。

typedef int ElemType;
typedef struct {
	ElemType data[MAXSIZE];
	int front;	//队头指针
	int rear;	//队尾指针
	int tag;	//用来标记队空还是队满 0 表示队空,1表示堆满
}Queue;

//初始化队列
void initQueue2(Queue& Q) {
	//对数据元素进行初始化,防止出现脏数据
	for (int i = 0; i < MAXSIZE; i++) {
		Q.data[i] = 0;
	}
	Q.front = 0;	//初始化队头指针指向0索引
	Q.rear = 0;		//队尾指针也指向0索引
	Q.tag = 0;      //初始化时tag=0表示队列为空
}

//判断队列是否已满

bool isFull2(Queue Q) {
	return Q.tag == 1 && Q.front == Q.rear;
}

//判断队列是否为空
bool isEmpty2(Queue Q) {
	return Q.tag == 0 && Q.front == Q.rear;
}

//元素x入队
void enQueue2(Queue& Q, ElemType x) {
	if (isFull2(Q)) {
		printf("队列已满\n");
		return;
	}
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MAXSIZE;
    //入队元素之后可能导致队列变满,如果满注意修改tag
	if (Q.rear == Q.front) {
		Q.tag = 1;
	}
}

//队头元素出队,并返回
ElemType deQueue2(Queue& Q) {
	if (isEmpty2(Q)) {
		printf("队列已空\n");
		return -999;
	}
	ElemType x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MAXSIZE;
    //出队后可能导致队列变空
	if (Q.front == Q.rear) {
		Q.tag = 0;
	}
	return x;
}

04.Q是一个队列,S是一个空栈,实现将队列中的元素逆置的算法。

//借助栈
void inverQueue(Queue& Q) {
	SqStack S;
	initStack(S);
	while (!isEmpty(Q)) {	//如果队列不为空
		ElemType x = deQueue(Q);	//依次出队并将出队元素进栈
		push(S, x);
	}
	while (!isEmpty(S)) {		//如果栈不为空
		enQueue(Q, pop(S));		//出栈并将出栈元素进队
	}
}

//利用递归
void inverQueue2(Queue& Q) {

	if (isEmpty(Q)) {		//终止条件
		return;
	}
	ElemType x = deQueue(Q);	//元素出队
	inverQueue2(Q);				//递归后续队列元素
	enQueue(Q, x);				//从前往后入队
}

05.用两个栈模拟队列的入队出队操作

void enToNewQueue(SqStack& S1,ElemType x) {	//模拟入队
	if (isFull(S1)) {	//S1作为辅助栈,如果S1不满,元素入队都入到S1中
		return;
	}
	push(S1, x);
}

ElemType deFromNewQueue(SqStack& S1, SqStack& S2) {	//模拟出队
	if (!isEmpty(S2)) {		//元素始终在S2中出队,如果S2有元素直接出队
		return pop(S2);
	}
	if (isEmpty(S1)) {
		return -999;	//如果S2和S1中都无元素,返回-999代表空
	}
	else {				//如果S2中无元素,看S2中是否有元素,如果有全部从S1出栈放到S2栈中
		while (!isEmpty(S1)) {
			push(S2, pop(S1));
		}
	}
	return pop(S2);		//返回S2的栈顶元素
}


bool isEmpty(SqStack S1, SqStack S2) {
	return isEmpty(S1) && isEmpty(S2);	//如果S1和S2都为空则返回空
}
void print(SqStack S1, SqStack S2) {
	while (!isEmpty(S2)) {
		printf("%d ", pop(S2));
	}
	while (!isEmpty(S1)) {
		push(S2, pop(S1));
	}
	while (!isEmpty(S2)) {
		printf("%d ", pop(S2));
	}
	printf("\n");
}

06.假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号,编写一个算法来判别表达式中的括号是否配对,以字符“\0” 作为算术表达式的结束符。

bool bracketCheak(char* str) {
	SqStack2 S;
	initStack2(S);
	int i = 0;
	while (str[i] != '\0') {
		switch (str[i]) {
			//左括号时直接压栈
		case '(':
		case'[':
		case'{':
			push2(S, str[i]);
			break;
			//右括号时如果栈为空或者栈顶与当前元素不匹配返回false
		case')':
			if (isEmpty2(S) || pop2(S) != '(')return false;
			break;
		case']':
			if (isEmpty2(S) || pop2(S) != '[')return false;
			break;
		case'}':
			if (isEmpty2(S) || pop2(S) != '{')return false;
			break;
		default:return false;
			break;
		}
		i++;
	}
	return isEmpty2(S);		//最后如果栈为空匹配成功,如果栈中还有元素不匹配
}

07.按下图所示铁道进行车厢调度(注意,两侧铁道均为单向行驶道,火车调度站有一个用于调度的“栈道”),火车调度站的入口处有n节硬座和软座车厢(分别用H和S表示)等待调度,试编写算法,输出对这n节车厢进行调度的操作(即入栈或出栈操作)序列,以使所有的软座车厢都被调整到硬座车厢之前。

image-20240118212106464

void train(char* train) {
	char* p = train, * res = train;//p是遍历指针,res理解成队尾指针(即该在哪个位置放入元素)
	SqStack2 S;
	initStack2(S);
	while (*p!='\0') {
		if (*p == 'H') {		//如果是硬座进栈
			push2(S, 'H');		
		}
		else {
			*(res++) = *p;	//如果是软座直接放到前面,res后移每次指向该连接的车厢
		}
		p++;
	}
	while (!isEmpty2(S)) {	//把栈中存的硬座车厢都甩后面去
		*(res++) = pop2(S);
	}
	//最后train就是排好的车厢
}

08.后缀表达式求值

int evalRPN(char* str) {
	Stack S;
	initStack(S);
	int i = 0;
	while (str[i] != '\0') {
		int cur = str[i] - '0';	//为了将char类型的数字'1'转成整型1
		switch (str[i])
		{
		case '+': {				//操作符弹栈两个元素计算新的结果重新入栈
			ElemType a = pop(S);
			ElemType b = pop(S);
			push(S, b + a);
		}break;
		case '-': {
			ElemType a = pop(S);
			ElemType b = pop(S);
			push(S, b - a);
		}break;
		case '*': {
			ElemType a = pop(S);
			ElemType b = pop(S);
			push(S, b * a);
		}break;
		case '/': {
			ElemType a = pop(S);
			ElemType b = pop(S);
			push(S, b / a);
		}break;
		default:push(S,cur);	//操作数直接入栈
			break;
		}
		i++;
	}
	return peek(S);		//最后栈顶元素就是结果
}

09.中缀表达式转后缀表达式

int priority(char ch) {
	if (ch == '*' || ch == '/') {
		return 2;
	}
	else if (ch == '+' || ch == '-') {
		return 1;
	}
	else if (ch == '(') {
		return 0;
	}
}
char* solve(char* str) {
	char* res = (char*)malloc(sizeof(char) * 100);
	int i = 0;
	int j = 0;
	SqStack S;
	initStack(S);
	while (str[i] != '\0') {
		//遇到操作符时
		if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
			//如果栈为空,直接将操作符入栈
			if (isEmpty(S)) {
				push(S, str[i]);
			}
			else {
				//当前操作符的优先级高于栈顶优先级时,直接入栈
				if (priority(str[i]) > priority(peek(S))) {
					push(S, str[i]);
				}
				else {
					//当栈不为空时去看栈中运算符优先级是否比当前操作符的优先级高或相等,满足大于等于时出栈
					while (!isEmpty(S) && priority(peek(S)) >= priority(str[i])) {
						res[j++] = pop(S);
					}
					//最后将当前操作符入栈
					push(S, str[i]);
				}
			}

		}
		//遇到左小括号直接入栈
		else if (str[i] == '(') {
			push(S, str[i]);
		}
		//遇到右小括号将栈中(之前的操作符都出栈
		else if (str[i] == ')') {
			while (!isEmpty(S) && peek(S) != '(') {
				res[j++] = pop(S);
			}
			//最后也将(出栈
			pop(S);
		}
		//如果是操作数直接连接到新的字符串后面
		else {
			res[j++] = str[i];
		}
		i++;//遍历指针每次后移
	}
	while (!isEmpty(S)) {
		res[j++] = pop(S);
	}
	res[j] = '\0';
	return res;
}

10.对于任意的无符号的十进制整数m,写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可)。[兰州大学(10 分)]

void decimalToHexadecimal(unsigned int m) {
	SqStack stack;
	initStack(stack);

	// 不断除以16,将余数入栈
	while (m != 0) {
		push(stack, m % 16);
		m /= 16;
	}
    
    //转8进制
	/*while (m != 0) {
		push(stack, m % 8);
		m /= 8;
	}*/
    
    //转二进制
	/*while (m != 0) {
		push(stack, m % 2);
		m /= 2;
	}*/

	// 出栈并打印
	while (!isEmpty(stack)) {
		unsigned int hex = pop(stack);
		if (hex < 10) {
			printf("%d", hex);
		}
		else {
			printf("%c", 'A' + hex - 10); // 10~15 对应 A~F
		}
	}
	printf("\n");
}

标签:结点,return,队列,ElemType,front,数据结构,rear,408
From: https://www.cnblogs.com/lingchuanfeng/p/18328818

相关文章

  • 【代码随想录训练营第42期 Day10打卡 LeetCode 232.用栈实现队列 225. 用队列实现栈 2
    目录一、做题心得二、题目与题解题目一:232.用栈实现队列题目链接题解题目二:225.用队列实现栈题目链接题解题目三:20.有效的括号题目链接题解题目四:1047.删除字符串中的所有相邻重复项 题目链接题解三、小结一、做题心得今天是代码随想录训练营打卡的第1......
  • CSP-S提高组数据结构算法模板大合集
    CSP-S算法总结2.2.1基础知识与编程环境无2.2.2C++程序设计2set/nultisetmap/multimapdeque/priority_queueSTL2.2.3数据结构P1886 滑动窗口/【模板】单调队列#include<iostream>usingnamespacestd;intn,k,a[1000005];intq[1000005],h,t;......
  • 数据结构-二叉树、堆、图
    一、线索二叉树规律:在有n个节点的链式二叉树中必定存在n+1个空指针链式二叉树中有很多的空指针,可以让这些空指针指向前一个节点\后一个节点,从而在有序遍历(中序遍历)二叉树时,不需要使用递归而通过循环即可以完成,并且效率要比递归快得多一定是搜索二叉树线索二叉树的结构typ......
  • C++ 数据结构体解析
    文章目录1.定义结构体2. 访问结构成员3. 结构作为函数参数4. 指向结构的指针5. typedef关键字1.定义结构体C/C++数组允许定义可存储相同类型数据项的变量,但是结构是C++中另一种用户自定义的可用的数据类型,它允许存储不同类型的数据项。结构用于表示一条记......
  • 从零开始学数据结构系列之第四章《克鲁斯卡尔算法应用场景-公交站问题》
    文章目录往期回顾某城市新增7个站点(A,B,C,D,E,F,G),现在需要修路把7个站点连通各个站点的距离用边线表示(权),比如A–B距离12公里问:如何修路保证各个站点都能连通,并且总的修建公路总里程最短?以上图为例,来对克鲁斯卡尔进行演示(假设用数组R保存......
  • 算法笔记|Day10栈与队列II
    算法笔记|Day10栈与队列II☆☆☆☆☆leetcode150.逆波兰表达式求值题目分析代码☆☆☆☆☆leetcode239.滑动窗口最大值题目分析代码☆☆☆☆☆leetcode347.前K个高频元素(待补充)题目分析代码☆☆☆☆☆leetcode150.逆波兰表达式求值题目链接:leetcode150.......
  • 算法笔记|Day9栈与队列
    算法笔记|Day9栈与队列☆☆☆☆☆leetcode232.用栈实现队列题目分析代码☆☆☆☆☆leetcode225.用队列实现栈题目分析代码☆☆☆☆☆leetcode20.有效的括号题目分析代码☆☆☆☆☆leetcode1047.删除字符串中的所有相邻重复项题目分析代码☆☆☆☆☆leetcod......
  • JUC并发编程:基于Condition实现一个阻塞队列
    Condition方法概述await():当前线程进入等待状态,直到被通知(siginal)或中断【和wait方法语义相同】。awaitUninterruptibly():当前线程进入等待状态,直到被通知,对中断不敏感。awaitNanos(longtimeout):当前线程进入等待状态直到被通知(siginal),中断或超时。awaitUnit......
  • 数据结构基础的学习
    数据结构:相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构:集合:所有数据在同一个集合中,关系平等。线性:数据和数据之间是一对一的关系树:一对多图:多对多物理结构(在内存当中的存储关系):顺序存储:数据存放在连续的存储单位中。逻辑关系和物理关系一致链式,数据存......
  • 数据结构的学习2
    树:n(n>=0)个结点的有限集合。n=0,空树。在任意一个非空树中,1,有且仅有一个特定的根结点2,当n>1时,其余结点可分为m个互不相交的有限集合T1,T2,T3.。。。。Tm,其中每一个集合又是一个树,并且称谓子树。结点拥有子树的个数称谓结点的度。度为0的结点称谓叶结点。度不为0,称谓......