栈和队列--数据结构初阶(2)(C/C++)

Ne0inhk

— 7 min read
栈和队列--数据结构初阶(2)(C/C++)

文章目录

前言

这期的话会给大家讲解栈和队列的模拟实现和在STL中栈和队列怎么用的一些知识和习题部分(这部分侧重于理论知识，习题倒还是不难)

理论部分

栈的模拟实现

 typedef int STDataType; typedef struct Stack { STDataType* a;//这里的a想表示的是数组 int top;//表示数组a当前的容量 int capacity; }ST; void STInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->capacity = 4; ps->top = 0; } void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } void STPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2); if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; } int STSize(ST* ps) { assert(ps); return ps->top; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }//拓展:bool里面如果return的是数字的话，会隐式转换 STDataType STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->a[ps->top - 1]; } 注意:这样写的话，此时的栈顶的下标是top-1 
stPush那里一般用ps->top == ps->capacity top那里是还没存元素的 开空间完记得检查是否开辟成功 尽量不要用while(st.top!=0去代替while(!STEmpty（&st）)),数据结构最好封装起来 注意STTop最后那里是ps->a[ps->top-1] 这个代码有个问题:封装时一般要typedef类型，这里搞了但是没去用 (让以后要改类型时只用改一次)

STL中的栈容器

stack容器（栈） 头文件：#include<stack> 创建:stack<T>st;//st是变量名，可以改；T是任意类型的数据 size empty push:进栈 pop:出栈 top:返回栈顶元素，但是不会删除栈顶元素 (先进后出)

队列的模拟实现

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefchar QDatatype;typedefstructQueueNode{structQueueNode* next; QDatatype data;}QNode;typedefstructQueue{ QNode* head; QNode* tail;int size;}Queue;voidQueueInit(Queue* pq);voidQueueDestroy(Queue* pq);voidQueuePush(Queue* pq, QDatatype x);voidQueuePop(Queue* pq);intQueueSize(Queue* pq); bool QueueEmpty(Queue* pq); QDatatype QueueFront(Queue* pq); QDatatype QueueBack(Queue* pq);voidQueueInit(Queue* pq){assert(pq); pq->head = pq->tail =NULL; pq->size =0;}voidQueueDestroy(Queue* pq){assert(pq); QNode* cur = pq->head;while(cur){ QNode* next = cur->next;free(cur); cur = next;} pq->head = pq->tail =NULL; pq->size =0;}voidQueuePush(Queue* pq, QDatatype x){ QNode* newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("malloc fail");return;} newnode->data = x; newnode->next =NULL;if(pq->head ==NULL){assert(pq->tail ==NULL); pq->head = pq->tail = newnode;}else{ pq->tail->next = newnode; pq->tail = newnode;} pq->size++;}voidQueuePop(Queue* pq){assert(pq);assert(pq->head !=NULL);if(pq->head->next ==NULL){free(pq->head); pq->head = pq->tail =NULL;}else{ QNode* next = pq->head->next;free(pq->head); pq->head = next;} pq->size--;}intQueueSize(Queue* pq){assert(pq);return pq->size;} bool QueueEmpty(Queue* pq){assert(pq);return pq->size ==0;} QDatatype QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;} QDatatype QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}
结构体定义那里可以像这样在结构体里面用自己的指针 结构体1里面套结构体2的话，定义结构体1后不用单独手动再为结构体1中的结构体2开辟 跟定义int指针，想变成数组需要malloc区分 注意:assert检查的是结果为0，就会报错

STL中的队列容器

queue(队列)： 头文件:#include<queue> 创建:queue<T>q;//q是变量名，T是任意类型的数据 size empty push pop front:返回队头元素，但不会删除 back:返回队尾元素，但不会删除 不可以用clear来直接清除队列 pop删除的是队头

作业部分

力扣 有效的括号

力扣 有效的括号 注意点:右括号数量不等于左括号这个特殊情况不要忘了 感悟:像这种如果匹配的话要继续走，不匹配的话要干啥的if里面写不匹配的条件会好些 代码实现: typedef struct Stack { char*a; int top; int capacity; } void STInit() { a = (char*)malloc(sizeof(char)*4); capacity = 4; top = 0; } void STPush(char*ps,char x) { assert(ps); if(ps->top == ps->capacity) { a = (char*)malloc(sizeof(char)*ps->capacity*2); capacity*=2; } ps->a[ps->top] = x; ps->top++; } void STPop(char*ps,char x) { assert(ps); ps->top--; } bool isValid(char* s) { struct Stack; &a = &s; } 
if如果判断条件多的话可以像下面这样写，这样写不用续行符 而且if后面只跟一个语句的话，一般跟if写同一行上
在这里插入图片描述
企业中的话，能初始化的尽量还是要初始化一下，竞赛一般不用

力扣 用栈实现队列

题目： 力扣 用栈实现队列 相比用队列实现栈可以优化的地方是:可以有个栈专门入栈，一个栈专门出栈，出栈的空了再把另一个栈倒过来 代码实现: class MyQueue { public: stack<int>q1; stack<int>q2; int count1 = 0; //用q1来存入栈，q2来搞出栈 void push(int x) { q1.push(x); } int pop() { if(!q2.empty()) { int m = q2.top(); q2.pop(); return m; } else{ while(q1.size()) { int k = q1.top(); q2.push(k); q1.pop(); } int n = q2.top(); q2.pop(); return n; } } int peek() { if(!q2.empty()) { return q2.top(); } else { while(q1.size()) { q2.push(q1.top()); q1.pop(); } return q2.top(); } } bool empty() { if(q1.empty()&&q2.empty()) return true; else{ return false; } } };

力扣 设计循环队列

题目:力扣 设计循环队列 这里用链表模拟队列不好(因为要找尾)所以用数组来模拟 想让数组也能循环的话，就要时不时让他对k取模(插入，删除过程中也要) 由这个题引申出来的知识有: 1.malloc了几次，后续也要free几次，虽然说不free也可以通过，但是要是在面试中就是减分项,比如下面这种malloc的方式
在这里插入图片描述


在这里插入图片描述
 代码实现: typedef struct { int*a; int front; int rear; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->front = obj->rear = 0; obj->k = k; obj->a = (int*)malloc(sizeof(int)*(k+1)); return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1) == obj->front; //这里的作用是让rear在数组末时可以返回到0那去以及防止是空 } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->rear] = value; obj->rear = ((++obj->rear))%(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) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); } 
队列和栈都属于线性数据结构 循环队列也是线性数据结构

Read more

微分的本质：从“变化率”到“线性映射”的飞跃 —— 可视化 Python 教程

微分的本质：从“变化率”到“线性映射”的飞跃 —— 可视化 Python 教程

引言 微积分是科学的语言，而微分是其灵魂。从一维导数到流形上的切映射，微分的本质始终是一个线性映射。本文将从这一核心观点出发，系统梳理微积分中一系列重要概念：导数、微分、雅可比矩阵、方向导数、梯度、链式法则、Hessian、切映射、拉回等，揭示它们背后的统一结构。更重要的是，我们将用 Python 代码可视化这些概念，让你直观地看到微分如何“线性化”非线性函数。 本文所有代码均使用 Python 3 + NumPy + Matplotlib 编写，你可以复制到自己的环境中运行，观察图形变化。 1. 一维导数的重新解读——从“数”到“线性映射” 1.1 传统定义的局限 对于一元函数 (f:\mathbb{R}\to\mathbb{R})，导数定义为 [ f’

By Ne0inhk
全网最全！Python、PyTorch、CUDA 与显卡版本对应关系速查表

全网最全！Python、PyTorch、CUDA 与显卡版本对应关系速查表

摘要：搞深度学习，最痛苦的不是写代码，而是配环境！ “为什么我的 PyTorch 认不出显卡？” “新买的显卡装了旧版 CUDA 为什么报错？” 本文提供一份保姆级的版本对应关系速查表，涵盖从 RTX 50 系列 (Blackwell) 到经典老卡的软硬件兼容信息。建议收藏保存，每次配环境前查一下，能省下大量的排坑时间！ 🗺️ 核心逻辑图解 在看表格前，先理清显卡架构的代际关系与 CUDA 版本的强绑定逻辑。 📊 一、PyTorch 版本对照表 (推荐) PyTorch 是目前兼容性最好的框架，只要 CUDA 驱动版本 足高，通常都能向下兼容。对于使用最新硬件（如 RTX 50 系）的用户，请务必使用 2.4 或更高版本。 PyTorch 版本Python 版本推荐 CUDA适用显卡建议2.

By Ne0inhk
【Python基础】（五）Python 库使用全攻略：从标准库到第三方库，让开发效率翻倍

【Python基础】（五）Python 库使用全攻略：从标准库到第三方库，让开发效率翻倍

目录 编辑 前言 一、Python 库的核心认知：什么是库？为什么要用库？ 1.1 库的本质：现成的 "代码工具箱" 1.2 库的分类：标准库 vs 第三方库 （1）标准库：Python 自带的 "基础工具箱" （2）第三方库：全球开发者共建的 "扩展工具箱" 1.3 使用库的核心优势：效率翻倍的关键 二、标准库实战：内置工具的高效用法 2.1 日期时间处理：datetime库（计算日期差、格式转换） 实战需求：计算你和心爱的人认识多少天 扩展用法：

By Ne0inhk
安装 Microsoft Visual C++ Build Tools

安装 Microsoft Visual C++ Build Tools

Microsoft Visual C++ Build Tools下载安装 安装Microsoft Visual C++ Build Tools是为了在windows系统上编译和运行需要C++支持的程序或库（例如某些Python包，Node.js模块等）。 1.下载 打开浏览器，访问 Visual Studio Build Tools下载页面。 在页面上找到“下载”按钮，点击下载 Build Tools for Visual Studio 的安装程序（vs_BuildTools.exe）。 2. 安装 双击下载好的软件（vs_BuildTools.exe）。 点击继续。 等待下载安装。 在安装Visual Studio Build Tools的时候，选择“C++生成工具”

By Ne0inhk