栈和队列知识点+例题

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶，另一端成为栈底。遵守后进先出的原则（类似于弹夹）

压栈：栈的插入操作叫做进栈/入栈/压栈，入数据在栈顶

出栈：栈的删除操作叫做出栈，出数据也在栈顶

那如何实现栈呢？

 经过比较，数组栈是最优解，（链式的扩容会很久才会扩容一下）

由于top的位置意义不同，我们分为两种解决方案

1.2基本操作 

1.定义一个栈

typedef int SLDataType；
typedef struct Stack
{
    int *a;
    int top;
    int capacity;
}

2,初始化一个栈

void STInit(ST*pst)
{
     assert(pst);
    pst->a=NULL;
    pst->top=0;
    pst->capacity=0;
}

3压栈

void STPush(ST* pst, SLDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		ST* newcapacity = pst->capacity == 0 ? 4 : capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc((SLDataType)*newcapacity);
		if (newcapacity == NULL)
		{
			return -1;
		}
		else
		{
			pst->a = tmp;
			pst->capacity = newcapacity;
			pst->a[pst->top] = x;
			pst->top++;
		}
	}
}

 4，弹栈

void STPop(ST* pst)
{
    assert(pst);
    assert(pst->top>0);
    pst->top--;
}

5 返回栈顶元素

void STTop(ST* pst)
{
    assert(pst);
    assert(pst->top>0);
    return pst->a[pst->top-1];
}

6 判断是否为空

bool STEmpty(ST* pst)
{
	assert(pst);
	if (pst->top == 0)
	{
		return true;

	}
	else
	{
		return false;
	}
}

7 栈的大小

int STSize(ST* pst)
{
    assert(pst);
    return pst->top;
}

8销毁栈

void STDestory(ST*pst)
{
    assert(pst);
    free(pst->a);
    pst->a=NULL;
    pst->top=pst->capacity=0;
}

让我们看几道例题吧

例题1：

 思路：栈的顺序是后进先出，有题可知，最后一个是E，所以E先出，故选B

例题2：

 我们首先看选项，A选项：1先进，1先出，把2 3 4放进去，把4拿出来，再把3拿出来，最后把2拿出来。同理，我们看C选项，把1 2 3放进去，然后把3拿出来，然后我们会发现，如果想要拿1的话，拿2是必经之路，所以此选项错误

例题3：

 思路：

1，先建立一个栈，初始化一个栈，

2，然后我们把所有的左括号放入栈里面，如果不是左括号，即是有括号；

3，其次我们要知道，本题的关键在于数量匹配和顺序匹配。所以我们要考虑一下栈是否为空（右括号的数量大于左括号的数量），然后考虑顺序匹配的问题

4，最后我们看栈是否为空，如果为空，就返回true，然后把栈毁掉

bool isVaild(char* s)
{
	ST st;// 定义一个栈
	STInit(&st);
	while (*s)
	{
		if (*s == '[' || *s == '{' || *s == '(')
		{
			STPush(&st, *s);
			s++;
		}
		else
		{
			if (STEmpty(&st))
			{
				return false;
			}
			//栈里面取左括号
			char top = STTop(&st);
			STPop(&st);
			//顺序不匹配
			if (*s == ']' && top != '[') || (8s == '}' && top != '{') || (*s == ')' && top == '(')
			{
				return false;
			}
			s++;
		}
	}
	//栈为空，返回真，说明数量都匹配
	bool ret = STEmpty(&st);
	STDestory(&pst);
	return ret;
}

好啦~栈我们就先讲到这里啦，让我们看一下队列的知识点吧

2，队列

2.1队列的概念和结构

 我们可以考虑一个问题

入队之后，出队的时候顺序是唯一一定的吗？

答案是：当然是；

从以上我们可以了解到，栈用数组的方法比较好；而队列用单链表，头删尾插的方式比较好

2.2基本操作

1定义一个队列

typedef int QueueType;
typedef struct QueueNode
{
	QueueType val;
	struct QueueNode* next;

}QNode;

为了解决二级指针以及两个指针的问题，我们可以把两个指针放入一个结构体里面，然后进行一级指针的操作即可

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

2.初始化一个队列

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

3.插入到队列

	void QueuePush（Queue* pq, QDataType x)
	{
		QNode* newnode = (QNode*)malloc(sizeof(QNode));
		if (newnode == NULL)
			return -1;
		else
		{
			newnode->val = x;
			newnode->next = NULL;
		}
		if (pq->tail == NULL)
		{
			return -1;

			pq->tail = pq->phead = newnode;
		}
		else
		{
			pq->tail->next = newnode;
			pq->tail = newnode;
		}
		pq->size++;
	}

4. 头删

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	if (pq->phead = NULL)
		pq->tail = NULL;
}

5找头结点的值

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

6队列是否为空

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

  return pq->phead=NULL;
}

7队列大小

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

8销毁队列

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		cur = next;
	}
pq->phead=pq->ptail=NULL;
}

让我们看几道关于队列和栈的例题吧

例题1：

思路： 

 代码实现：

typedef struct
{
	Queue q1;
	Queue q2;

}Stack;

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

	return pst;
}
void mystackpush(Mystack* obj, int x)
{
	Queue Empty = &obj->q1;
	Queue nonEmpty =&obj->q2;
	if (!Empty(&obj->q1))
	{
		Queue Empty = &obj->q2;
		Queue nonEmpty = &obj->q1;
	}
	//开始到数据
	while (QueueSize(nonempty) > 1)
	{
		QueuePush(Empty, QueueFront(nonempty));
		QueuePop(nonempty);
	}
	int top = QueueFront(nonempty);
	QueuePop(nonempty);
	return top;
}

int mystackTop(Mystack* obj)
{
	if (!Empty(&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)
{
	QueueDestory(&obj->q1);
	QueueDestory(&obj->q2);
	free(obj);
}

例题2：

 

 思路：

 代码实现：

 

typedef struct
{
	int* a;
	int top;
	int capacity;
}ST;
typedef struct
{
	ST pushst;
	ST popst;
}MyQueue;
//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
//压栈
void STPush(ST* pst, SLDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		ST* newcapacity = (SLDataType*)malloc(sizeof(SLDataType);
		SLDataType* tmp = pst->capacity == 0 ? 4 : newcapacity * 2;
		if (newcapacity == 0)
		{
			return -1;
		}
		else
		{
			pst->a = tmp;
			pst->capacity = newcapacity;
			pst->a[pst->top] = x;
			pst->top++;
		}
	}
}
//返回栈顶元素
void STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}
//弹栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
//判断是否为空
bool STEmpty(ST* pst)
{
	assert(pst);
	if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return -1;
	}
}
MyQueue* myQueueCreate()
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	STInit(&obj->pushst);
	STInit(&obj->popst);
	return obj;
}
void myQueuePush(MyQueue* obj, int x)
{
	STPush(&obj->pushst, x);
}
返回队列开头的元素（不删除）
void myQueuepeek(MyQueue* obj)
{
	if (!STEmpty(&obj->popst))
	{
		return STTop(&obj->popst);
	}
	else
	{
		while (!STEmpty(&obj->pushst))
		{
			STPush(&obj->popst, STTop(&obj->pushst);
			STPop(&obj->pushst);
		}
		return STTop(&obj->popst);
	}
}
//从队列开头移除并返回元素
void myQueuePop(MyQueue* obj)
{
	int front = myQueuePeek(obj);
	STPop(&obj->popst);
	return front;
}
bool myQueueEmpty(MyQueue* obj)
{
	return  STEmpty(&obj->pushst) && (&obj->popst);
}
void myQueueFree(MyQueue* obj)
{
	STDestory(&obj->popst);
	STDestory(&obj->pushst);
	free(obj);
}

接下来我们看一下循环队列吧

1.判断循环队列是否为空：front==back（front指向对头，back指向队尾的下一个）

 

 如何判断队列是否为满

1.前提：front==back（当size=0时，为空，size！=0则为满）

2，再增加一个地方）

即

数组实现（back+1）%（k+1）==front则为满，其中，k+1指的是开辟空间的个数，k指的是有效数据数 数组实现&（k+1）是为了防止溢出

链表实现，即把上面式子去掉  %（k+1）

链表实现：

 

 数组实现：

 单链表缺陷以及找尾的办法：

 如何计算循环中元素的个数

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 = 0;
	return obj;
}
//是否为空
bool myCircularQueueEmpty(MyCircularQueue* obj)
{
	return obj->front = obj - back;

}
//是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	return (obj->front) % (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) = obj->back;
	return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj, int value)
{

	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	++obj->front;
	obj->front % (obj->k + 1) = obj->front;
	return true;
}
//返回队头
int myCircularQueueFront(MyCircularQueue* obj)
{
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	return obj->a[obj->front];
}
//返回队尾
int myCircularQueueRear(MyCircularQueue* obj)
{
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	return obj->a[obj->back - 1];
}
//清空
void myCircularQueueFree(MyCircularQueue* obj)
{
	free(obj->a);
	free(obj);
}

好啦~关于栈和队列的知识点就这些啦~谢谢大家观看~

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

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

相关文章

【考研数学】正交变换后如果不是标准型怎么办？| 关于二次型标准化的一些思考

【考研数学】正交变换后如果不是标准型怎么办？| 关于二次型标准化的一些思考

文章目录 引言一、回顾二次型的定义是什么？什么叫标准二次型？怎么化为标准型？ 二、思考写在最后 引言 前阵子做了下 20 年真题，问题大大的，现在订正到矩阵的第一个大题，是关于二次型正交变换的。和常规不同…
阅读更多...
『亚马逊云科技产品测评』活动征文｜通过lightsail一键搭建Drupal VS 手动部署

『亚马逊云科技产品测评』活动征文｜通过lightsail一键搭建Drupal VS 手动部署

『亚马逊云科技产品测评』活动征文｜通过lightsail一键搭建Drupal 提示：授权声明：本篇文章授权活动官方亚马逊云科技文章转发、改写权，包括不限于在 Developer Centre, 知乎，自媒体平台，第三方开发者媒体等亚…
阅读更多...
面试官：你能说说常见的前端加密方法吗？

面试官：你能说说常见的前端加密方法吗？

给大家推荐一个实用面试题库 1、前端面试题库 （面试必备） 推荐：★★★★★ 地址：web前端面试题库 前言 本篇文章略微介绍一下前端中常见的加密算法。前端中常见的加密算法主要形式包括——哈希函数，对称…
阅读更多...
图片叠加_图片压缩

图片叠加_图片压缩

图片叠加 try {/* 1 读取第一张图片*/File fileOne new File("1.png");BufferedImage imageFirst ImageIO.read(fileOne);/* 2读取第二张图片 */File fileTwo new File("2.png");BufferedImage imageSecond ImageIO.read(fileTwo);//创建一个最底层画…
阅读更多...
Ftrans自动同步软件：满足企业级数据同步的需求

Ftrans自动同步软件：满足企业级数据同步的需求

随着数字经济的发展，企业数字化的办公场景越来越复杂，其中一个急需解决的问题就是企业不同服务器之间的文件自动同步的需求。然而，目前市场上的同步软件通常有很多的缺点，让用户感到困扰。 1、数据安全：在同步数据的过…
阅读更多...
Apache POI（Java）

Apache POI（Java）

一、Apache POI介绍 Apache POI是Apache组织提供的开源的工具包（jar包）。大多数中小规模的应用程序开发主要依赖于Apache POI（HSSF XSSF）。它支持Excel 库的所有基本功能; 文本的导入和导出是它的主要特点。 我们可以使用 POI 在…
阅读更多...
起立科技(起鸿)在第25届高交会上展示透明OLED技术创新

起立科技(起鸿)在第25届高交会上展示透明OLED技术创新

第二十五届中国国际高新技术成果交易会 日期：2023年11月15日 地点：福田会展中心7号馆 深圳，2023年11月15日 — 起鸿科技，作为透明OLED领域的引领者，于今日参展了第二十五届中国国际高新技术成果交易会。这一展会将汇…
阅读更多...
云计算赛项容器云2023搭建

云计算赛项容器云2023搭建

部署容器云平台[5 分] 使 用 OpenStack 私 有 云 平 台 创 建 两 台 云 主 机 ， 云 主 机 类 型 使 用 4vCPU/12G/100G 类型，分别作为 Kubernetes 集群的 Master 节点和 node 节点， 然后完成 Kubernetes 集群的部署，并完成 Istio …
阅读更多...
MAC上修改mysql的密码（每一步都图文解释哦）

MAC上修改mysql的密码（每一步都图文解释哦）

当你想要连接本机数据库时，是不是有可能突然忘记了自己的数据库密码? 在此文中，我们来详细解决一下如何去修改自己的数据库密码，并使用Navicat来连接测试 1.停止mysql服务 打开终端，键入命令,将mysql服务先停止掉，…
阅读更多...
身份证阅读器和社保卡读卡器Harmony鸿蒙系统ArkTS语言SDK开发包

身份证阅读器和社保卡读卡器Harmony鸿蒙系统ArkTS语言SDK开发包

项目需求，用ArkTS新一代开发语言实现了在Harmony鸿蒙系统上面兼容身份证阅读器和社保卡读卡器，调用了DonseeDeviceLib.har这个读卡库。 需要注意的是，鸿蒙系统的app扩展名为.hap，本项目编译输出的应用为：entry-default…
阅读更多...
4-1三个整数的最大数

4-1三个整数的最大数

#include<stdio.h> int main(){int a,b,c,t,max;printf("请输入三个数&#xff1a;");scanf("%d,%d,%d",&a,&b,&c);t(a>b)?a:b;max(t>c)?t:c;printf("输出三个数中最大是数字是&#xff1a;%d",max);return 0;}
阅读更多...
Redis 的集群模式实现高可用

Redis 的集群模式实现高可用

来源&#xff1a;Redis高可用&#xff1a;武林秘籍存在集群里&#xff0c;那稳了~ (qq.com) 1. 引言 前面我们已经聊过 Redis 的主从同步&#xff08;复制&#xff09;和哨兵机制&#xff0c;这期我们来聊 Redis 的集群模式。 但是在超大规模的互联网应用中&#xff0c;业务规…
阅读更多...
交易量原则，昂首资本一个比喻说清楚

交易量原则，昂首资本一个比喻说清楚

即使你是刚进入交易市场的新手小白&#xff0c;也可能听过这句话&#xff1a;“当需求超过供给时&#xff0c;市场就会上涨。当供应超过需求时&#xff0c;市场就会下跌。”为了理解交易量的重要性&#xff0c;昂首资本来看看这句话背后的原则。 对于未接触过此类术语的读者&a…
阅读更多...
京东小程序：无代码开发实现API集成，连接电商平台、CRM和客服系统

京东小程序：无代码开发实现API集成，连接电商平台、CRM和客服系统

无需复杂API开发&#xff0c;京东小程序连接电商平台 京东小程序平台以其全开放的生态模式&#xff0c;让商家享有京东系APP流量福利、海量SKU和开放能力&#xff0c;提升用户体验&#xff0c;同时也带来了新商机。京东小程序的最大优势在于&#xff0c;商家无需进行复杂的API…
阅读更多...
接口自动化项目落地之HTTPBin网站

接口自动化项目落地之HTTPBin网站

原文&#xff1a;https://www.cnblogs.com/df888/p/16011061.html 接口自动化项目落地系列 找个开源网站或开源项目&#xff0c;用tep实现整套pytest接口自动化项目落地&#xff0c;归档到电子书&#xff0c;作为tep完整教程的项目篇一部分。自从tep完整教程发布以后&#…
阅读更多...
WMS仓储管理系统的工作流程是什么

WMS仓储管理系统的工作流程是什么

在当前的物流行业中&#xff0c;高效和精准的仓库管理被视为成功的关键。为了满足这一需求&#xff0c;WMS仓储管理系统应运而生。这个系统是物流中心的核心部分&#xff0c;可以显著提高仓库的运营效率&#xff0c;为现代物流管理带来前所未有的便捷。 WMS仓储管理系统的工作流…
阅读更多...
josef约瑟 闭锁继电器 LB-7DG 100V 50HZ 导轨安装

josef约瑟 闭锁继电器 LB-7DG 100V 50HZ 导轨安装

LB-7型闭锁继电器 闭锁继电器LB-7导轨安装 一、用途 LB-7型闭锁继电器(以下简称继电器)用于发电厂及变电所内高压母线带电时防止和接地刀闸。 二、结构和工作原理 1、继电器按整流式原理构成&#xff0c;该继电器由变压器、电阻器、整流桥、滤波电容、极化继电器及指示灯组…
阅读更多...
openGauss学习笔记-128 openGauss 数据库管理-设置透明数据加密（TDE）

openGauss学习笔记-128 openGauss 数据库管理-设置透明数据加密（TDE）

文章目录 openGauss学习笔记-128 openGauss 数据库管理-设置透明数据加密&#xff08;TDE&#xff09;128.1 概述128.2 前提条件128.3 背景信息128.4 密钥管理机制128.5 表级加密方案128.6 创建加密表128.7 切换加密表加密开关128.8 对加密表进行密钥轮转 openGauss学习笔记-12…
阅读更多...
php伪随机数

php伪随机数

利用工具 php_mt_seed <?php // php 7.2function white_list() {return mt_rand();}echo white_list(), "\n";echo white_list(), "\n";echo white_list(), "\n"; 输入命令&#xff1a; ./php_mt_seed 1035656029 <?phpmt_srand(181095…
阅读更多...
腐蚀监测常用技术及作用

腐蚀监测常用技术及作用

上次我们介绍了设备状态监测中的红外热像技术>>热成像仪的工作原理及在工业设备状态监测中的应用&#xff0c;这次我们一起来探讨腐蚀监测技术方面的内容。 在工业领域中&#xff0c;腐蚀监测技术是腐蚀控制的重要部分和可靠而有效的手段。通过对设备的腐蚀情况进行监测和…
阅读更多...
最新文章

Copyright @ 2022~2023