当前位置： 首页 > news >正文

栈和队列OJ习题

news 2025/8/30 13:58:56

目录

一. leetcode 20 有效的括号

思路（利用数据结构——栈）

代码实现

二. leetcode 225 用队列实现栈

思路

代码实现

三. leetcode 232 用栈实现队列

思路

代码实现

四. leetcode 622 环形队列

思路（用数组实现）

代码实现

一. leetcode 20 有效的括号

https://leetcode.cn/problems/valid-parentheses/description/

思路（利用数据结构——栈）

1、遍历字符串，遍历到左括号就入栈

2、遍历到右括号，就取栈顶，但是在取栈顶之前要先判断栈是否为空 ，若为空，说明前面肯定没有左括号与它匹配，返回 false

3、如果不为空，就可以比较遍历到的右括号是否与栈顶左括号匹配，如果不匹配，返回 false；如果匹配成功，就将左括号出栈，继续向后遍历字符串，直到遍历到字符串的末尾（即 '\0'）

4、遍历完成之后，要判断栈是否为空，若为空，说明每个左括号都匹配成功，然后出栈了，如果栈不为空，说明仍有左括号在栈中未匹配并出栈，即这个字符串无效

代码实现

//定义栈的结构
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;//指向栈顶的位置--刚好就是栈中有效数据的个数int capacity;
}ST;//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDesTory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity){//增容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//空间足够ps->arr[ps->top++] = x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--; 
}//取栈顶
STDataType STTop(ST* ps)
{assert(ps);return ps->arr[ps->top - 1];
}//---------------以上为栈结构的定义及一些常用方法----------------bool isValid(char* s) {ST st;STInit(&st);char* pi=s;while(*pi!='\0'){//左括号入栈if(*pi=='(' || *pi=='[' || *pi=='{'){STPush(&st,*pi);}else{//判断栈是否为空，不为空才能取栈顶if(STEmpty(&st)){STDesTory(&st);return false;}//右括号---取栈顶，比较，匹配出栈，不匹配直接返回falsechar top=STTop(&st);if((top=='(' && *pi !=')')|| (top=='[' && *pi !=']')|| (top=='{' && *pi !='}')){STDesTory(&st);return false;}//本次是匹配的，出栈STPop(&st);}pi++;}//判断栈是否为空,为空有效，非空无效//if(STEmpty(&st))// {//     STDataType(&st);//     return true;// }bool ret=STEmpty(&st) ? true :false;STDesTory(&st);return ret;
}

二. leetcode 225 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/description/

思路

  • 入栈：往不为空的队列中插入数据（两个都为空队列，随便选择一个即可，但是不能往两个队列都插入数据）
  • 出栈：将不为空队列的前 size-1 个数据依次插入到另一个队列中，再将其最后一个数据出队列
  • 取栈顶（不出数据）：找不为空的队列，返回队尾数据
  • 判空：两个队列都为空，返回 true，有一个不为空即返回 false

代码实现

typedef int QDataType;
//定义队列节点结构
typedef struct QueueNode {QDataType data;struct QueueNode* next;
}QueueNode;//定义队列结构
typedef struct Queue {QueueNode* phead;//对头QueueNode* ptail;//队尾
//	int size;        //队列中有效数据个数
}Queue;//初始化
void QInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;
}//入队——队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建值为x的节点QueueNode* newnode =(QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;//相等返回true，不相等返回false 
}//出队——队头出
void QueuePop(Queue* pq)
{//判断队列是否为空assert(!QueueEmpty(pq)); //队列中只有一个节点if (pq->phead == pq->ptail){pq->phead = pq->ptail = NULL;}else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;int size = 0;while (pcur){size++;pcur = pcur->next;}return size; 
}//销毁
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;
}//---------------------以上是队列的结构和常用方法---------------------------//两个队列实现一个栈
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));QInit(&pst->q1);QInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {//往不为空的队列中插入数据  if(!QueueEmpty(&obj->q1)){//q1QueuePush(&obj->q1,x);}else{//q2QueuePush(&obj->q2,x);}}int myStackPop(MyStack* obj) {//找不为空的队列Queue* emp=&obj->q1;Queue* noneEmp=&obj->q2;if(QueueEmpty(&obj->q2)){emp=&obj->q2;noneEmp=&obj->q1;}//不为空队列前size-1个数据挪到空队列while(QueueSize(noneEmp)>1){// //取队头// int front=QueueFront(&noneEmp);// //入另一个队列// QueuePush(&emp,front);//上面两步合并，取队头入另一个队列QueuePush(emp,QueueFront(noneEmp));//出队头QueuePop(noneEmp);}//不为空队列出数据int top =QueueFront(noneEmp);QueuePop(noneEmp);return 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) {QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);obj=NULL;
}

三. leetcode 232 用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/

思路

  • 入队列：往 pushST 栈中直接插入数据
  • 出队列：若 popST 栈为空，要将pushST 栈中的所有数据依次插入到popST 栈中，然后出popST 栈顶；若popST 栈不为空，则直接出 popST 栈顶
  • 取队头：若 popST 栈为空，要将pushST 栈中的所有数据依次插入到popST 栈中，然后取popST 栈顶；若popST 栈不为空，则直接取 popST 栈顶
  • 判空：两个栈都为空，返回 true，有一个不为空即返回 false

代码实现

//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//指向栈顶的位置--刚好就是栈中有效数据的个数int capacity;
}ST;//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDesTory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity){//增容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//空间足够ps->arr[ps->top++] = x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--; 
}//取栈顶
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}//----------------以上是栈的结构定义和常见方法------------------typedef struct {ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* pq=(MyQueue*)malloc(sizeof(MyQueue));STInit(&pq->pushST);STInit(&pq->popST);return pq;
}//入队
void myQueuePush(MyQueue* obj, int x) {//往pushST中插入数据STPush(&obj->pushST,x);
}//出队
int myQueuePop(MyQueue* obj) {//popST为空---将pushST(不为空)所有数据导入到popSTif(STEmpty(&obj->popST)){while(!STEmpty(&obj->pushST)){//取栈顶，入栈，出栈STPush(&obj->popST,STTop(&obj->pushST));STPop(&obj->pushST);}}//popST不为空直接出STDataType top=STTop(&obj->popST); STPop(&obj->popST);return top;
}//取队头
int myQueuePeek(MyQueue* obj) {//popST为空---将pushST(不为空)所有数据导入到popSTif(STEmpty(&obj->popST)){while(!STEmpty(&obj->pushST)){//取栈顶，入栈，出栈STPush(&obj->popST,STTop(&obj->pushST));STPop(&obj->pushST);}}//popST不为空直接取数据STDataType top=STTop(&obj->popST); return top;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushST) && STEmpty(&obj->popST);
}void myQueueFree(MyQueue* obj) {STDesTory(&obj->pushST);STDesTory(&obj->popST);free(obj);obj=NULL;
}

四. leetcode 622 环形队列

https://leetcode.cn/problems/design-circular-queue/description/

环形队列的特点：

  • 队头删数据，队尾插数据
  • 给定固定的空间，使用过程中不可以扩容
  • 环形队列满了，不可以继续插入数据（即插入数据失败）

环形队列可以使用数组实现，也可以用循环链表实现，用数组比较简便，原因如下：

如果用链表，初始化时，有多少个数据，就要创建多少个节点，并且每个节点就有两个成员，将这些节点联系在一起；如果用数组的话，初始化时，有多少数据，直接申请多大的空间即可，所以初始化数组更简便。而且在进行遍历/插入/删除操作时，两者的没有太大的区别。综上，数组在结构上和初始化时更简便，所以用数组比较好。（感兴趣的同学可以自行用链表试一下）

思路（用数组实现）

假设 k == 4 时，往数组中插入4个数据，rear 想要回到头节点，我们可以将 rear % 4，这样rear就回到了队头，这时 front == rear,但是，队列为空时，front == rear。如何区分环形队列是空的还是满的？

我们可以在环形队列结构中增加一个计数器成员来保存队列中有效数据的个数。那如果不能在环形队列结构中额外增加计数器成员来保存有效数据个数呢？

虽然题目要求只能保存 k 个数据，但是没有要求这个环形队列只能是 k 个空间，所以我们可以多增加一个空间，这个空间不保存任何数据，申请 k+1 个空间，这样只是在环形队列的 arr 数组中浪费了一个空间。

代码实现

typedef struct {int* arr;int front;//队头int rear;//队尾int capacity;//循环队列的空间大小（即K）
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请k+1个空间pq->arr = (int*)malloc(sizeof(int)*(k+1));pq->front = pq->rear = 0;pq->capacity = k;return pq;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1)%(obj->capacity + 1) == obj->front;
}//向循环队列插入一个元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断是否满了if(myCircularQueueIsFull(obj)){return false;}//没有满obj->arr[obj->rear++] = value;//如果rear果越界obj->rear %= obj->capacity + 1;return true;
}//从循环队列中删除一个元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断是否为空if(myCircularQueueIsEmpty(obj)){return false;}//非空，删除队头数据++obj->front;//如果front越界obj->front %= obj->capacity + 1;return true;
}//从队首获取元素
int myCircularQueueFront(MyCircularQueue* obj) {//判断是否为空if(myCircularQueueIsEmpty(obj)){return -1;}//不为空return obj->arr[obj->front];
}//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//判断是否为空if(myCircularQueueIsEmpty(obj)){return -1;}//不为空int prev = obj->rear - 1;if(obj->rear == 0){prev = obj->capacity;}return obj->arr[prev];
}void myCircularQueueFree(MyCircularQueue* obj) {//看初始化时向操作系统要了那些空间if(obj->arr)free(obj->arr);free(obj);obj = NULL;
}

总结

栈与队列作为数据结构中的 “基础容器”，其 “先进后出（LIFO）” 与 “先进先出（FIFO）” 的核心特性，是解决诸多算法问题的关键逻辑支撑。本文通过经典题型拆解，系统梳理了栈和队列 OJ 习题的解题思路，旨在帮助读者从 “会做题” 过渡到 “懂原理、能迁移”。

如果大家在练习中发现新的解题角度，或是有没搞懂的知识点，欢迎在评论区留言讨论。后续我也会持续更新数据结构相关的 OJ 解析，咱们一起在刷题中夯实基础，稳步进阶！

http://www.xdnf.cn/news/1394263.html

相关文章：

  • 佳易王钓场计时计费系统：全方位赋能钓场智能化管理，软件操作教程
  • vue在函数内部调用onMounted
  • 2025年热门职业资格证书分析
  • Rust 登堂 之 深入Rust 类型（六）
  • Linux内存管理 - LRU机制
  • 「LangChain 学习笔记」LangChain大模型应用开发：代理 （Agent）
  • VeOmni 全模态训练框架技术详解
  • 蓝蜂蓝牙模组：破解仪器仪表开发困境
  • 《P2863 [USACO06JAN] The Cow Prom S》
  • C++模板类的详细介绍和使用指南
  • 桌面GIS软件添加第三方图层
  • 【无标题】透明显示屏设计，提升展厅视觉体验边界
  • 【0424】为用户指定（CREATE TABLE）的 table 创建 relcache entry，并将其注册到 relcache ④
  • ros2--action/动作--接口
  • 【链表 - LeetCode】146. LRU 缓存
  • LeetCode Hot 100 Python (11~20)
  • Windows 11 跳过 OOBE 的方法和步骤
  • 打工人日报#20250829
  • 亚马逊季节性产品运营策略：从传统到智能化的演进
  • 【AOSP】Android Dump 开发与调试指南
  • 麒麟系统使用-VSCode运行.net过程中一些可能问题及解决办法
  • 每周资讯 | 《恋与深空》获科隆游戏展2025“最佳移动游戏奖”；8月173个版号下发
  • 25.8.29_NSSCTF——[BJDCTF 2020]Easy_WP
  • sqlachemy
  • ClickHouse 客户端
  • 精益管理学会｜工厂建设如何做好布局？
  • Express框架介绍与基础入门
  • BugKu Web渗透之file_get_contents
  • 什么是 MySQL的主从同步机制?它是如何实现的?
  • Spring Boot 使用 RestTemplate 调用 HTTPS 接口时报错：PKIX path building failed 解决方案