栈和队列特别篇:栈和队列的经典算法问题

devtools/2025/2/2 21:35:23/

图均为手绘,代码基于vs2022实现

系列文章目录

数据结构初探: 顺序表
数据结构初探:链表之单链表篇
数据结构初探:链表之双向链表篇
链表特别篇:链表经典算法问题
数据结构:栈篇
数据结构:队列篇

文章目录

  • 系列文章目录
  • 前言
  • 一.有效的括号(leetcode 20)
  • 二.用队列实现栈(leetcode 225)
  • 三.用栈实现队列(leetcode 232)
  • 四.设计循环队列(leetcode 622)
  • 五.总结

前言

  • 栈和队列作为基础数据结构，是算法设计中的重要基石。它们在操作系统、编译器设计、网络协议等领域有着广泛应用。本文将通过C语言实现经典算法问题，帮助读者深入理解它们的底层原理和应用技巧。学习这些内容不仅能提升算法能力，还能加深对内存管理和数据结构设计的理解。

一.有效的括号(leetcode 20)

让我们先来看看题目:
在这里插入图片描述
让我们来理清楚思路:

  • 首先,我们可以用栈来实现匹配

1.我们将左括号入栈;
2.在遍历中找到右括号,进行匹配;

  • 在这个过程中,我们需要手撕一个栈的代码出来,加在题目代码之前,如果发现还不太熟练,可以再去我的这篇博客中熟悉熟悉—> 数据结构:栈篇
  • 我们还是上代码实际感受一下吧(考虑到篇幅有限,已省略栈的代码):
//注意这里是字符,栈的代码中要将int改为char
//typedef char STDataType;
bool isValid(char* s) {ST st;//创建栈STInit(&st);//初始化栈while(*s)//依次遍历字符串{if(*s == '(' || *s == '[' || *s == '{')//如果是左括号{STPush(&st,*s);//我们就将其入栈}else//其他情况{if(STEmpty(&st))//如果没找到左括号,就算下面有右括号{//我们也无法找到匹配的括号STDestroy(&st);//所以销毁,防止内存泄漏return false;//直接返回false,表示找不到匹配的括号}//因为题目要求的是按顺序一一对应;char top=STTop(&st);//此时记录下栈顶元素STPop(&st);//再pop,表示出栈操作//匹配括号逻辑结构//大家可以自行分析;//即如果右括号没有在栈顶找到对应的左括号,则错误if((*s == ')' && top != '(')||(*s == ']' && top != '[')||(*s == '}' && top != '{')){STDestroy(&st);//所以销毁,防止内存泄漏return false;//直接返回false,表示找不到匹配的括号}}s++;//更新循环条件}bool ret=STEmpty(&st);//记录是否找到对应括号的状态STDestroy(&st);//销毁,防止内存泄漏return ret;//返回对应状态
}

在这里插入图片描述

学完后,自己多多练习,自行手撕,理清逻辑即可;

二.用队列实现栈(leetcode 225)

让我们先来看看题目:
在这里插入图片描述
让我们来理清楚思路:
我们需要用到两个队列来实现栈:

  • 一个用来当作入栈队列
  • 一个用来当作出栈队列
  • 我们还要注意其LIFO的性质,和随进随出的特点
    1.我们需要保持一个队列为空,一个队列存数据
    2.出栈,把前面的数据导入空队列
    3.如此两班来回倒,就可以实现栈的特性;
    逻辑如图:
    在这里插入图片描述
    在这个过程中,我们需要手撕队列的代码出来,加在题目代码之前,如果发现还不太熟练,可以再去我的这篇博客中熟悉熟悉—> 数据结构:队列篇
    我们来实战一下:
//创建两个队列的结构体
typedef struct {Queue q1;Queue q2;
} MyStack;
//我们需要动态开辟出空间来实现mystack
MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst == NULL){perror("malloc fail");return NULL;}QueueInit(&pst->q1);//对两个队列初始化QueueInit(&pst->q2);return pst;//返回初始化后的我们的mystack
}
//来实现栈的插入
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))//如果q1不为空就插入到q1里{//反正有一个队列里面是空的,我们不能插入,一旦插入就会弄乱整体的逻辑QueuePush(&obj->q1,x);//可以参看上文图进行理解}else//如果q2不为空就插入到q2里{//两个都为空就随便选一个QueuePush(&obj->q2,x);}
}
//实现栈的删除,题目要求:移除并返回栈顶元素
int myStackPop(MyStack* obj) {//首先要明确哪个为空,哪个为非空Queue* emptyQ=&obj->q1;//假设q1为空Queue* nonemptyQ=&obj->q2;//q2不为空if(!QueueEmpty(&obj->q1))//验证是否正确{//进入则是不正确emptyQ=&obj->q2;//不正确则交换nonemptyQ=&obj->q1;}while(QueueSize(nonemptyQ) > 1)//设置遍历循环{QueuePush(emptyQ,QueueFront(nonemptyQ));//将非空的前面n-1个挪入空队列QueuePop(nonemptyQ);//pop掉已经挪入的那n-1个}//剩下的就是要按照栈的特性LIFO顺序的数据int top=QueueFront(nonemptyQ);//按照题目要求记录下数据QueuePop(nonemptyQ);//popreturn top;//返回数据
}
//返回栈顶元素
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);
}

销毁逻辑示例图:
在这里插入图片描述

在这里插入图片描述

三.用栈实现队列(leetcode 232)

让我们先来看看题目:
在这里插入图片描述
让我们来理清楚思路:
我们需要用到两个栈来实现队列:

  • 一个用来当作入队栈
  • 一个用来当作出队栈
  • 我们还要注意其FIFO的性质,和随进随出的特点
    1.我们需要保持一个入队栈,一个出队栈
    2.出队列,把前面的数据导入空栈
    3.当出队栈不为空时,不能再将出队栈中的数据导入,否则顺序会乱;
    如图:
    在这里插入图片描述
    让我们来感受一下代码:
typedef struct {ST pushst;//入队栈ST popst;//出队栈
} MyQueue;int myQueuePeek(MyQueue* obj);//返回队头元素的函数声明;
//动态开辟
MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if(obj==NULL){perror("malloc fail");return NULL;}STInit(&obj->pushst);//初始化两个栈STInit(&obj->popst);return obj;//返回模拟队列
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);//正常往入队栈中直接插入
}
//按题目要求,从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj) {int front=myQueuePeek(obj);//记录队头元素STPop(&obj->popst);//删除return front; //返回元素
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst))//如果出队栈为空{while(!STEmpty(&obj->pushst))//开始遍历循环{//并且入队栈不为空STPush(&obj->popst,STTop(&obj->pushst));//将全部元素挪过去STPop(&obj->pushst);//在入队栈中删除的操作}}return STTop(&obj->popst);//返回栈顶即是队头,可以参看上图;
}
//判空
bool myQueueEmpty(MyQueue* obj) {
//两个栈都为空,才为空return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}
//释放所有动态开辟的空间
void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);}

在这里插入图片描述

四.设计循环队列(leetcode 622)

让我们来看看题目:
在这里插入图片描述
我们来理清楚逻辑:
这里我们选择用数组来实现,链表实现也是可以的,但是相对来说,数组实现会更加容易;对于数组是否满了,我们有两种解决办法:

  • 在结构体中加入size来计量;
  • 空出一个位置来提醒判断已满
    让我们来实战:
//定义结构体
typedef struct {int* a;//静态数组int front;//头int rear;//尾int k;//满数据时候的个数
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//函数声明,防止编译错误
bool myCircularQueueIsFull(MyCircularQueue* obj);
//开出对应大小的空间
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj==NULL){perror("malloc fail");return NULL;}obj->a=(int*)malloc(sizeof(int)*(k+1));//多开,防止溢出if(obj->a==NULL){perror("malloc fail");return NULL;}obj->front=obj->rear=0;//指向开头obj->k=k;return obj;
}
//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//如果是满的{return false;//返回false,表示不能再插入了}obj->a[obj->rear++] = value;//否则存储值,并且rear++到下一个位置;obj->rear %= (obj->k+1);//对尾取模,比如,1%5==1,3%5==3,如果满了5%5==0//就会循环回到数组开始的下标return true;//返回true,表示还可以插入
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//如果是空的{return false;//返回false,表示不能再删除了}obj->front++;//头往下一个位置走,这个就与我们曾经讲过的顺序表里面的删除一样的//只要我们不把它计量在有效个数中就可以删除它obj->front %= (obj->k+1);//对头取模,比如,1%5==1,3%5==3,如果满了5%5==0//就会循环回到数组开始的下标return true;//返回true,表示还可以删除
}
//按题目要求:从队首获取元素。如果队列为空，返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//若为空{return -1;//返回}return obj->a[obj->front];//返回头元素
}
//按题目要求:获取队尾元素。如果队列为空，返回 -1 
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->rear-1+obj->k+1) % (obj->k+1)];//防止因为rear在下标0的位置--,而发生错误;//通过取模,来造成循环;
}
//简单的判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}
//判断满
bool myCircularQueueIsFull(MyCircularQueue* obj) {//通过取模,来造成循环;return (obj->rear+1) % (obj->k+1) == obj->front;//保证rear的下一个是头
}
//释放,相同与前两题,可以自行画图理解;
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

以上就是我要讲的所有的经典问题,你学会了吗?

五.总结

在本次博客中，我们围绕栈和队列这两种基础数据结构，通过C语言实现经典算法问题，深入探索了它们的底层原理与应用技巧。

  • 首先是“有效的括号”问题，利用栈来匹配括号，左括号入栈，右括号与栈顶元素匹配，这种方式充分展现了栈“后进先出”（LIFO）的特性，在处理具有成对结构的数据时十分有效 ，能够清晰地判断括号是否匹配，避免逻辑混乱。
  • 接着，在“用队列实现栈”和“用栈实现队列”的问题中，分别运用两个队列和两个栈来模拟对方的特性。用队列实现栈时，通过在两个队列间来回转移数据，确保满足栈的LIFO性质；用栈实现队列则是利用两个栈，在入队栈和出队栈间合理转移数据，保证队列“先进先出”（FIFO）的特性。这两个问题不仅锻炼了对数据结构特性的灵活运用，还让我们深入理解了不同数据结构间的转换和模拟方法。
  • 最后，在“设计循环队列”中，使用数组实现循环队列，通过巧妙的取模操作实现队列的循环，同时提供了判空和判满的方法。这种实现方式既高效又简洁，充分利用了数组的连续性和可索引性，加深了我们对队列数据结构的理解和应用能力。

通过解决这些经典算法问题，我们不仅掌握了栈和队列在实际编程中的应用，还提升了算法设计、逻辑思维以及内存管理的能力。希望读者能够通过不断练习，熟练掌握这些知识，在后续的编程学习和实践中更加得心应手，灵活运用栈和队列解决各种复杂的实际问题，为更深入的算法学习和系统开发打下坚实的基础。


http://www.ppmy.cn/devtools/155544.html

相关文章

寒假刷题Day19

寒假刷题Day19

一、923. 三数之和的多种可能 class Solution { public:int threeSumMulti(vector<int>& arr, int target) {const int MOD 1000000007; // 正确的模数long long ans 0; // 使用 long long 防止溢出std::sort(arr.begin(), arr.end());for (size_t i 0; i < a…
阅读更多...
IO流操作

IO流操作

目录 一、字符集 常见字符集 编码、解码操作 二、IO流 FileInputStream FileOutputStream FileReader FileWriter 三、打印流 PrintStream 一、字符集 常见字符集 我们的计算机底层是不可以直接存储字符的&#xff0c;计算机中底层只能存储二进制(0、1)&#xff0c…
阅读更多...
软件工程概论试题二

软件工程概论试题二

一、单选 1. 下面的说法是哪种视角对系统进行建模?“对系统与环境之间或系统构件之间的交互进行建模 A. 外部视角 B.交互式视角 C.结构化视角 D.行为视角 正答:B 2.下面描述是从哪种视角对系统进行建模的? “对系统的体系结构和系统处理的数据的结构建模”。 A.外部视角 B.交…
阅读更多...
PostgreSQL技术内幕24：定时任务调度插件pg_cron

PostgreSQL技术内幕24：定时任务调度插件pg_cron

文章目录 0.简介1.基础知识2.pg_cron安装使用方式2.1 安装pg_cron2.2 使用方式 3.实现原理3.1 启动过程3.2 任务添加和管理3.3 调度过程3.4 执行原理 0.简介 pg_cron是PostgreSQL中的一个简单的基于cron的任务调度插件&#xff0c;本文将从其基础知识&#xff08;Linux中Cron的…
阅读更多...
PostgreSQL 数据查询操作（排序、筛选、连接、分组、子查询）

PostgreSQL 数据查询操作（排序、筛选、连接、分组、子查询）

&#xff08;1&#xff09;排序查询与筛选查询操作 排序查询使用ORDER BY&#xff0c;对某个表中的列1按照列升序&#xff08;ASC&#xff0c;默认升序&#xff09;或降序&#xff08;DESC&#xff09;排序&#xff0c;排序后展示列1和列2两列。此外&#xff0c;也可以按照多列…
阅读更多...
MySQL数据类型转换应注意什么？

MySQL数据类型转换应注意什么？

文章目录 1. **隐式转换**2. **显式转换**3. **数据截断**4. **字符集与排序规则**5. **日期和时间转换**6. **数值转换**7. **NULL 处理**8. **性能影响**9. **错误处理**10. **函数选择**示例总结 在 MySQL 中进行数据类型转换时&#xff0c;需要注意以下几个关键点&#xff…
阅读更多...
基于Cipher的Java加密工具类

基于Cipher的Java加密工具类

一、什么是Cipher Cipher是一种用于加密和解密信息的算法或方法。它将原始的明文转化为密文&#xff0c;从而保护信息的安全性和机密性。使用密码学中的数学原理和技术&#xff0c;Cipher可以对数据进行加密处理&#xff0c;使其在传输或存储过程中对未授权的访问者不可读。在必…
阅读更多...
LVGL+FreeRTOS实战项目：智能健康助手（lcd篇）

LVGL+FreeRTOS实战项目：智能健康助手（lcd篇）

1.8寸彩色TFT显示屏简介 接线图 我们选用的是分辨率为128*160的彩色显示屏&#xff0c;采用的SPI接口&#xff0c;通过我们STM32的SPI外设&#xff0c;来和我们的屏幕进行通信&#xff0c;以显示我们需要显示的图片。 软件部分 #include "lcd_driver.h"//液晶IO初始…
阅读更多...
最新文章

Copyright @ 2022~2023