栈和队列篇

目录

一、栈

1.栈的概念及结构

1.1栈的概念

1.2栈的结构示意图

2.栈的实现

2.1支持动态增长的栈的结构

2.2压栈(入栈)

2.3出栈

2.4支持动态增长的栈的代码实现

二、队列

1.队列的概念及结构

1.1队列的概念

1.2队列的结构示意图

2.队列的实现

2.1队列的结构

2.2队尾入队列

2.3队头出队列

2.4队列的代码实现

一、栈

1.栈的概念及结构

1.1栈的概念

        栈是一种特殊的线性表。栈只允许在固定的一端进行插入和删除数据的操作,栈的插入操作叫做压栈(进栈),栈的删除操作叫做出栈,进行数据插入和删除操作的一端叫做栈顶,另一端为栈底。栈中的元素遵循先进后出的原则。

1.2栈的结构示意图

2.栈的实现

        栈一般分为静态栈和支持动态增长的栈,静态栈由于栈的空间大小固定不具实用性,所以我们只针对支持动态增长的栈进行代码实现:

2.1支持动态增长的栈的结构

        栈的实现一般使用数组形式来实现,支持动态增长的栈即开辟一个动态数组a用来存储数据,当栈的容量满了之后方便扩容。

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

2.2压栈(入栈)

        每次压栈首先检查栈的容量是否已满,再决定是否需要扩容,压栈的元素变为新的栈顶

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 5 : (ps->capacity) * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

2.3出栈

        出栈后新的栈顶变为出栈前的栈顶的前一个元素

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

2.4支持动态增长的栈的代码实现

#pragma once
#include<assert.h>
#include<stdlib.h>
#include<stdio.h>

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//top指向栈顶的下一个位置,对top的操作需要是:先使用后++
	ps->capacity = 0;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 5 : (ps->capacity) * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

二、队列

1.队列的概念及结构

1.1队列的概念

        不同于栈的概念,队列只允许在其一端进行插入数据操作,在另一端进行删除数据操作。进行插入数据操作的一端是队尾,进行删除数据操作的一端是队头。队列是一种特殊的线性表,遵循先进先出的原则。

1.2队列的结构示意图

2.队列的实现

2.1队列的结构

        队列的实现一般使用链表的结构更优:

代码:

// 队列成员节点结构
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;

简图:

2.2队尾入队列

代码:

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	
	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
	if (NewNode == NULL)
	{
		perror("malloc:");
		return;
	}
	NewNode->data = data;
	NewNode->next = NULL;
	if (q->size == 0)
	{
		q->front = q->rear = NewNode;
	}
	else
	{
		q->rear->next = NewNode;
		q->rear = q->rear->next;
	}
	q->size++;
}

简图:

2.3队头出队列

代码:

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	//assert(!QueueEmpty(q));
	if (q->front ==q->rear)
	{
		if (q->front == NULL)
		{
			return;
		}
		else
		{
			free(q->front);
			q->front = q->rear = NULL;
		}
	}
	else
	{
		QNode* Tmp = q->front;
		q->front = Tmp->next;
		free(Tmp);
		Tmp = NULL;
	}
	q->size--;
}

简图:

2.4队列的代码实现

#pragma once
#include<assert.h>
#include<stdlib.h>
#include<stdio.h>

// 链式结构:表示队列成员节点
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	
	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
	if (NewNode == NULL)
	{
		perror("malloc:");
		return;
	}
	NewNode->data = data;
	NewNode->next = NULL;
	if (q->size == 0)
	{
		q->front = q->rear = NewNode;
	}
	else
	{
		q->rear->next = NewNode;
		q->rear = q->rear->next;
	}
	q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	//assert(!QueueEmpty(q));
	if (q->front ==q->rear)
	{
		if (q->front == NULL)
		{
			return;
		}
		else
		{
			free(q->front);
			q->front = q->rear = NULL;
		}
	}
	else
	{
		QNode* Tmp = q->front;
		q->front = Tmp->next;
		free(Tmp);
		Tmp = NULL;
	}
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0 ? 1 : 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
    while(!QueueEmpty(q))
    {
        QueuePop(q);
    }
}

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

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

相关文章

设计模式-适配器

文章目录 一、简介二、适配器模式基础1. 适配器模式定义与分类2. 适配器模式的作用与优势3.UML图 三、适配器模式实现方式1. 类适配器模式2. 对象适配器模式3.类适配器模式和对象适配器模式对比 四、适配器模式应用场景1. 继承与接口的适配2. 跨平台适配 五、适配器模式与其他设…

滑动窗口和双指针

滑动窗口和双指针 一、循环不变量1.1 定义1.2 总结 二、使用循环不变量写对代码2.1 注意2.2 总结 三、滑动窗口3.1 固定长度的滑动窗口&#xff08;同向交替移动的两个变量&#xff09;3.2 不定长度的滑动窗口3.2.1 定义3.2.2 总结 3.3 计数问题3.3.1 标准3.3.2 总结 3.4 使用数…

JavaScript【转】

以下内容转载和参考自&#xff1a;w3school的JavaScript学习内容&#xff0c;HTML JavaScript。 JavaScript 使 HTML 页面更具动态性和交互性&#xff0c;前面我们都是在代码中一开始就将元素的值、属性、style样式写死&#xff0c;使用JavaScript 的话就可以对这些内容动态的更…

ChatGPT癌症治疗“困难重重”,真假混讲难辨真假,准确有待提高

近年来&#xff0c;人工智能在医疗领域的应用逐渐增多&#xff0c;其中自然语言处理模型如ChatGPT在提供医疗建议和信息方面引起了广泛关注。然而&#xff0c;最新的研究表明&#xff0c;尽管ChatGPT在许多领域取得了成功&#xff0c;但它在癌症治疗方案上的准确性仍有待提高。…

简易虚拟培训系统-UI控件的应用1

目录 前言 UI结构总体介绍 建立初步的系统UI结构 Image控件 前言 前面的文章介绍了关于Oculus设备与UI控件的关联&#xff0c;从本文开始采用小示例的方式介绍基本的UI控件在系统中的基本作用&#xff08;仅介绍“基本作用”&#xff0c;详细的API教程可参考官方文档&#x…

中级深入--day15

案例&#xff1a;使用BeautifuSoup4的爬虫 我们以腾讯社招页面来做演示&#xff1a;搜索 | 腾讯招聘 使用BeautifuSoup4解析器&#xff0c;将招聘网页上的职位名称、职位类别、招聘人数、工作地点、发布时间&#xff0c;以及每个职位详情的点击链接存储出来。 # bs4_tencent.p…

VScode远程连接主机

一、前期准备 1、Windows安装VSCode&#xff1b; 2、在VSCode中安装PHP Debug插件&#xff1b; 3、安装好Docker 4、在容器中安装Xdebug ①写一个展现phpinfo的php文件 <?php phpinfo(); ?>②在浏览器上打开该文件 ③复制所有信息丢到Xdebug: Installation instr…

使用php实现微信登录其实并不难,可以简单地分为三步进行

使用php实现微信登录其实并不难&#xff0c;可以简单地分为三步进行。 第一步&#xff1a;用户同意授权&#xff0c;获取code //微信登录public function wxlogin(){$appid "";$secret "";$str"http://***.***.com/getToken";$redirect_uriu…

【Java核心知识】ThreadLocal相关知识

ThreadLocal 什么是ThreadLocal ThreadLoacal类可以为每个线程保存一份独有的变量&#xff0c;该变量对于每个线程都是独占的。实现原理为每个Thread类中包含一个ThreadHashMap&#xff0c;key为变量的name&#xff0c;value为变量的值。 在日常使用中&#xff0c;我们可以通…

【React学习】—React中的事件绑定(八)

【React学习】—React中的事件绑定&#xff08;八&#xff09; 一、原生JS <body><button id"btn1">按钮1</button><button id"btn2">按钮2</button><button onclick"demo()">按钮3</button><scr…

Git——Windows平台创建gitee私有仓库详解

目录 1. 安装git 2. gitbash配置 2.1 设置 2.2 生成key 2.3 项目管理 2.3.1 本地新建 2.3.2 clone远程仓库的工程到本地改文件 1. 安装git 默认安装。 2. gitbash配置 2.1 设置 打开gitbash&#xff0c;设置用户名和邮箱&#xff1a; git config --global user.name …

浅析Linux系统I/O模型

文章目录 概述阻塞式I/O模型非阻塞式I/O模型I/O多路复用模型信号驱动式I/O模型异步I/O模型相关参考 概述 在操作系统中&#xff0c;I/O类操作是相对慢速的&#xff0c;应用发起一个I/O操作&#xff0c;需要等待I/O资源就绪后&#xff0c;才能继续后面的处理。这种简单的请求-响…

详解MES中的四大现场执行管理模式

导 读 ( 文/ 3426 ) 制造业是全球经济中至关重要的一部分&#xff0c;随着市场竞争的加剧和客户需求的多样化&#xff0c;企业需要寻找合适的生产方式来提高生产效率、降低成本并保证产品质量。在这个背景下&#xff0c;制造执行系统&#xff08;MES&#xff09;作为连接管理层…

前端基础3——JavaScript基础用法

文章目录 一、基本使用1.1 内部方式1.2 外部导入方式1.3 css标签调用js脚本&#xff08;触发事件&#xff09; 二、Windows对象2.1 对象属性2.2 对象方法 三、数据类型3.1 字符串处理3.2 数组处理3.3 对象处理 四、流程控制4.1 操作符4.2 if判断语句4.3 for循环语句4.4 continu…

2018ECCV Can 3D Pose be Learned from2D Projections Alone?

摘要 在计算机视觉中&#xff0c;从单个图像的三维姿态估计是一个具有挑战性的任务。我们提出了一种弱监督的方法来估计3D姿态点&#xff0c;仅给出2D姿态地标。我们的方法不需要2D和3D点之间的对应关系来建立明确的3D先验。我们利用一个对抗性的框架&#xff0c;强加在3D结构…

【链表OJ 10】环形链表Ⅱ(求入环节点)

前言: &#x1f4a5;&#x1f388;个人主页:​​​​​​Dream_Chaser&#xff5e; &#x1f388;&#x1f4a5; ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 leetcode142. 环形链表 II 1.问题描述 2.代码思路 3.问题分析 leetcode142. 环形链…

安全开发-JS应用NodeJS指南原型链污染Express框架功能实现审计WebPack打包器第三方库JQuery安装使用安全检测

文章内容 环境搭建-NodeJS-解析安装&库安装安全问题-NodeJS-注入&RCE&原型链案例分析-NodeJS-CTF题目&源码审计打包器-WebPack-使用&安全第三方库-JQuery-使用&安全 环境搭建-NodeJS-解析安装&库安装 Node.js是运行在服务端的JavaScript 文档参考…

Java 大厂八股文面试专题-设计模式 工厂方法模式、策略模式、责任链模式

面试专题-设计模式 前言 在平时的开发中&#xff0c;涉及到设计模式的有两块内容&#xff0c;第一个是我们平时使用的框架&#xff08;比如spring、mybatis等&#xff09;&#xff0c;第二个是我们自己开发业务使用的设计模式。 面试官一般比较关心的是你在开发过程中&#xff…

javaee之黑马乐优商城2

简单分析一下商品分类表的结构 先来说一下分类表与品牌表之间的关系 再来说一下分类表和品牌表与商品表之间的关系 面我们要开始就要创建sql语句了嘛&#xff0c;这里我们分析一下字段 用到的数据库是heima->tb_category这个表 现在去数据库里面创建好这张表 下面我们再去编…

剑指 Offer 44. 数字序列中某一位的数字(中等)

题目&#xff1a; class Solution { //本题单纯找规律&#xff0c;要注意通过n%digits来判断有几个位数为digits的数 public:int findNthDigit(int n) {long base 9, digits 1; //digits代表位数while(n-base*digits>0){ //该循环是为了确定目标数字所在…