Lesson4--栈和队列

【本节目标】

  • 1.
  • 2.队列
  • 3.栈和队列面试题

1.栈

1.1栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。 栈中的数据元素遵守后进先出 LIFO Last In First Out )的原则。
压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶
出栈:栈的删除操作叫做出栈。 出数据也在栈顶

 1.2栈的实现

        栈的实现一般可以使用数组或者链表实现 ,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。

// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
 STDataType* _a;
 int _top; // 栈顶
 int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps); 
// 入栈
void StackPush(Stack* ps, STDataType data); 
// 出栈
void StackPop(Stack* ps); 
// 获取栈顶元素
STDataType StackTop(Stack* ps); 
// 获取栈中有效元素个数
int StackSize(Stack* ps); 
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps); 
// 销毁栈
void StackDestroy(Stack* ps);

*1.2.1具体代码

stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int	STDatatype;
struct stack
{
	STDatatype* arr;
	int top;
	int capacity;
};
typedef struct stack ST;

void STInit(ST* ps);//初始化
void STDestory(ST* ps);//销毁
void STPush(ST* ps, STDatatype x);//压栈
void STPop(ST* ps);//出栈;
STDatatype STTop(ST* ps);//栈顶的数
int STSize(ST* ps);//栈的大小
bool STEmpty(ST* ps);

stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;

}

void STDestory(ST* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STPush(ST* ps, STDatatype x)
{
	assert(ps);
	//满了扩容
	if (ps->top == ps->capacity)
	 {
		int newcapacity;
		if (ps->capacity == 0)
		{                                                   
			newcapacity = 4;
		}
		else 
		{

			 newcapacity = 2 * ps->capacity;
			
		}
		STDatatype* temp = (STDatatype*)realloc(ps->arr, newcapacity * sizeof(STDatatype));
		if (temp == NULL)
		{
			perror("realloc fail!");
			return;
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}

 	ps->arr[ps->top] = x;
	ps->top++;
	
	
}
void STPop(ST* ps)
{
	assert(ps);
	ps->top--;
}
STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->arr[ps->top - 1];
}
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	while (!STEmpty(&s))
	{
		int top = STTop(&s);
		printf("%d ", top);
		STPop(&s);
	}

}

这个就是 后进先出的意思

但是也不是绝对的

2.队列  

2.1队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为 队尾 出队列:进行删除操作的一端称为 队头

2.2队列的实现 

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数 组头上出数据,效率会比较低。
// 链式结构:表示队列
typedef struct QListNode
{ 
 struct QListNode* _pNext; 
 QDataType _data; 
}QNode; 
// 队列的结构
typedef struct Queue
{ 
 QNode* _front; 
 QNode* _rear; 
}Queue; 
// 初始化队列
void QueueInit(Queue* q); 
// 队尾入队列
void QueuePush(Queue* q, QDataType data); 
// 队头出队列
void QueuePop(Queue* q); 
// 获取队列头部元素
QDataType QueueFront(Queue* q); 
// 获取队列队尾元素
QDataType QueueBack(Queue* q); 
// 获取队列中有效元素个数
int QueueSize(Queue* q); 
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q); 
// 销毁队列
void QueueDestroy(Queue* q);

*2.2.1队列具体代码的实现

queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QueueData;
struct QueueNode
{
	QueueData val;
	struct QueueNode* next;
};
typedef struct QueueNode QNode;
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Que;
void QueueInit(Que* pq);//队列初始化
void QueueDestroy(Que* pq);//队列销毁

void QueuePush(Que* pq,QueueData x);//入队列
void QueuePop(Que* pq);//出队列

QueueData QueueBack(Que* pq);
QueueData QueueFront(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);

 queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
void QueueInit(Que* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
void QueueDestroy(Que* pq)
{
	QNode* pcur = pq->phead;
	while (pcur)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;	
}

void QueuePush(Que* pq,QueueData x)
{
	assert(pq);
	QNode* newnode = (Que*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail)
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->phead = pq->ptail = newnode;
	}
	pq->size++;
}
void QueuePop(Que* pq)
{
	assert(pq->phead != NULL);

	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead =pq->ptail= NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead); 
		pq->phead = next;
	}
	pq->size--;
}

QueueData QueueFront(Que* pq)
{
	assert(pq!=NULL);

	assert(pq->phead != NULL);
	return pq->phead->val;
}
QueueData QueueBack(Que* pq)
{
	assert(pq!=NULL);

	assert(pq->ptail != NULL);
	return pq->ptail->val;
}
bool QueueEmpty(Que* pq)
{
	return pq->phead == NULL;
}
int QueueSize(Que* pq)
{
	assert(pq);
	return pq->size;

}

 注意看栈和队列是相对的

3.栈和队列面试题  

1. 括号匹配问题。 20. 有效的括号 - 力扣(LeetCode)
2. 用队列实现栈。 225. 用队列实现栈 - 力扣(LeetCode)
3. 用栈实现队列。 232. 用栈实现队列 - 力扣(LeetCode)
4. 设计循环队列。 622. 设计循环队列 - 力扣(LeetCode)

4.概念选择题  

选择题
1. 一个栈的初始
次出栈,则元素出
栈的顺序是(
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
2. 若进栈序列为
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
3. 循环队列的存储空间为 Q(1:100) ,初始状态为 front=rear=100 。经过一系列正常的入队与退队操作
后, front=rear=99 ,则循环队列中的元素个数为( )
A 1
B 2
C 99
D 0 或者 100
4. 以下 ( ) 不是队列的基本运算?
A 从队尾插入一个新元素
B 从队列中删除第 i 个元素
C 判断一个队列是否为空
D 读取队头元素的值
5. 现有一循环队列,其队头指针为 front ,队尾指针为 rear ;循环队列长度为 N 。其队内有效长度为? ( 假设
队头不存放数据 )
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)

答案

1.B
2.C
3.D
4.B
5.B

 

 

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

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

相关文章

vue快速入门(三十五)组件通信-父传子

注释很详细&#xff0c;直接上代码 上一篇 新增内容 父组件传值子组件接收父组件传来的数据 源码 App.vue <template><div id"app"><!-- :item"item"为将item的值传递给MyTest组件 --><MyTest v-for"item in roles" :key&q…

【双曲几何】圆盘上的三角形概念

目录 一、说明二、对偶三角形概念2.1 反演关系2.2 对偶关系2.3 找出三角形的对偶三角形 三、正交三角形概念3.1 通过对偶三角形&#xff0c;找到垂心3.2 正交三角形的概念3.3 中心射影点的概念 四、后记 一、说明 本文对双曲空间的三角形进行分析&#xff0c;本篇首先给出&am…

(vue)el-select选择框加全选/清空/反选

(vue)el-select选择框加全选/清空/反选 <el-form-item label"批次"><el-selectv-model"formInline.processBatch"multiplecollapse-tagsfilterableplaceholder"请选择"style"width: 250px"no-data-text"请先选择企业、日…

基于docker的开发者集成环境

docker-compose一键部署开发者环境。 常见的中间件&#xff1a;nginx, mysql, redis, mongo, rabbitmq, nacos, rocketmq, zookeeper等。 GIthub项目地址 1. 下载项目&#xff1a;git clone https://github.com/xhga/docker-develop-env.git 2. 进入文件夹&#xff1a;cd d…

实例分割——苹果数据集

一、重要性及意义 重要性&#xff1a; 提升农业生产效率&#xff1a;通过自动化检测和分割技术&#xff0c;可以快速准确地识别出图像中的苹果&#xff0c;进而实现自动化的采摘、计数和品质评估。这极大地提高了农业生产的效率&#xff0c;减少了人工劳动成本。 优化资源配置…

【网站项目】高校毕业论文管理系统小程序

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

力扣:LCR 022. 环形链表 II

力扣&#xff1a;LCR 022. 环形链表 II 给定一个链表&#xff0c;返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环&#xff0c;则返回 null。 为了表示给定链表中的环&#xff0c;我们使用整数 pos 来表示链…

为了机器学习量化策略,我标注了两万条数据

题图&#xff1a;芝加哥大学海德公园。芝大是经济学重镇&#xff0c;其学者开创了著名的芝加哥经济学派&#xff0c;共产生了 100 位诺奖、10 位菲尔兹奖、4 位图灵奖。今天量化人追逐的 Alpha&#xff0c; 最早就来自于 Michael Jessen 在芝大时的博士论文。 很多人对基于机器…

Git - 在PyCharm/Idea中集成使用Git

文章目录 Git - 在PyCharm/Idea中集成使用Git1.新建GitHub仓库2.将仓库与项目绑定3.在PyCharm中使用Git4.新建Gitee仓库5.将仓库与项目绑定6.在IDEA中使用Git Git - 在PyCharm/Idea中集成使用Git 本文详细讲解了如何在 PyCharm 或 Idea 中配置 Gitee 或 GitHub 仓库&#xff0…

稀碎从零算法笔记Day53-LeetCode:不同路径 II

稀碎系列有点更不动(更多是自己懈怠了) 题型&#xff1a;矩阵、模拟 链接&#xff1a;63. 不同路径 II - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &…

DQ-DETR: DETR WITH DYNAMIC QUERY FOR TINY OBJECTDETECTION 学习笔记

论文地址&#xff1a;https://arxiv.org/pdf/2404.03507.pdf 此DQ-DETR与IDEA提出的同名&#xff0c;该文主要集中于小目标的检测 尽管之前的类似DETR的方法在通用目标检测中取得了成功&#xff0c;但在小目标检测方面仍然具有挑战性&#xff0c;因为目标 Query 的位置信息并未…

软件开发中的“左移”是什么意思?

我曾经有过一个经理&#xff0c;在讨论我们的项目时提到&#xff0c;我们需要尽可能地将我们的工作左移。 几个月后&#xff0c;在一次面试中&#xff0c;面试官问我是否知道“左移”是什么意思。 除非有人没告诉我一个秘密的软件舞蹈&#xff0c;我现在就来告诉你左移是什么…

iview中基于upload源代码组件封装更为完善的上传组件

业务背景 最近接了一个用iview为基础搭建的vue项目&#xff0c;在开需求研讨会议的时候&#xff0c;我个人提了一个柑橘很合理且很常规的建议&#xff0c;upload上传文件支持同时上传多个并且可限制数量。当时想的是这不应该很正常吗&#xff0c;但是尴尬的是&#xff1a;只有…

YZ系列工具之YZ10:VBA_梦幻图像

我给VBA下的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套一部VBA手册&#xff0c;教程分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的…

一分钟成为点灯大师(超简单1行代码-STM32F407的HAL实现按键中断方式点亮LED灯)

一、开发环境 硬件&#xff1a;正点原子探索者 V3 STM32F407 开发板 单片机&#xff1a;STM32F407ZGT6 Keil版本&#xff1a;5.32 STM32CubeMX版本&#xff1a;6.9.2 STM32Cube MCU Packges版本&#xff1a;STM32F4 V1.27.1 使用STM32F407的HAL库实现按键中断方式读取按键…

HCF-Net:用于红外小目标检测的分层上下文融合网络

摘要 红外小目标检测是一项重要的计算机视觉任务&#xff0c;涉及在红外图像中识别和定位微小物体&#xff0c;这些物体通常仅包含几个像素。然而&#xff0c;由于物体尺寸极小以及红外图像中通常复杂的背景&#xff0c;这项任务面临困难。在本文中&#xff0c;我们提出了一种…

【漏洞复现】魔方网表mailupdate.jsp接口存在任意文件上传漏洞

漏洞描述 魔方网表帮助其搭建了支持信创环境的端到端的一站式数据智能填报系统,实现数据收集模板个性化定义,收集任务集中管控,结构化数据存储、分析及呈现等功能。魔方网表mailupdate.jsp接口存在任意文件上传漏洞 免责声明 技术文章仅供参考,任何个人和组织使用网络应当…

Tomcat源码解析——类加载机制

一、类加载器的创建 在之前的Tomcat启动源码中&#xff0c;简单的介绍了Tomcat的四种类加载器&#xff0c;再复习一遍。 类加载器 作用父加载器commonLoader&#xff08;共同类加载器&#xff09;加载$CATALINA_HOME/lib下的类加载器应用类加载器catalinaLoader&#xff08;容器…

CAD小软件diy-读柴油机壳体装配图

读取一个柴油机壳体dxf图纸&#xff0c;一般这种装配体轮廓曲线都是用直线和圆弧拟合的&#xff0c;全部都是显示的白色实现&#xff0c;发现有线段间隙&#xff0c;拖动线段补上间隙。 这个测试放在蓝奏云上面 https://wwf.lanzout.com/ip1Xx1vvhbkh

08 SQL进阶 -- 集合运算 -- 表的连结(JOIN)

1. 连结(JOIN) 前一节我们学习了 UNION和INTERSECT 等集合运算, 这些集合运算的特征就是以行方向为单位进行操作. 通俗地说, 就是进行这些集合运算时, 会导致记录行数的增减。使用 UNION 会增加记录行数,而使用 INTERSECT 或者 EXCEPT 会减少记录行数。 但这些运算不能改变…