【数据结构】栈与队列面试题(C语言)

我们再用C语言做题时,是比较不方便的,因此我们在用到数据结构中的某些时只能手搓或者Ctrl+cv

我们这里用到的栈或队列来自栈与队列的实现

有效的括号

有效的括号,链接奉上。
在这里插入图片描述

解题思路:

先说结论
因为我们是在讲栈与队列的面试题,故当然此题用栈或者队列做最为合适
但是为什么会想到使用栈与队列呢?
这就要求我们对数据结构具有比较高的熟悉度,看到题目就会想出比较恰当的应对措施,这与我们的做题程度也密不可分

利用的特性,当有左括号出现时,需要压栈,有右括号出现时pop出左括号进行匹配
在这里插入图片描述
解决完最主要的问题就可以逐步探测一些比较不容易被发现的坑点
,我会在代码实现中一步一步带大家深入

代码实现:

bool isValid(char* s) 
{
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            StackPush(&st, *s);
        }
        else
        {
            char tmp = StackTop(&st);
            StackPop(&st);
            if(!(*s == '}' && tmp == '{'
              || *s == ']' && tmp == '['
              || *s == ')' && tmp == '('))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    StackDestroy(&st);
    return true;
}

写完之后我们提交,发现:在这里插入图片描述
这就说明我们应当在加一个判断,当栈中有剩余时,说明数量不匹配

    if(StackSize(&st) > 0)
    {
        StackDestroy(&st);
        return false;
    }

继续提交,发现当只有一个右括号时,因为会top,而栈用又没有元素,所以报错,我们继续加一个判断
在这里插入图片描述
加的位置在while中的else

            if(StackSize(&st) == 0)
            {
                StackDestroy(&st);
                return false;
            }

完整代码:

bool isValid(char* s) 
{
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            StackPush(&st, *s);
        }
        else
        {
            if(StackSize(&st) == 0)
            {
                StackDestroy(&st);
                return false;
            }
            char tmp = StackTop(&st);
            StackPop(&st);
            if(!(*s == '}' && tmp == '{'
             || *s == ']' && tmp == '['
             || *s == ')' && tmp == '('))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    if(StackSize(&st) > 0)
    {
        StackDestroy(&st);
        return false;
    }
    StackDestroy(&st);
    return true;
}

用队列实现栈

在这里插入图片描述
用队列实现栈,链接奉上

解题思路:

在这里插入图片描述

代码实现:

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() 
{
    MyStack* head = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&head->q1);
    QueueInit(&head->q2);
    return head;
}

void myStackPush(MyStack* obj, int x) 
{
    Queue empty = obj->q1;
    if(!QueueEmpty(&empty))
        QueuePush(&obj->q1, x);
    else
        QueuePush(&obj->q2, x);
}

int myStackPop(MyStack* obj) 
{
    Queue* emptyq = &obj->q1;
    Queue* nonemptyq = &obj->q2;
    if(!QueueEmpty(emptyq))
    {
        emptyq = &obj->q2;
        nonemptyq = &obj->q1;
    }
    
    
    while(QueueSize(nonemptyq) > 1)
    {
        QueuePush(emptyq, QueueFront(nonemptyq));
        QueuePop(nonemptyq);    
    }

    int tmp = QueueFront(nonemptyq);
    QueuePop(nonemptyq);
    return tmp;
}

int myStackTop(MyStack* obj) {
    Queue* emptyq = &obj->q1;
    Queue* nonemptyq = &obj->q2;
    if(!QueueEmpty(emptyq))
    {
        emptyq = &obj->q2;
        nonemptyq = &obj->q1;
    }
    return QueueBack(nonemptyq);
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
}

用栈实现队列

在这里插入图片描述

用栈实现队列

解题思路:

与上一题类似,可以将两个栈来回导,最终实现

代码实现:

typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* ret = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&ret->s1);
    StackInit(&ret->s2);
    return ret;
}

void myQueuePush(MyQueue* obj, int x) {
    if(!(StackEmpty(&obj->s1)))
    {
        StackPush(&obj->s2, x);
    }
    else
    {
        StackPush(&obj->s1, x);
    }
}

int myQueuePop(MyQueue* obj) {
    MyQueue* emptys = &obj->s1; 
    MyQueue* nonemptys = &obj->s2; 

    if(!StackEmpty(&obj->s1))
    {
        emptys = &obj->s2; 
        nonemptys = &obj->s1; 
    }
    
    while(StackSize(nonemptys) > 1)
    {
        StackPush(emptys, StackTop(nonemptys));
        StackPop(nonemptys);
    }
    int ret = StackTop(nonemptys);
    StackPop(nonemptys);

    while(StackSize(emptys))
    {
        StackPush(nonemptys, StackTop(emptys));
        StackPop(emptys);
    }

    return ret;
}

int myQueuePeek(MyQueue* obj) {
    MyQueue* emptys = &obj->s1; 
    MyQueue* nonemptys = &obj->s2; 

    if(!StackEmpty(&obj->s1))
    {
        emptys = &obj->s2; 
        nonemptys = &obj->s1; 
    }
    
    while(StackSize(nonemptys) > 1)
    {
        StackPush(emptys, StackTop(nonemptys));
        StackPop(nonemptys);
    }
    int ret = StackTop(nonemptys);
    StackPush(emptys, StackTop(nonemptys));
    StackPop(nonemptys);

    while(StackSize(emptys))
    {
        StackPush(nonemptys, StackTop(emptys));
        StackPop(emptys);
    }

    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s1);
    
    free(obj);
}

遇到问题可以及时与博主沟通,定知无不言,言无不尽

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

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

相关文章

[C国演义] 哈希的使用和开闭散列的模拟实现

哈希的使用和开闭散列的模拟实现 1. 使用1.1 unordered_map的接口1.2 unordered_set的接口 2. 哈希底层2.1 概念2.2 解决哈希冲突 3. 实现3.1 开放寻址法3.2 拉链法 1. 使用 1.1 unordered_map的接口 构造 void test1() {// 空的unordered_map对象unordered_map<int, in…

【Proteus仿真】【Arduino单片机】LM35温度计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用PCF8574、LCD1602液晶、LM35传感器等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示传感器检测温度。 二、软件设计 /* 作者&a…

Jmeter 吞吐量Per User作用

第一点&#xff1a;Per User仅在Total Execution时生效 第二点&#xff1a;Per User 选中后 聚合报告中将统计的的样本数将变成线程组配置的线程数*吞吐量控制器配置的执行样本数量&#xff08;前提是线程组配置执行接口的次数线程数*循环数 大于吞吐量控制器配置的执行样本数…

【脑与认知科学】【n-back游戏】

请参考课堂内容&#xff0c;设计一种测试工作记忆的实验方法&#xff0c;并选择三位同学作为被试测试工作记忆。请画出实验流程图&#xff0c;叙述实验测试目标&#xff0c;并分析实验结果。 举例&#xff1a;一般我们选择n_back来测试对数字或字母的记忆&#xff0c;选择色块实…

Python字典六种类型概述

1. 引言 看到这个标题&#xff0c;你可能会觉得奇怪&#xff0c;事实上在Python的标准库中共有6种字典类型&#xff01;在某些情形下&#xff0c;你可能会觉得标准的Python字典dict&#xff0c;并不能完全符合你的需求。在本文中&#xff0c;我们将讨论Python中其他5个鲜为人知…

【火炬之光-魔灵装备】

文章目录 装备天赋追忆石板技能魂烛刷图策略 装备 头部胸甲手套鞋子武器盾牌项链戒指腰带神格备注盾牌其余的装备要么是召唤物生命&#xff0c;要么是技能等级&#xff0c;鞋子的闪电技能等级加2不是核心&#xff0c;腰带的话主要是要冷却有冷却暗影的技能是不会断的&#xff…

快速提高编码生产力——中国用户如何使用Jetbrains内置的AI助手

文章目录 安装AI助手插件怎么在国内使用改Jetbrains账户Country特殊工具安排上系统设置代理IDE设置代理 使用案例 安装AI助手插件 此功能依赖于AI Assistant插件&#xff0c;您需要安装并启用该插件。 按打开 IDE 设置&#xff0c;然后选择插件。CtrlAltS打开Marketplace选项…

pyqt designer的版本问题

之前我的电脑Windows11 python3.12上安装好了pyqt6后&#xff0c;安装不了pyqt6-tools&#xff0c;导致不能使用designer设计师服务。经过摸索&#xff0c;然来只需要安装qt-tools就够了。qt-tools在plugin包里。比如文章顶部的资源包&#xff0c;下载下来直接使用pip安装该whl…

Linux inotify 文件监控

Linux 内核 2.6.13 以后&#xff0c;引入了 inotify 文件系统监控功能&#xff0c;通过 inotify 可以对敏感目录设置事件监听。这样的功能被也被包装成了一个文件监控神器 inotify-tools。 使用 inotify 进行文件监控的过程&#xff1a; 创建 inotify 实例&#xff0c;获取 i…

小命令,大世界

Linux是一个大系统&#xff0c;功能丰富&#xff0c;好比是一台巨型机器&#xff0c;而命令&#xff0c;就是这台机器的操作台。要想控制好这台机器&#xff0c;用好这台机器&#xff0c;就得会看仪表&#xff0c;会操作各种按钮。《Linux常用命令自学手册》就是介绍如何操作这…

Linux上编译和安装SOFA23.06

前言 你可以直接使用编译安装好的SOFA版本Installing from all-included binaries (v23.06.00)&#xff1a; 如果你想自己编译&#xff0c;可以看我下面写的内容&#xff0c;不过绝大多数是从官网来的&#xff0c;如果和官网有出入&#xff0c;建议还是以官网为准。 在Linux下…

csapp深入理解计算机系统 bomb lab(1)phase_1

实验目的&#xff1a;进一步了解机器级代码&#xff0c;提高汇编语言、调试器和逆向工程等方面原理与技能的掌握。 实验环境&#xff1a;C、linux 实验获取&#xff1a;进入csapp官网&#xff0c;点击linux/x86-64 binary bomb下载实验压缩包。 实验说明&#xff1a;一共有6…

下一代搜索引擎会什么?

现在是北京时间2023年11月18日。聊一聊搜索。 说到搜索&#xff0c;大家首先想到的肯定是谷歌&#xff0c;百度。我把这些定义成上一个时代的搜索引擎。ChatGPT已经火热了有一年的时间了&#xff0c;大家都认为Ai搜索是下一代的搜索。但是AI搜索&#xff0c;需要的是很大算力&a…

Wireshark TS | 应用传输缓慢问题

问题背景 沿用之前文章的开头说明&#xff0c;应用传输慢是一种比较常见的问题&#xff0c;慢在哪&#xff0c;为什么慢&#xff0c;有时候光从网络数据包分析方面很难回答的一清二楚&#xff0c;毕竟不同的技术方向专业性太强&#xff0c;全栈大佬只能仰望&#xff0c;而我们…

前端JS 使用input完成文件上传操作,并对文件进行类型转换

使用input实现文件上传 // 定义一个用于文件上传的按钮<input type"file" name"upload1" />// accept属性用于定义允许上传的文件类型&#xff0c; onchange用于绑定文件上传之后的相应函数<input type"file" name"upload2"…

【0基础学Java第十课】-- 认识String类

10. 认识String类 10.1 String类的重要性10.2 常用方法10.2.1 字符串构造10.2.2 String对象的比较10.2.3 字符串查找10.2.4 转化10.2.5 字符串替换10.2.6 字符串拆分10.2.7 字符串截取10.2.8 字符串的不可变性10.2.9 字符串修改 10.3 StringBuilder和StringBuffer10.3.1 String…

cadence virtuoso寄生参数提取问题

问题描述&#xff1a; 寄生参数提取的最后一步出现问题 calibre View generation encountered a fatal Error.Please consult the logfile for messages. 解决办法&#xff1a; sudo gedit /etc/profile&#xff08;如果失败就切换到超级用户root&#xff0c;使用su root命令…

装修干货|卧室常见3个软装搭配问题。福州中宅装饰,福州装修

引言 作为一名软装设计师&#xff0c;我对卧室的家具及软装布置颇有心得&#xff0c;现在就给你们带来卧室装修设计一些小技巧&#xff1a; 1. 床&#xff1b;衣柜&#xff1b;床头柜的摆放 床的摆放位置非常重要&#xff0c;一般要放在离窗户稍远的地方&#xff0c;避免直接…

CV计算机视觉每日开源代码Paper with code速览-2023.11.14

点击CV计算机视觉&#xff0c;关注更多CV干货 论文已打包&#xff0c;点击进入—>下载界面 点击加入—>CV计算机视觉交流群 1.【基础网络架构&#xff1a;Transformer】Aggregate, Decompose, and Fine-Tune: A Simple Yet Effective Factor-Tuning Method for Vision…