C语言之数据结构之栈和队列的运用

目录

    • 1. 用队列实现栈
      • 1.1 思路讲解
      • 1.2 代码实现
    • 2. 用栈实现队列
      • 1.1 思路讲解
      • 1.2 代码实现
    • 总结

在这里插入图片描述
•͈ᴗ•͈ 个人主页：御翮
•͈ᴗ•͈ 个人专栏：C语言数据结构
•͈ᴗ•͈ 欢迎大家关注和订阅!!!

在这里插入图片描述

1. 用队列实现栈

题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[ [ ], [1], [2], [ ], [ ], [ ] ]
输出：
[ null, null, null, 2, 2, false ]

解释：

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

  • 1 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top 都保证栈不为空

1.1 思路讲解

首先队列的特性是先入先出，而栈的特性是先入后出

题目说用两个队列实现一个栈

所以当栈为空时我们有两个空队列q1和q2

我们入数据时先默认入q2，假设这里依次入1、2、3

在这里插入图片描述

如果这个时候我们要出栈呢，如果按队列先入先出，我们会拿到1而不是最后入的3

此时我们可以先把1和2依次放入q1中，此时q2中就只剩3，就可以先取出3了

在这里插入图片描述

如果我们接着要放数据，就放入非空的队列q1，这样留一个队列q2为空，就还可以继续这样的出栈操作

在这里插入图片描述

当我们要继续出栈时，就把前n-1个数据放入空的队列中，再把最后一个数据取出，这样如此颠倒反复，就完成了先入后出的操作

在这里插入图片描述

1.2 代码实现

队列代码：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

typedef int QDatatype;

typedef struct QNode
{
	struct QNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void Init_Queue(Queue* ptr)
{
	assert(ptr);
	ptr->head = ptr->tail = NULL;
}
void Destroy_Queue(Queue* ptr)
{
	assert(ptr);
	QNode* cur = ptr->head;
	while (ptr->head != NULL)
	{
		cur = ptr->head;
		ptr->head = ptr->head->next;
		free(cur);
	}
	ptr->tail = NULL;
}

QNode* Buy_Node()
{
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	return tmp;
}

void Print_Queue(Queue* ptr)
{
	assert(ptr);
	QNode* cur = ptr->head;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void Push_Queue(Queue* ptr, QDatatype val)
{
	assert(ptr);
	QNode* newnode = Buy_Node();
	if (newnode == NULL)
	{
		perror("Push_Queue\n");
		exit(1);
	}
	newnode->data = val;
	newnode->next = NULL;
	if (ptr->head == NULL)
	{
		ptr->head = ptr->tail = newnode;
	}
	else
	{
		ptr->tail->next = newnode;
		ptr->tail = newnode;
	}
}

int Queue_Size(Queue* ptr)
{
	assert(ptr);
	int count = 0;
	QNode* cur = ptr->head;
	while (cur != NULL)
	{
		cur = cur->next;
		count++;
	}
	return count;
}

void Pop_Queue(Queue* ptr)
{
	assert(ptr);
	if (ptr->head == NULL)
	{
		printf("队列中没有元素\n");
		return;
	}
	if (Queue_Size(ptr) == 1)
	{
		free(ptr->tail);//如果删完了但是没有将tail置为NULL，则case 5 会发生错误，显示队尾元素随机值。
		ptr->tail = NULL;
		ptr->head = NULL;
		return;
	}
	QNode* pop = ptr->head;
	ptr->head = ptr->head->next;
	free(pop);
}

QDatatype Queue_Front(Queue* ptr)
{
	assert(ptr);
	return ptr->head->data;
}

QDatatype Queue_Back(Queue* ptr)
{
	assert(ptr);
	return ptr->tail->data;
}

int Check_Empty(Queue* ptr)
{
	assert(ptr);
	if (Queue_Size(ptr))
		return 0;
	else
		return 1;
}

//以上是自己创建的队列，因为c语言没有队列

队列实现栈代码：

typedef struct 
{
	Queue q1;
	Queue q2;
} MyStack;



// 创建栈
MyStack* myStackCreate() 
{
	MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));

	if (tmp == NULL) // 开辟空间可能失败，失败则终止程序
	{
		printf("Fail: myStackCreate\n");
		exit(1);
	}

	Init_Queue(&tmp->q1); // 我们的栈由两个队列组成，所以初始化要调用队列的初始化
	Init_Queue(&tmp->q2);

	return tmp;
}



// 数据入栈
void myStackPush(MyStack* obj, int x) 
{
	if (Check_Empty(&obj->q1)) // 哪个队列有元素就往哪放，两个都没有就默认放q2，保证只有一个队列有数据
	{
		Push_Queue(&obj->q2, x);
	}
	else
		Push_Queue(&obj->q1, x);
}



// 数据出栈
int myStackPop(MyStack* obj) 
{
	//题目保证每次调用pop时栈都不为空，不用考虑为空时的pop

	if (Check_Empty(&obj->q1)) // 哪个队列有数据就将n-1个数据放到另一个队列，剩下的最后一个元素就是栈顶元素，直接出栈
	{
		int sum = Queue_Size(&obj->q2); // 获取队列元素个数n

		for (int i = 0; i < sum - 1; i++) // 将前n-1个数据放到另一个空队列
		{
			Push_Queue(&obj->q1, Queue_Front(&obj->q2));
			Pop_Queue(&obj->q2);
		}

		QDatatype tmp = Queue_Front(&obj->q2); // 保存最后一个元素的值，再pop，因为要返回出栈元素的值
		Pop_Queue(&obj->q2);

		return tmp;
	}
	else
	{
		int sum = Queue_Size(&obj->q1);

		for (int j = 0; j < sum - 1; j++)
		{
			Push_Queue(&obj->q2, Queue_Front(&obj->q1));
			Pop_Queue(&obj->q1);
		}

		QDatatype tmp = Queue_Front(&obj->q1);

		Pop_Queue(&obj->q1);
		return tmp;
	}
}



// 获取栈顶元素
int myStackTop(MyStack* obj) 
{
	//题目保证每次调用top时栈都不为空，不用考虑为空时的top

	if (Check_Empty(&obj->q1)) // 因为我们前面入栈时保证了只有一个队列有数据，所以队尾元素就是栈顶元素
	{
		return Queue_Back(&obj->q2);
	}
	else
		return Queue_Back(&obj->q1);
}



// 判断栈是否为空
bool myStackEmpty(MyStack* obj) 
{
	if (Check_Empty(&obj->q1) && Check_Empty(&obj->q2)) // 栈由两个队列组成，两个队列都为空栈就为空
	{
		return true;
	}
	else
		return false;
}



// 销毁栈
void myStackFree(MyStack* obj) 
{
	Destroy_Queue(&obj->q1); // 消耗栈要销毁里面的两个队列
	Destroy_Queue(&obj->q2);
	free(obj);
}

2. 用栈实现队列

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

注意：

  • 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 ：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[ [ ], [1], [2], [ ], [ ], [ ] ]
输出：
[ null, null, null, 1, 1, false ]

解释：

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

1.1 思路讲解

首先栈的特性是先入后出，而队列的特性是先入先出

题目说用两个栈实现一个队列

所以当队列为空时我们有两个空栈

我们给这两个栈分别命名为push和pop

我们入数据只往push里放

在这里插入图片描述

出数据的话，如果pop为空，我们就把push栈里面的数据全放进pop栈里，再出栈，就取到了队头的元素

在这里插入图片描述

如果pop不为空，就直接出栈就好了

在这里插入图片描述

后序有数据也是直接放在push，push只进行入栈，pop只进行出栈，不像用队列实现栈一样要来回颠倒。

1.2 代码实现

栈代码：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <errno.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* stack;
	int size;
	int capacity;
}Stack;

void Init_Stack(Stack* ptr)
{
	assert(ptr);
	STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType));
	if (tmp == NULL)
	{
		perror("Init_Stack\n");
		exit(1);
	}
	ptr->stack = tmp;
	ptr->capacity = 3;
	ptr->size = 0;
}

void Destroy_Stack(Stack* ptr)
{
	assert(ptr);
	free(ptr->stack);
	ptr->stack = NULL;
}

void Check_Capacity(Stack* ptr)
{
	assert(ptr);
	if (ptr->size == ptr->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("Check_Capacity\n");
			exit(1);
		}
		ptr->stack = tmp;
		ptr->capacity *= 2;
	}
}

void Print_Stack(Stack* ptr)
{
	assert(ptr);
	for (int i = 0; i < ptr->size; i++)
	{
		printf("%d ", ptr->stack[i]);
	}
	printf("\n");
}

void Push_Stack(Stack* ptr, STDataType val)
{
	assert(ptr);
	Check_Capacity(ptr);
	ptr->stack[ptr->size] = val;
	ptr->size++;
}

void Pop_Stack(Stack* ptr)
{
	assert(ptr);
	ptr->size--;
}

STDataType Top_Stack(Stack* ptr)
{
	assert(ptr);
	return ptr->stack[ptr->size - 1];
}

int Size_Stack(Stack* ptr)
{
	assert(ptr);
	return ptr->size;
}

int Empty_Stack(Stack* ptr)
{
	assert(ptr);
	if (ptr->size == 0)
		return 1;
	else
		return 0;
}

typedef struct 
{
	Stack push;
	Stack pop;
} MyQueue;

栈实现队列代码：

// 创建队列
MyQueue* myQueueCreate() 
{
	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));

	if (queue == NULL) // 开辟空间有可能失败，失败则终止程序
	{
		perror("myQueueCreate");
		exit(1);
	}

	Init_Stack(&queue->push); // 初始化队列要初始化里面的栈
	Init_Stack(&queue->pop);

	return queue;
}



// 数据入队列
void myQueuePush(MyQueue* obj, int x) 
{
	Push_Stack(&obj->push, x); // 数据只入push栈
}



// 数据出队列
int myQueuePop(MyQueue* obj) 
{
	if (Empty_Stack(&obj->pop)) // 如果pop栈为空，就要从push栈里面把数据拿过来
	{
		int sum = Size_Stack(&obj->push); // 获取push中的元素个数n

		for (int i = 0; i < sum; i++)
		{
			Push_Stack(&obj->pop, Top_Stack(&obj->push));
			Pop_Stack(&obj->push);
		}
	}

	int ret = Top_Stack(&obj->pop); // 先储存队头元素再出队列，因为题目要返回队头元素
	Pop_Stack(&obj->pop);

	return ret;
}



// 获取队头元素
int myQueuePeek(MyQueue* obj) 
{
	if (Empty_Stack(&obj->pop)) // 如果pop栈为空，那就把push栈里面的元素拿过来
	{
		int sum = Size_Stack(&obj->push);
		for (int i = 0; i < sum; i++)
		{
			Push_Stack(&obj->pop, Top_Stack(&obj->push));
			Pop_Stack(&obj->push);
		}
	}

	return Top_Stack(&obj->pop); // 队头元素就是pop栈中的栈顶元素，因为pop栈内的元素是push栈内的元素顺序颠倒过来
}



// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) 
{
	if (Empty_Stack(&obj->push) && Empty_Stack(&obj->pop)) // 两个栈都为空，队列就为空
	{
		return true;
	}
	else
		return false;
}



// 销毁队列
void myQueueFree(MyQueue* obj) 
{
	Destroy_Stack(&obj->push);  // 销毁队列要销毁里面的两个栈
	Destroy_Stack(&obj->pop);
	free(obj);					// 不要忘记释放这个空间
}

总结

两个队列实现栈需要来回颠倒。
两个栈实现队列要确定一个push和一个pop。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/600978.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

uniapp 自定义App UrlSchemes

uniapp 自定义App UrlSchemes

需求&#xff1a;外部浏览器H5页面&#xff0c;跳转到uniapp开发的原生app内部。 1、uniapp内部的配置&#xff1a; &#xff08;1&#xff09;打开manifest->App常用其他设置&#xff0c;如下&#xff0c;按照提示输入您要设置的urlSchemes&#xff1a; &#xff08;2&am…
阅读更多...
如何更好地使用Kafka? - 故障时解决

如何更好地使用Kafka? - 故障时解决

要确保Kafka在使用过程中的稳定性&#xff0c;需要从kafka在业务中的使用周期进行依次保障。主要可以分为&#xff1a;事先预防&#xff08;通过规范的使用、开发&#xff0c;预防问题产生&#xff09;、运行时监控&#xff08;保障集群稳定&#xff0c;出问题能及时发现&#…
阅读更多...
自签名进行免杀

自签名进行免杀

文章目录 什么是自签名使用cmd生成自签名文件对EXE进行签名将PFX签名使用脚本安装到受信任的根证书颁发机构 什么是自签名 在对抗AV/EDR中使用签名文件是一种很好的策略,拥有签名也就意味着是安全的程序, 大多数AV是不会杀签名程序的,但是签名程序的获取往往比较麻烦使用过期签…
阅读更多...
RabbitMQ之消费者并发消费

RabbitMQ之消费者并发消费

为什么要引入消费者的并发消费&#xff1f; 当生产者的推送速度是远远超过消费者的能力的&#xff0c;可以提高消费者的消费速度。比如在java中我们可以启动多个 JVM 进程&#xff0c;实现多进程的并发消费&#xff0c;从而加速消费的速度&#xff0c;在mq中也可以通过设置配置…
阅读更多...
Momentum靶机系列Momentum2

Momentum靶机系列Momentum2

先进行arp扫描&#xff1a; 获得渗透靶机的IP&#xff1a;192.168.13.142 扫描一下靶机的使用的端口&#xff1a; 具有tcp端口和http服务的80端口 可以扫描一下80端口的http服务&#xff1a; 可以发现一个网站&#xff1a;http://192.168.13.142 打开该网址&#xff1a; 查看…
阅读更多...
error code [1449]； The user specified as a definer (‘root‘@‘%‘) does not exist

error code [1449]； The user specified as a definer (‘root‘@‘%‘) does not exist

其实就是说我的root用户权限不够&#xff0c;那就要加上权限&#xff0c;网上其他地方也有好多处理办法&#xff0c;但是要注意数据库版本。我用的是MySQL8.0.32版本&#xff0c;我是这样处理的&#xff0c;简单可行&#xff1a; GRANT ALL ON *.* TO root% ;FLUSH PRIVILEGES…
阅读更多...
当AI遇见现实：数智化时代的人类社会新图景

当AI遇见现实：数智化时代的人类社会新图景

文章目录 一、数智化时代的机遇二、数智化时代的挑战三、如何适应数智化时代《图解数据智能》内容简介作者简介精彩书评目录精彩书摘强化学习什么是强化学习强化学习与监督学习的区别强化学习与无监督学习的区别 前言/序言 随着科技的日新月异&#xff0c;我们步入了一个前所未…
阅读更多...
爬虫学习：XPath匹配网页数据

爬虫学习：XPath匹配网页数据

目录 一、安装XPath 二、XPath的基础语法 1.选取节点 三、使用XPath匹配数据 1.浏览器审查元素 2.具体实例 四、总结 一、安装XPath 控制台输入指令&#xff1a;pip install lxml 二、XPath的基础语法 XPath是一种在XML文档中查找信息的语言&#xff0c;可以使用它在HTM…
阅读更多...
B端系统菜单栏中使用阿里图标

B端系统菜单栏中使用阿里图标

B端系统菜单栏中使用阿里图标 1.需求说明 由于组件库自带的图标数量和内容有限&#xff0c;采用丰富多样的阿里图标是不错的选择 2.阿里图标使用 2.1官网 iconfont-阿里巴巴矢量图标库 2.2使用 2.2.1.先根据关键词搜索并选择对应的图标 注意&#xff1a;若只是少量的sv…
阅读更多...
自动驾驶学习1-超声波雷达

自动驾驶学习1-超声波雷达

1、简介 超声波雷达&#xff1a;利用超声波测算距离的雷达传感器装置&#xff0c;通过发射、接收 40kHz、48kHz或 58kHz 频率的超声波&#xff0c;根据时间差测算出障碍物距离&#xff0c;当距离过近时触发报警装置发出警报声以提醒司机。 超声波&#xff1a;人耳所不能听到的…
阅读更多...
FMEA助力智能电网升级：构建安全、高效、可靠的电力网络

FMEA助力智能电网升级：构建安全、高效、可靠的电力网络

随着科技的不断进步&#xff0c;智能电网已成为现代电力行业的重要发展方向。而在这个过程中&#xff0c;FMEA&#xff08;失效模式和影响分析&#xff09;作为一种重要的质量管理工具&#xff0c;正日益发挥着其在智能电网建设中的赋能作用。本文将从FMEA的基本概念出发&#…
阅读更多...
Study--Oracle-02-单实例部署Oracle19C

Study--Oracle-02-单实例部署Oracle19C

一、CentOS 7 环境准备 1、软件准备 操作系统&#xff1a;CentOS 7 数据库版本: Oracle19C 2、操作系统环境配置 关闭selinux &#xff0c;编辑 /etc/selinux/config文件&#xff0c;设置SELINUX enforcing 为SELINUXdisabled [rootoracle ~]# grep SELINUX /etc/seli…
阅读更多...
顺序表的实现（迈入数据结构的大门）

顺序表的实现（迈入数据结构的大门）

什么是数据结构 数据结构是由&#xff1a;“数据”与“结构”两部分组成 数据与结构 数据&#xff1a;如我们所看见的广告、图片、视频等&#xff0c;常见的数值&#xff0c;教务系统里的&#xff08;姓名、性别、学号、学历等等&#xff09;&#xff1b; 结构&#xff1a;当…
阅读更多...
python网络爬虫学习——编写一个网络爬虫

python网络爬虫学习——编写一个网络爬虫

参考资料&#xff1a;用Python写网络爬虫&#xff08;第2版&#xff09; 1、编写一个函数 &#xff08;1&#xff09;用于下载网页&#xff0c;且当下载网页发生错误时能及时报错。 # 导入库 import urllib.request from urllib.error import URLError,HTTPError,ContentTooS…
阅读更多...
Golang 开发实战day12 - Pointer

Golang 开发实战day12 - Pointer

&#x1f3c6;个人专栏 &#x1f93a; leetcode &#x1f9d7; Leetcode Prime &#x1f3c7; Golang20天教程 &#x1f6b4;‍♂️ Java问题收集园地 &#x1f334; 成长感悟 欢迎大家观看&#xff0c;不执着于追求顶峰&#xff0c;只享受探索过程 Golang 开发实战day12 - 指针…
阅读更多...
Hive读写文件机制

Hive读写文件机制

Hive读写文件机制 1.SerDe是什么&#xff1f; SerDe是Hive中的一个概念&#xff0c;代表着“序列化/反序列化” &#xff08;Serializer/Deserializer&#xff09;。 SerDe在Hive中是用来处理数据如何在Hive与底层存储系统&#xff08;例如HDFS&#xff09;之间进行转换的机制…
阅读更多...
Xinstall广告效果监测，助力广告主优化投放策略

Xinstall广告效果监测，助力广告主优化投放策略

在移动互联网时代&#xff0c;APP推广已成为企业营销的重要手段。然而&#xff0c;如何衡量推广效果&#xff0c;了解用户来源&#xff0c;优化投放策略&#xff0c;一直是广告主和开发者面临的难题。这时&#xff0c;Xinstall作为国内专业的App全渠道统计服务商&#xff0c;以…
阅读更多...
SpringBoot项目部署到阿里云服务器

SpringBoot项目部署到阿里云服务器

部署步骤 步骤分以下&#xff1a; 将SpringBoot项目打包Linux上准备好Java环境、可用的MySql数据库项目上传到服务器启动项目停止项目 1.SpringBoot项目打包 数据库的链接&#xff0c;账户和密码需要和Linux上一致。 如上图打包即可。 2.Linux上准备好Java环境以及Mysql环境…
阅读更多...
微生物群落构建（community assembly）

微生物群落构建（community assembly）

Introduction Zhou, J. & Ning, D. Stochastic Community Assembly: Does It Matter in Microbial Ecology? Microbiol Mol Biol Rev 81, e00002-17 (2017). This review is very comprehensive (1)&#xff01; 周集中老师实验室的长期研究兴趣集中在从基因组到生态系统…
阅读更多...
ZIP压缩输出流（将ZIP文件解压）

ZIP压缩输出流（将ZIP文件解压）

文章目录 前言一、ZIP压缩输出流是什么&#xff1f;二、使用介绍 1.使用方法2.实操展示总结 前言 该篇文章相对应的介绍如何使用java代码将各种文件&#xff08;文件夹&#xff09;从ZIP压缩文件中取出到指定的文件夹中。解压流将ZIP文件中的文件以条目的形式逐一读取&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023