基础数据结构之堆栈

堆栈的定义、入栈、出栈、查询栈顶

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

// 定义栈节点结构体
struct StackNode;

struct StackNode {
    DataType data;              // 节点数据
    struct StackNode* next;     // 指向下一个节点的指针
};

// 定义栈结构体
struct Stack {
    struct StackNode* head;     // 栈顶节点指针
    int size;                   // 栈的大小（元素数量）
};

// 将元素压入栈中
void StackPushStack(struct Stack* stk, DataType dt) {
    struct StackNode* vtx = (struct StackNode*)malloc(sizeof(struct StackNode));  // 创建新节点
    vtx->next = stk->head;       // 新节点的下一个节点指针指向栈顶节点
    vtx->data = dt;              // 设置新节点的数据为传入的数据
    stk->head = vtx;             // 更新栈顶节点为新节点
    ++stk->size;                 // 增加栈的大小
}

// 将栈顶元素弹出栈
void StackPopStack(struct Stack* stk) {
    struct StackNode* temp = stk->head;   // 临时存储栈顶节点指针
    stk->head = temp->next;               // 更新栈顶节点为下一个节点
    free(temp);                           // 释放原栈顶节点的内存
    --stk->size;                          // 减少栈的大小
}

// 获取栈顶元素的值
DataType StackGetTop(struct Stack* stk) {
    return stk->head->data;     // 返回栈顶节点的数据
}

int main() {
    // 创建一个栈
    struct Stack myStack;
    myStack.head = NULL;    // 初始化栈顶节点指针为空
    myStack.size = 0;       // 初始化栈的大小为0

    // 将元素压入栈中
    StackPushStack(&myStack, 10);
    StackPushStack(&myStack, 20);
    StackPushStack(&myStack, 30);

    // 获取栈顶元素并打印
    DataType top = StackGetTop(&myStack);
    printf("Top element: %d\n", top);

    // 从栈中弹出一个元素
    StackPopStack(&myStack);

    // 获取新的栈顶元素并打印
    top = StackGetTop(&myStack);
    printf("Top element after popping: %d\n", top);

    return 0;
}

例题1

括号的最大嵌套深度

提示

如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：

  • 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
  • 字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
  • 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。

类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：

  • depth("") = 0
  • depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
  • depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
  • depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串

例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。

给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。

示例 1：

输入：s = "(1+(2*3)+((8)/4))+1"
输出：3
解释：数字 8 在嵌套的 3 层括号中。

示例 2：

输入：s = "(1)+((2))+(((3)))"
输出：3

提示：

  • 1 <= s.length <= 100
  • s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
  • 题目数据保证括号表达式 s 是 有效的括号表达式

 

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    char* stack;
    int top;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->stack = (char*)malloc(capacity * sizeof(char));
    stack->top = -1;
    return stack;
}

void push(Stack* stack, char element) {
    stack->stack[++stack->top] = element;
}

char pop(Stack* stack) {
    return stack->stack[stack->top--];
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}                                                                                                    
int maxDepth(char* s) {
    int maxDepth = 0;
    int currentDepth = 0;
    int i = 0;
    Stack* stack = createStack(100);
    while (s[i] != '\0') {
        if (s[i] == '(') {
            push(stack, s[i]);
            currentDepth++;
            if (currentDepth > maxDepth) {
                maxDepth = currentDepth;
            }
        } else if (s[i] == ')') {
            pop(stack);
            currentDepth--;
        }
        i++;
    }
    return maxDepth;
}
int main() {
    char s[] = "(1+(2*3)+((8)/4))+1";
    int depth = maxDepth(s);
    printf("The maximum nesting depth is: %d\n", depth);
    return 0;
}

例题2

回文链表

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

输入: head = [1,2]
输出: false

提示：

  • 链表 L 的长度范围为 [1, 105]
  • 0 <= node.val <= 9
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

// 创建一个堆栈结构
struct Stack {
    int* array;
    int top;
    int capacity;
};

// 初始化堆栈
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->array = (int*)malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

// 判断堆栈是否为空
bool isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

// 判断堆栈是否已满
bool isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// 将元素压入堆栈
void push(struct Stack* stack, int value) {
    if (isFull(stack)) {
        return;
    }
    stack->array[++stack->top] = value;
}

// 从堆栈中弹出元素
int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        return -1;
    }
    return stack->array[stack->top--];
}

// 判断链表是否为回文链表
bool isPalindrome(struct ListNode* head) {
    if (!head || !head->next) {
        return true;
    }
    
    // 统计链表的长度
    int length = 0;
    struct ListNode* curr = head;
    while (curr) {
        length++;
        curr = curr->next;
    }
    
    // 将链表前半部分的值压入堆栈
    struct Stack* stack = createStack(length / 2);
    curr = head;
    int i = 0; 
    for (i = 0; i < length / 2; i++) {
        push(stack, curr->val);
        curr = curr->next;
    }
    
    // 如果链表长度为奇数，跳过中间节点
    if (length % 2 == 1) {
        curr = curr->next;
    }
    
    // 比较链表后半部分的值与堆栈中弹出的值是否相等
    while (curr) {
        int value = pop(stack);
        if (value != curr->val) {
            return false;
        }
        curr = curr->next;
    }
    
    return true;
}

int main() {
    // 创建链表 [1, 2, 3, 2, 1]
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->val = 2;
    head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->val = 3;
    head->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->next->val = 2;
    head->next->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->next->next->val = 1;
    head->next->next->next->next->next = NULL;
    
    bool isPalin = isPalindrome(head);
    if (isPalin) {
        printf("The linked list is a palindrome.\n");
    } else {
        printf("The linked list is not a palindrome.\n");
    }
    
    // 释放链表的内存
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* temp = curr;
        curr = curr->next;
        free(temp);
    }
    
    return 0;
}

例题3

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

// 创建一个堆栈结构
struct Stack {
    int* array;
    int top;
    int capacity;
};

// 初始化堆栈
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->array = (int*)malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}
// 判断堆栈是否为空
bool isEmpty(struct Stack* stack) {
    return stack->top == -1;
}
// 判断堆栈是否已满
bool isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}
// 将元素压入堆栈
void push(struct Stack* stack, int value) {
    if (isFull(stack)) {
        return;
    }
    stack->array[++stack->top] = value;
}
// 从堆栈中弹出元素
int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        return -1;
    }
    return stack->array[stack->top--];
}
// 反转链表
struct ListNode* reverseList(struct ListNode* head) {
	if (!head || !head->next) {
        return head;
    }
	 // 统计链表的长度
    int length = 0;
    struct ListNode* curr = head;
    while (curr) {
        length++;
        curr = curr->next;
    }
    // 将链表的值压入堆栈
    struct Stack* stack = createStack(length);
    curr = head;
    int i = 0; 
    for (i = 0; i < length; i++) {
        push(stack, curr->val);
        curr = curr->next;
    }
    // 将堆栈弹出的值给链表 
    curr = head;
    while (curr) {
        curr->val = pop(stack);
        curr = curr->next;
    }
	return head;
} 

int main() {
    // 创建链表 [1, 2, 3, 4, 5]
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->val = 2;
    head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->val = 3;
    head->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->next->val = 4;
    head->next->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->next->next->val = 5;
    head->next->next->next->next->next = NULL;
    
    head=reverseList(head);
    int i=0;
    for(i=0;i<5;i++)
    {
    	printf("%d ",head->val);
    	head=head->next;
	}
    // 释放链表的内存
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* temp = curr;
        curr = curr->next;
        free(temp);
    }
    
    return 0;
}

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

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

相关文章

Python基础知识：整理12 JSON数据格式的转换

Python基础知识：整理12 JSON数据格式的转换

首先导入python中的内置包json import json 1 准备一个列表&#xff0c;列表内每个元素都是字典&#xff0c;将其转换为JSON 使用json.dumps()方法 data [{"name": "John", "age": 30}, {"name": "Jane", "age":…
阅读更多...
NAND系统性能提升常见方案

NAND系统性能提升常见方案

随着NAND的发展&#xff0c;针对NAND系统性能提升&#xff0c;业内目前主要的做法有以下几种方案&#xff1a; 1.提升总线频率和优化AC时序&#xff1a; 提高NAND闪存接口的工作频率可以显著加快数据传输速度。通过不断改进工艺和技术&#xff0c;缩短了信号稳定时间、降低了延…
阅读更多...
逆向分析爬取网页动态

逆向分析爬取网页动态

本例子以爬取人民邮电出版社网页新书的信息为例 由于页面是动态的&#xff0c;信息会不停地更新&#xff0c;所以不同时间的爬取结果会不同。
阅读更多...
Selenium+Remote WebDriver+python脚本访问示例

Selenium+Remote WebDriver+python脚本访问示例

一、环境要求&#xff1a; 1、selenium-server安装&#xff0c;下载地址&#xff1a;Release Selenium 4.16 SeleniumHQ/selenium GitHub 2、python3及pycharm 二、启动selenium-server 下载selenium-server之后&#xff0c;解压到D:\selenium-server目录&#xff0c;然后…
阅读更多...
error: undefined reference to ‘cv::imread(std::__ndk1::basic_string＜char

error: undefined reference to ‘cv::imread(std::__ndk1::basic_string＜char

使用android studio编译项目时&#xff0c;由于用到了 cv::imread&#xff08;&#xff09;函数&#xff0c;编译时却报错找不到该函数的定义。 cv::imread一般是在highgui.hpp中定义&#xff0c;因此我加上了该头文件&#xff1a; #include “opencv2/highgui/highgui.hpp” 但…
阅读更多...
设计模式之六大设计原则

设计模式之六大设计原则

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…
阅读更多...
Hive 数据同步

Hive 数据同步

一、需求 同步集团的数据到断直连环境。 二、思路 三、同步数据&#xff08;方案&#xff09; 1、环境&#xff1a;断直连模拟环境 2、操作机器&#xff1a;ETL 机器 XX.14.36.216 3、工作路径&#xff1a;cd /usr/local/fqlhadoop/hadoop/bin 4、执行命令&#xff1a; 命令…
阅读更多...
GIS真的是天坑专业吗？

GIS真的是天坑专业吗？

是&#xff0c;也不是。 首先说是&#xff0c;GIS到底坑在哪&#xff1f; 1、专业定位不清晰&#xff0c;具有很强的误导性 听过很多学生抱怨&#xff0c;关于GIS专业&#xff0c;大家觉得最坑的地方&#xff0c;在于一开始在选专业的时候&#xff0c;以为这个专业跟计算机专…
阅读更多...
如何判断 vite 的运行环境是开发模式还是生产模式 production？ development？

如何判断 vite 的运行环境是开发模式还是生产模式 production？ development？

如何判断 vite 的运行环境是开发模式还是生产模式 production&#xff1f; development&#xff1f; vite 有两种获取当前运行环境模式的方法&#xff1a; 官方说明&#xff1a; 完整说明地址&#xff1a; https://cn.vitejs.dev/guide/env-and-mode.html#node-env-and-modes…
阅读更多...
【LangChain学习之旅】—（6） 提示工程（下）：用思维链和思维树提升模型思考质量

【LangChain学习之旅】—（6） 提示工程（下）：用思维链和思维树提升模型思考质量

【LangChain学习之旅】—&#xff08;6&#xff09; 提示工程&#xff08;下&#xff09;&#xff1a;用思维链和思维树提升模型思考质量 什么是 Chain of ThoughtFew-Shot CoTZero-Shot CoTChain of Thought 实战CoT 的模板设计程序的完整框架Tree of Thought总结 Reference&a…
阅读更多...
一阶低通滤波器

一阶低通滤波器

一阶低通滤波器 X为输入&#xff0c;Y为滤波后得到的输出值&#xff1b;本次的输出结果主要取决于上次的滤波输出值&#xff0c;其中a是和滤波效果有关的一个参数&#xff0c;称为滤波系数&#xff1b;它决定新采样值在本次滤波结果中所占的权重&#xff1b; 滤波系数a越小&a…
阅读更多...
AI绘画软件Stable Diffusion模型/Lora/VAE文件存放位置

AI绘画软件Stable Diffusion模型/Lora/VAE文件存放位置

型下载说明&#xff08;下载模型后输入对应参数即可生成&#xff09; 建议直接去civitai.com找模型&#xff0c;如果无法找到可以在幕后模型区找也可以去&#xff0c; 下载好后放入对应的文件夹。进入127.0.0.1:7680 左上角刷新即可看到新的模型。 模型种类 大模型 大模型特…
阅读更多...
揭秘人工智能：探索智慧未来

揭秘人工智能：探索智慧未来

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;数据结构、网络奇遇记 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 什么是人工智能?二. 人工智能的关键技术2.1 机器学习2.2 深度学习2.1 计算机…
阅读更多...
【一文详解】知识分享:(C#开发学习快速入门)

【一文详解】知识分享:(C#开发学习快速入门)

面向对象(OOP) c语言是面向过程。 c是面向过程面向对象。 c#是纯粹的面向对象: 核心思想是以人的思维习惯来分析和解决问题。万物皆对象。 面向对象开发步骤: 分析对象 特征行为关系(对象关系/类关系) 写代码: 特征–>成员变量 方法–>成员方法 实例化–具体对象 …
阅读更多...
一本数学教材严谨和通俗哪个更重要？

一本数学教材严谨和通俗哪个更重要？

一本教材也许无法同时兼顾严谨和通俗&#xff0c;而且在不同的场景下&#xff0c;严谨和通俗的重要性也不尽相同&#xff1a; 在正式的学术场合&#xff0c;严谨当然重要&#xff0c;一些不严谨的教材可能无法通过审校&#xff0c;在读者存在疑问的时候&#xff0c;也不一定能给…
阅读更多...
揭露欧拉骗局4.“Σ1/n²=π²/6”里的猫腻

揭露欧拉骗局4.“Σ1/n²=π²/6”里的猫腻

自然数平方倒数求和Σ1/n是一个并不复杂的问题&#xff0c;但它困扰了欧洲大陆整整90年&#xff0c;在欧系数学里它被称为“巴塞尔级数”。 解决巴塞尔级数让欧拉一战成名&#xff0c;然而欧拉采用的方法对数学这门学问是严重的侮辱。数学是工具学科&#xff0c;数学的宗旨是化…
阅读更多...
apipost 前端使用云端mock实现自定义返回

apipost 前端使用云端mock实现自定义返回

目录 一.新建接口 1.选择mock环境 2.设置接口路径&#xff0c;以及相关参数 3.自定应响应示例 4.开启云端mock,设置相应条件 5.更改接口类型post,保存设置&#xff0c;发送请求 6.测试 一.新建接口 1.选择mock环境 如图&#xff0c;更改环境 2.设置接口路径&#xff0c…
阅读更多...
68.网游逆向分析与插件开发-角色数据的获取-利用蓝量属性分析角色数据基址

68.网游逆向分析与插件开发-角色数据的获取-利用蓝量属性分析角色数据基址

内容参考于&#xff1a;易道云信息技术研究院VIP课 上一个内容&#xff1a;67.网游逆向分析与插件开发-角色数据的获取-分析角色数据基址-CSDN博客 然后分析任何一个东西&#xff0c;逆向分析的本质就是找东西的意思&#xff0c;找东西核心的观念是内存里得有&#xff0c;就是…
阅读更多...
内 存 取 证

内 存 取 证

1.用户密码 从内存中获取到用户admin的密码并且破解密码&#xff0c;以Flag{admin,password}形式提交(密码为6位)&#xff1b; 1&#xff09;查看帮助 -h ./volatility_2.6_lin64_standalone -h 2&#xff09;获取内存镜像文件的信息 imageinfo ./volatility_2.6_lin64_stand…
阅读更多...
【数据库原理】（21）查询处理过程

【数据库原理】（21）查询处理过程

关系型数据库系统的查询处理流程是数据库性能的关键&#xff0c;该流程涉及到将用户的查询请求转化成有效的数据检索操作。通常可以分为四个阶段:查询分析、查询处理、查询优化和查询执行&#xff0c;如图所示。 第一步&#xff1a;查询分析 这个阶段是整个查询处理的起点。数…
阅读更多...
最新文章

Copyright @ 2022~2023