栈和队列经典练习题

目录

前言：

一、括号匹配问题

        1.题目描述

        2.解题思路 

        3.题目链接

二、用队列实现栈

        1.题目描述

        2.解题思路 

        3.题目链接

三、用栈实现队列

        1.题目描述

        2.题目分析 

         3.题目链接

四、设计循环队列

        1.题目描述

        2. 题目分析 

        3.题目链接

最后

前言：

        前面已经为大家讲解了栈和队列的概念以及如何实现，接下来本博主为大家整理了几道题目，帮助大家更好的理解栈和队列，请大家看完本文后不要忘记练习哦。

一、括号匹配问题

        1.题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

        2.解题思路 

        大家在看到此题时，相信会有以下思路：既然要解决括号匹配，那么，我用一个变量left来记录左括号的数量，用变量right来记录右括号的数量，咋一听似乎是可行的，那么，我们使用如下的代码经行测试。

bool isValid(char* s) {
    int left = 0;
    int right = 0;
    while(*s)
    {
        if(*s == '(' || *s == '{' || *s == '[')
        {
            left++;
        }
        if(*s == ')' || *s == '}' || *s == ']')
        {
            right++;
        }
        s++;
    }
    if(right == left)
    {
        return true;
    }
    else
    {
        return false;
    }
}

        结果如下：

        很显然官方也知道我们会有这样的想法，提前准备好用例来隔绝此种可能。那么，我们就束手无策了吗？当然不能，坐以待毙不是我们的风格，对吧？

        我们之前学习过了栈，那么，这道题我们用栈来考虑一下：

        我们首先 开辟一个栈用来放左括号，当有右括号要来匹配时，我们拿出最后入栈的左括号与之匹配，若能匹配成功，就继续比较下一组，若不行就反回false。

        这个思路明显可行，那我们就来实现一下吧！

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

        使用以上代码进行测试，至于栈的底层实现，相信大家都很乐意当CV工程师（手动dogo）。这样写，测试用例也可以通过，但提交会失败。

        这是为什么呢？大家这时把这个带入到代码中试一下，我们会发现无右括号与之匹配，那么，我们怎么处理比较好？我们可不可以在最后去判空一下，因为有右括号在时，我们才会进行Pop，这时又来个问题，如果只有右括号，没左括号，那还是true，对吧。所以，我们也应该在else那经行判空。这次思路代码如下：

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

         这次的提交不就通过了，所以，我们今后写代码一定要考虑周全。

        3.题目链接

        . - 力扣（LeetCode）

二、用队列实现栈

        1.题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

 

        2.解题思路 

        题目要求使用队列来实现栈，首先，我们都明白队列和栈的特点。队列：先进先出。栈：先进后出。那么使用两个队列来实现栈，就要使用其特性来进行实现。这里，给大家说一说思路：

        代码实现思路如下：

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

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

void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&(obj->q1)))
    {
        QueuePush(&(obj->q1), x);
    }
    else {
        QueuePush(&(obj->q2), x);
    }
}int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        nonempty = &obj->q1;
        empty = &obj->q2;
    }
    while (QueueSize(nonempty) > 1)
    {
        QueuePush(empty, QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int tmp = QueueFront(nonempty);
    QueuePop(nonempty);
    return tmp;
}

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

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

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

         对于底层代码大家若是想练习敲一遍即可，如果熟悉了即可成为CV工程师。

        3.题目链接

        . - 力扣（LeetCode）

三、用栈实现队列

        1.题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

 

        2.题目分析 

        此题与上题类似，都是互相实现对方的题目。此类题目都要求我们掌握其特性以及都对其底层代码都能熟练掌握。话不多说，我们来分析一下此题，大家都可以思考一下，此题大致思路与上题类似。

        代码实现思路如下：

typedef struct {
    Stack p1;
    Stack p2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pst->p1);
    StackInit(&pst->p2);
    return pst;
}

void myQueuePush(MyQueue* obj, int x) {
   StackPush(&obj->p1,x);
}

int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);
    StackPop(&obj->p2);
    return front;
}

int myQueuePeek(MyQueue* obj) {
   if(StackEmpty(&obj->p2))
   {
        while(!StackEmpty(&obj->p1))
        {
            int top = StackTop(&obj->p1);
            StackPop(&obj->p1);
            StackPush(&obj->p2,top);
        }
   }
   return StackTop(&obj->p2);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->p1) && StackEmpty(&obj->p2);
}

void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->p1);
    StackDestory(&obj->p2);
    free(obj);
}

         3.题目链接

        . - 力扣（LeetCode）

四、设计循环队列

        在开始说此题前，先简单对大家解释一下什么为循环队列。

        大家，可这样理解：相信大家对循环链表不陌生（博主之前讲解链表习题时说过）。那么，大家可以把链表换成数组想象一下即可。

        当我们简单知道了这是一个什么东西后，我们一定要明白的知识点为：如何判断此时的链表是空还是满？ 

        如何断定是空？相信大家有办法即：因为要记录其头地址和尾地址，在开始时，使头地址和尾地址指向一致，此时该队列为空。

        那么？如何判断该队列为满的情况呢？相信有人说：使头（head）和尾（tatil）一致即可。可是，咱们不是规定为空吗？这不就矛盾了吗？别慌，我将介绍两种方法供大家参考使用。

        法一：设一个size常量。刚开始使之为0，数组长度为k，若size % k == 0，认为队列满了。相信此方法大家都能理解。

        法二：多开辟一个一个空间，注意：此空间不放元素。判断队列满了的条件为：（tail+1）%k + 1 == head。大家可画图理解都不难。（常用法二）

        此处，教大家一个计算队列元素的方法：（ tail-head+size（MAX）） %size（MAX）。可帮助大家解决选择题。

        好了，我们一起来看看题目吧！

        1.题目描述

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

 

        2. 题目分析 

        此题考查循环队列，其实就是上面我给大家说的知识，此题难点为：如何删除元素以及获取尾元素。

        删除元素：使head++，然后确定其下标即可。操作很简单，该如何理解呢？

        获取尾元素：有人说，这个简单取tail--的值即可，是不错。那要是tail此时指向头呢？估计会有人说：不可能，绝对不可能。怎么不可能呢？别忘了，这可是循环队列,都有可能 。

        为了应对这种情况可以用这种写法:(tail-1+k+1) % (k+1) 。这个是常规写法,既然有常规,那肯定还有不常规了,不常规也可以称之为:装逼写法 。只要你一键三连便可解锁,即:(tail+k) %(k+1) 。这时,有人说了:就这?也没啥吗?你们这样想,如果没上面的写法,你能看懂这种写法吗?都看到这了,记得承诺哦 。

        难点已解决,接下来,展示本题代码:

typedef struct {
    int* a;
    int head;
    int ptail;
    int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->head = obj->ptail = 0;
    obj->k = k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) {
        return false;
    }
    obj->a[obj->ptail] = value;
    obj->ptail++;
    obj->ptail %= (obj->k + 1);

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
        ++obj->head;
        obj->head %= (obj->k + 1);
        return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    } else {
        return obj->a[obj->head];
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    } else {
        return obj->a[(obj->ptail + obj->k ) %( obj->k + 1)];
    }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->ptail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->ptail + 1) % (obj->k + 1) == obj->head;
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

        3.题目链接

        . - 力扣（LeetCode）

最后

        以上便是全部内容,记得练习 。如有问题可私信也可评论区见!

完!

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

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

相关文章

JCR一区 | Matlab实现1D-2D-GASF-CNN-BiLSTM-MATT的多通道输入数据分类预测

JCR一区 | Matlab实现1D-2D-GASF-CNN-BiLSTM-MATT的多通道输入数据分类预测

JCR一区 | Matlab实现1D-2D-GASF-CNN-BiLSTM-MATT的多通道输入数据分类预测 目录 JCR一区 | Matlab实现1D-2D-GASF-CNN-BiLSTM-MATT的多通道输入数据分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 Matlab实现1D-2D-GASF-CNN-BiLSTM-MATT的多通道输入数据分类预…
阅读更多...
未授权访问：VNC未授权访问

未授权访问：VNC未授权访问

目录 1、漏洞原理 2、环境搭建 3、未授权访问 防御手段 今天继续学习各种未授权访问的知识和相关的实操实验，一共有好多篇，内容主要是参考先知社区的一位大佬的关于未授权访问的好文章，还有其他大佬总结好的文章： 这里附上大…
阅读更多...
修改MTU值解决Linux下运行top命令卡死问题

修改MTU值解决Linux下运行top命令卡死问题

上周明月的Linux服务器上运行top命令总是莫名的出现卡死现象，甚至是CtrlC都无法终止进程，今天终于抽空找到了解决办法，原来是需要修改Linux的MTU值，将服务器操作系统数据包调小，加上VxLAN数据包小于1500即可。 top命令…
阅读更多...
Python-VBA函数之旅-sum函数

Python-VBA函数之旅-sum函数

目录 一、sum函数的常见应用场景 二、sum函数使用注意事项 三、如何用好sum函数？ 1、sum函数： 1-1、Python： 1-2、VBA： 2、推荐阅读： 个人主页： https://myelsa1024.blog.csdn.net/ 一、sum函数的常…
阅读更多...
摩苏尔大坝形变监测

摩苏尔大坝形变监测

摩苏尔大坝，是伊拉克最大的大坝。它位于底格里斯河35公里，北距摩苏尔市，这是一座粘土质地的水坝，高113米，长3.2公里，于1986落成。 大坝建成后不久，大坝就遇到了由软石膏地基造成的一些结构性问题…
阅读更多...
jenkins连接ubuntu普通用户节点

jenkins连接ubuntu普通用户节点

1.创建credentials 2.创建node 3.在jenkins服务器还需要进行的操作（jenkins服务器中） mkdir /var/lib/jenkins/.ssh ssh-keyscan -H 192.168.110.204 >> /var/lib/jenkins/.ssh/known_hosts chown -R jenkins:jenkins /var/lib/jenkins/.ssh/ 4.…
阅读更多...
试衣不再有界：Tunnel Try-on开启视频试衣应用新纪元

试衣不再有界：Tunnel Try-on开启视频试衣应用新纪元

论文：https://arxiv.org/pdf/2404.17571 主页：https://mengtingchen.github.io/tunnel-try-on-page/ 一、摘要总结 随着虚拟试衣技术的发展，消费者和时尚行业对于能够在视频中实现高质量虚拟试衣的需求日益增长。这项技术允许用户在不实际穿…
阅读更多...
【实战】算法思路总结

【实战】算法思路总结

面试过程中，总是被拷打，信心都要没了。但是也慢慢摸索出一些思路，希望对大家有帮助。 （需要多用一下ACM模式，力扣模式提供好了模板，自己在IDEA里面写的话，还是会有些陌生） 0、基本…
阅读更多...
MFC重要的初始化函数InitInstance

MFC重要的初始化函数InitInstance

MFC应用程序最早处理的类的初始化函数通常是CWinApp类的构造函数。CWinApp类是MFC应用程序的主类，负责整个应用程序的初始化和管理。 在MFC应用程序中，通常会创建一个派生自CWinApp类的应用程序类，例如CMyApp。在应用程序启动时，…
阅读更多...
【Oracle篇】rman物理备份工具的基础理论概述（第一篇，总共八篇）

【Oracle篇】rman物理备份工具的基础理论概述（第一篇，总共八篇）

☘️博主介绍☘️： ✨又是一天没白过，我是奈斯，DBA一名✨ ✌✌️擅长Oracle、MySQL、SQLserver、阿里云AnalyticDB for MySQL(分布式数据仓库)、Linux，也在扩展大数据方向的知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章&am…
阅读更多...
Mujoco仿真【将urdf文件转化为xml文件】

Mujoco仿真【将urdf文件转化为xml文件】

最近开始学习mujoco仿真方面的内容 先前写过一篇博客：强化学习：MuJoCo机器人强化学习仿真入门（1）_mujoco仿真-CSDN博客 简单介绍了mujoco仿真的一些内容，下面想在Mujoco中将urdf转为xml文件，了解到mujoco是…
阅读更多...
Docker需要代理下载镜像

Docker需要代理下载镜像

systemctl status docker查看docker的状态和配置文件是/usr/lib/systemd/system/docker.service vi /usr/lib/systemd/system/docker.service， 增加如下配置项 [Service] Environment"HTTP_PROXYhttp://proxy.example.com:8080" "HTTPS_PROXYhttp:…
阅读更多...
MySQL软件安装基于压缩包

MySQL软件安装基于压缩包

打开mysql官网网址 MySQL :: Download MySQL Community Server 本次针对版本8的安装包方式进行安装，下载成功后接下来对MySQL进行安装 下载后有一个以zip后缀结尾的压缩包文件 对于安装包方式安装，比起可视化安装省去了许多安装步骤，这里直接…
阅读更多...
WordPress插件Show IDs by Echo，后台显示文章、页面、分类、标签、媒体库、评论、用户的ID

WordPress插件Show IDs by Echo，后台显示文章、页面、分类、标签、媒体库、评论、用户的ID

WordPress的这款Show IDs by Echo插件，可以让我们设置是增加一列ID还是直接在“编辑 |快速编辑 |查看”操作后面增加ID，而且支持展示以下内容的ID： 文章页面类别标签评论自定义帖子类型自定义分类法用户媒体 Show IDs by Echo插件的安装及启…
阅读更多...
数据缓存，可以尝试RocksDB了

数据缓存，可以尝试RocksDB了

shigen坚持更新文章的博客写手，擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长，分享认知，留住感动。 个人IP：shigen shigen在最近的学习中，接触到了一款新的缓存数据库RocksDB&#xff…
阅读更多...
ctfshow web271--web273

ctfshow web271--web273

web271 laravel5.7反序列化漏洞 define(LARAVEL_START, microtime(true));/* |-------------------------------------------------------------------------- | Register The Auto Loader |-------------------------------------------------------------------------- | |…
阅读更多...
开源流程引擎选型 —— Activiti、Flowable、Camunda

开源流程引擎选型 —— Activiti、Flowable、Camunda

目录 一. 前言 二. 主流开源流程引擎介绍 2.1. Osworkflow 2.2. JBPM 2.3. Activiti 2.4. Flowable 2.5. Camunda 三. Flowable 与 Camunda 对比分析 3.1. 功能方面对比 3.2. 性能方面对比 四. 总结 一. 前言 市场上比较有名的开源流程引擎有 Osworkflow、JBPM、Act…
阅读更多...
【35分钟掌握金融风控策略25】定额策略实战2

【35分钟掌握金融风控策略25】定额策略实战2

目录 基于收入和负债的定额策略 确定托底额度和盖帽额度 确定基础额度 基于客户风险评级确定风险系数 计算最终授信额度 确定授信有效期 基于收入和负债的定额策略 在实际生产中，客户的收入和负债数据大多无法直接获得，对于个人的收入和负债数据&…
阅读更多...
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )

LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！ 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航： LeetCode解锁100…
阅读更多...
【算法】dfs

【算法】dfs

快乐的流畅：个人主页 个人专栏：《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火，在为久候之人燃烧！ 文章目录 引言一、全排列1. 决策树2. 设计代码1. 全局变量2. dfs函数3. 细节问题 二、子集解法一1. 决策树2. 设计代码…
阅读更多...
最新文章

Copyright @ 2022~2023