C语言数据结构-----栈和队列练习题(分析+代码)

前言

前面的博客写了如何实现栈和队列，下来我们来看一下队列和栈的相关习题。

链接: 栈和队列的实现

文章目录

  • 前言
  • 1.用栈实现括号匹配
  • 2.用队列实现栈
  • 3.用栈实现队列
  • 4.设计循环队列

1.用栈实现括号匹配

在这里插入图片描述

此题最重要的就是数量匹配和顺序匹配。
用栈可以完美的做到：
1.左括号入栈
2.有右括号，取栈顶左括号匹配

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;		// 标识栈顶位置的
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;

	// 表示top指向栈顶元素的下一个位置
	pst->top = 0;

	// 表示top指向栈顶元素
//pst->top = -1;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	pst->top--;
}

STDataType STTop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

bool STEmpty(ST* pst)
{
	assert(pst);

	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pst->top == 0;
}

int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
//这里以上都是栈的代码
bool isValid(char* s)
{
	ST st;
	STInit(&st);
	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			STPush(&st, *s);
		}
		else
		{
			if (STEmpty(&st)!=NULL)//右括号比左括号多
			{
				STDestroy(&st);
				return false;
			}

			char top = STTop(&st);
			STPop(&st);

			if ((*s == ']' && top != '[')//控制顺序不匹配
				|| (*s == '}' && top != '{')
				|| (*s == ')' && top != '('))
			{
				STDestroy(&st);
				return false;
			}
		}
		++s;
	}
	bool ret = STEmpty(&st);//如果栈空了，那么就是都匹配走了
	STDestroy(&st);         //只要不空，说明没匹配完，但只能解决左括号多，右括号少的问题
	return ret;
}

2.用队列实现栈

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
这样感觉没什么用，很低效，但是这题考的就是我们对于队列和栈性质的理解！

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->val = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;

	if (pq->phead == NULL)
		pq->ptail = NULL;

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->ptail);

	return pq->ptail->val;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}
//这里之前都是队列的代码
typedef struct //匿名结构体
{
	Queue q1;
	Queue q2;
} MyStack;


MyStack* myStackCreate() 
{
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&pst->q1);
	QueueInit(&pst->q2);
	return pst;
}

void myStackPush(MyStack* obj, int x) //插入，哪个不为空就往哪里插，都为空随便进一个都行
{
	if (!QueueEmpty(&obj->q1))
		QueuePush(&obj->q1, x);
	else
		QueuePush(&obj->q2, x);
}

int myStackPop(MyStack* obj) 
{
	//假设q1为空，q2不为空
    Queue* emptyq=&obj->q1;
    Queue* nonemptyq=&obj->q2;
	if (!QueueEmpty(&obj->q1))//如果假设错了,就交换
	{
		emptyq = &obj->q2;
		nonemptyq = &obj->q1;   
	}
	//非空队列钱N-1个元素导入空队列，最后一个就是栈顶元素
	while (QueueSize(nonemptyq)>1)
	{
		QueuePush(emptyq, QueueFront(nonemptyq));//将非空队列插入空队列
		QueuePop(nonemptyq);//删掉
	}
	//并返回栈顶元素
	int top=QueueFront(nonemptyq);
    QueuePop(nonemptyq);
    return top;
}

int myStackTop(MyStack* obj) 
{
	//谁不为空就返回谁的队尾数据，队尾数据就是导数据之后栈顶的数据
	if (!QueueEmpty(&obj->q1))
		return QueueBack(&obj->q1);
	else
		return QueueBack(&obj->q2);
}

bool myStackEmpty(MyStack* obj) 
{
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);//两个都为空才是空
}

void myStackFree(MyStack* obj) 
{
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}

3.用栈实现队列

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

和队列实现栈的思路一样，主要考察栈和队列的性质

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>


typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;		// 标识栈顶位置的
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;

	// 表示top指向栈顶元素的下一个位置
	pst->top = 0;

	// 表示top指向栈顶元素
	//pst->top = -1;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	pst->top--;
}

STDataType STTop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

bool STEmpty(ST* pst)
{
	assert(pst);

	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pst->top == 0;
}

int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
//以上为栈的代码
typedef struct 
{
	ST pushst;//入数据栈
	ST popst;//出数据栈
} MyQueue;


MyQueue* myQueueCreate() 
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	STInit(&obj->popst);
	STInit(&obj->pushst);
	return obj;
}

void myQueuePush(MyQueue* obj, int x) 
{
	STPush(&obj->pushst, x);
}

int myQueuePop(MyQueue* obj)
{
	int front = myQueuePeek(obj);//有数据不动，没数据导数据
	STPop(&obj->popst);
	return front;
}

int myQueuePeek(MyQueue* obj) //返回队列开头的元素
{
	if (STEmpty(&obj->popst))//如果popst不为空,跳到最后返回栈顶元素
	{                        
		while (!STEmpty(&obj->pushst))
		{//popst为空，那就导数据，把pushst的数据导入popst，再返回栈顶元素
			STPush(&obj->popst, STTop(&obj->pushst));
			STPop(&obj->pushst);
		}
	}
	return STTop(&obj->popst);//返回栈顶元素
}

bool myQueueEmpty(MyQueue* obj) 
{
	return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

void myQueueFree(MyQueue* obj) 
{
	STDestroy(&obj->popst);
	STDestroy(&obj->pushst);
	free(obj);
}

部分函数的结构如下：
在这里插入图片描述

4.设计循环队列

在这里插入图片描述
在这里插入图片描述
①
在这里插入图片描述
②
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdbool.h>

typedef struct
{
    int* a;//数组指针(一开始开的空间)
    int front;//头
    int back;//尾
    int k;//数据个数
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = 0;
    obj->back = 0;
    obj->k = k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->front == obj->back;//头等于尾是空
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    return (obj->back + 1) % (obj->k + 1) == obj->front;//上述图片分析出的公式
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //插入
{
    if (myCircularQueueIsFull(obj))
        return false;              //如果满了就返回错

    obj->a[obj->back] = value;
    obj->back++;
    obj->back %= (obj->k + 1);//防止越界
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) //删除
{
    if (myCircularQueueIsEmpty(obj))
        return false;

    ++obj->front;
    obj->front %= (obj->k + 1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) //从队首获取元素。如果队列为空，返回 -1 。
{
    if (myCircularQueueIsEmpty(obj))
        return -1;

    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) //获取队尾元素。如果队列为空，返回 -1 。
{
    if (myCircularQueueIsEmpty(obj))
        return -1;

    if (obj->back == 0)
        return obj->a[obj->k];
    else
        return obj->a[obj->back - 1];
}


void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->a);
    free(obj);
}

部分代码结构如下：
①
在这里插入图片描述
②
在这里插入图片描述
③
在这里插入图片描述

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

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

相关文章

性能优化中使用Profiler进行内存泄露的排查及解决方式

性能优化中使用Profiler进行内存泄露的排查及解决方式

文章目录 一、前言二、内存泄露的排查方式三、参考链接 一、前言 对于常规意义上的线程使用要及时关闭&#xff0c;数据库用完要及时关闭&#xff0c;数据用完要及时清空等等这里不再赘述&#xff0c;但是在开发中总会有不熟悉的api&#xff0c;开发进度过快&#xff0c;开发人…
阅读更多...
[⑥ADRV902x]: 软件系统初始化流程学习

[⑥ADRV902x]: 软件系统初始化流程学习

前言 本篇博客主要记录ADRV902x参考软件中对ADRV902x系统的初始化流程&#xff0c;使用API函数来实现transceiver的配置&#xff0c;校准和控制等。官方将整个系统初始化称之为multichip synchronization initialization (MCS) sequence&#xff0c;主要分成PreMcsInit&#x…
阅读更多...
CMA认证是什么?CMA软件测试报告如何获取?

CMA认证是什么?CMA软件测试报告如何获取?

资格证书在各行各业都是一种专业性象征&#xff0c;如第三方检测机构的CMA认证&#xff0c;在相应的检测报告上加盖CMA章可获得国家以及行业认可&#xff0c;还是享受税收优惠的有力证明材料。 一、CMA认证是什么? 　　CMA是中国计量认证的简称&#xff0c;由省级以上人民政府…
阅读更多...
SpringBoot 入门学习

SpringBoot 入门学习

开发环境配置 JDK 1.8、Maven 3.8.8、 IDEA CE 2023.2 框架介绍 Spring Boot 是由 Pivotal 团队提供的全新框架&#xff0c;其设计目的是用来简化 Spring 应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置&#xff0c;从而使开发人员不再需要定义样板化的配置…
阅读更多...
基于单片机温湿度光照自动窗帘系统设计

基于单片机温湿度光照自动窗帘系统设计

**单片机设计介绍&#xff0c; 基于单片机温湿度光照自动窗帘系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的温湿度光照自动窗帘系统是一种智能家居系统&#xff0c;通过使用单片机作为控制核心&#xff0c…
阅读更多...
LeetCode Hot100 543.二叉树的直径

LeetCode Hot100 543.二叉树的直径

题目&#xff1a; 给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 方法&#xff1a;灵神 代码&#xff1a; ​…
阅读更多...
Kafka生产者发送消息的流程

Kafka生产者发送消息的流程

Kafka 生产者发送消息的流程涉及多个步骤&#xff0c;从消息的创建到成功存储在 Kafka 集群中。以下是 Kafka 生产者发送消息的主要步骤&#xff1a; 1. 创建消息 生产者首先创建一个消息&#xff0c;消息通常包含一个键&#xff08;可选&#xff09;和一个值&#xff0c;以及…
阅读更多...
手写数字识别加法器--深度学习实验

手写数字识别加法器--深度学习实验

上次老师布置了一个实验&#xff1a; 手写数字识别--深度学习实验-CSDN博客 这次在上次的基础上又布置了一个实验&#xff0c;也是做了好久才做出&#xff0c;所以把实验报告放到CSDN保存&#xff0c;自己忘了方便查阅&#xff0c;也为其他人提供借鉴。 实验源码自取&#x…
阅读更多...
关于easy-es的聚合问题-已解决

关于easy-es的聚合问题-已解决

es实体类&#xff1a; public class ChemicalES {IndexId(type IdType.CUSTOMIZE)private Long id;HighLightIndexField(fieldType FieldType.TEXT, analyzer "ik_max_word")private String name;IndexField(fieldType FieldType.KEYWORD)private List<Stri…
阅读更多...
记一次深入内核的数据库高并发性能优化实践

记一次深入内核的数据库高并发性能优化实践

前不久&#xff0c;我们接到客户长江电力的反馈&#xff0c;称在生产环境中进行高并发查询&#xff0c;例如包含数百个测点的近千个并发作业&#xff0c;在从近三月的数据中取数或聚合计算时&#xff0c;会出现作业超时&#xff0c;但CPU利用率却很低。 接到反馈后&#xff0c…
阅读更多...
rabbitMQ对优先级队列的使用

rabbitMQ对优先级队列的使用

注意事项&#xff1a; 1.队列设置优先级 权制范围&#xff08;0-255&#xff09;推荐0-10 否则浪费CPU与内存 2.发消息时给消息设置优先级 3.消息需要完全事先在队列中&#xff0c;在被消费者消费 会被排序&#xff0c;否则边生产边消费不会达到预期的队列优先效果。 优先级队列…
阅读更多...
Skywalking接入实际应用做日志跟踪

Skywalking接入实际应用做日志跟踪

Skywalking客户端挂载 从官网下载skywalking-agent客户端&#xff0c;并挂在到应用服务器指定目录 挂载到应用主机中,好处是解决打包应用镜像的时候&#xff0c;镜像过大&#xff0c;部署成本过高。 docker-compose部署应用,并接入skywalking服务,这里以gateway为例 versio…
阅读更多...
vr红色教育虚拟展馆全景制作提升单位品牌形象

vr红色教育虚拟展馆全景制作提升单位品牌形象

720全景展馆编辑平台以其独特的优势&#xff0c;为展览行业带来了革命性的变革。这种创新的技术应用为参展商提供了更高效、更便捷、更全面的展示解决方案&#xff0c;进一步提升了展览行业的水平和影响力。 一、提升展示效果&#xff0c;增强品牌形象 720全景展馆编辑平台通过…
阅读更多...
Aseprite for mac(像素动画制作工具)

Aseprite for mac(像素动画制作工具)

Aseprite是一款专业的像素绘图软件&#xff0c;旨在方便用户创建动画和像素艺术作品。该软件提供了一系列强大的绘图工具和动画功能&#xff0c;使其成为许多游戏开发者、动画师和艺术家的首选工具之一。 Aseprite具有用户友好的界面&#xff0c;易于上手&#xff0c;使用户可以…
阅读更多...
MAX/MSP SDK学习06：内存管理

MAX/MSP SDK学习06：内存管理

提供两种内存分配方式&#xff1a;①简单指针&#xff0c;②句柄&#xff08;二级指针&#xff09;&#xff1b;官方文档建议使用前者。 // 简单指针 char *ptr; ptr sysmem_newptr(2000); post("I have a pointer %lx and it is %ld bytes in size",ptr, sysmem_p…
阅读更多...
存在即合理，低代码的探索之路

存在即合理，低代码的探索之路

目录 一、前言 二、低代码迅速流行的原因 三、稳定性和生产率的最佳实践 四、程序员用低代码开发应用有哪些益处&#xff1f; 1、提升开发价值 2、利于团队升级 一、前言 低代码的热潮至今未消停&#xff0c;从阿里钉钉跨平台协作方式&#xff0c;再到飞书上的审批流程&#xf…
阅读更多...
OMP: Error #15: Initializing libiomp5md.dll

OMP: Error #15: Initializing libiomp5md.dll

问题描述 在conda虚拟环境运行程序时&#xff0c;出现以下的错误&#xff1a; 问题原因 anaconda的环境下存在两个libiomp5md.dll文件。 解决方法 一、在代码上加上限制&#xff08;每次都得加&#xff09; import os os.environ[KMP_DUPLICATE_LIB_OK]True 这种方法解决不…
阅读更多...
6.一维数组——用冒泡法，选择法将5个整数由大到小排序

6.一维数组——用冒泡法，选择法将5个整数由大到小排序

文章目录 前言一、题目描述 二、题目分析 三、解题 程序运行代码&#xff08;冒泡法&#xff09;程序运行代码&#xff08;选择法&#xff09; 前言 本系列为一维数组编程题&#xff0c;点滴成长&#xff0c;一起逆袭。 一、题目描述 用冒泡法将5个整数由大到小排序 二、题目…
阅读更多...
印刷企业建设数字工厂管理系统的工作内容有哪些

印刷企业建设数字工厂管理系统的工作内容有哪些

随着科技的不断进步&#xff0c;数字工厂管理系统在印刷企业中的应用越来越广泛。这种系统可以有效地整合企业内外资源&#xff0c;提高生产效率&#xff0c;降低生产成本&#xff0c;并为印刷企业提供更好的业务运营与管理模式。本文将从以下几个方面探讨印刷企业建设数字工厂…
阅读更多...
奇异值分解SVD（Singular Value Decomposition）

奇异值分解SVD（Singular Value Decomposition）

一种理解方式&#xff0c;值得学习&#xff08;分解时空矩阵&#xff09; 先在这里阐述一下SVD的用途吧&#xff0c;具体细节稍后再做补充 1.通过SVD对数据的处理&#xff0c;我们可以使用小得多的数据集来表示原始数据集&#xff0c;这样做实际上是去除了噪声和冗余信息&…
阅读更多...
最新文章

Copyright @ 2022~2023