栈和队列初级题目（包含四个题）

目录

一、原题链接：

二、有效的括号：

​编辑代码实现：

 三、用队列实现栈：

四、用栈实现队列：

五、设计循环队列：

六、读书分享：

一、原题链接：

20. 有效的括号

225. 用队列实现栈

232. 用栈实现队列

622. 设计循环队列

二、有效的括号：

这种题大家应该在上数据结构课时应该就听过吧（括号匹配）。对于这个题，我们可以使用栈实现。

当栈顶元素与将要入栈的元素形成一个完整的括号时，就让栈顶元素出栈。直到把所有括号遍历完，栈里没有剩余元素时，就是有效的括号。


代码实现：

//手动实现一个栈
typedef char StackDataType;
typedef struct Stack
{StackDataType* _a;int _top;int _capacity;
}Stack;
void StackInit(Stack* pst);
void StackDestory(Stack* pst);
void StackPush(Stack* pst, StackDataType x);
void StackPop(Stack* pst);
int StackSize(Stack* pst);
bool StackEmpty(Stack* pst);
StackDataType StackTop(Stack* pst);
void StackInit(Stack* pst)
{assert(pst);pst->_a = (StackDataType*)malloc(sizeof(StackDataType) * 4);pst->_top = 0;pst->_capacity = 4;
}
void StackDestory(Stack* pst)
{assert(pst);free(pst->_a);pst->_a = NULL;pst->_top = 0;pst->_capacity = 0;
}
void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst->_top == pst->_capacity){pst->_capacity *= 2;StackDataType* tmp = (StackDataType*)realloc(pst->_a, sizeof(StackDataType) * pst->_capacity);if (tmp == NULL){printf("内存不足\n");exit(-1);}else{pst->_a = tmp;}}pst->_a[pst->_top] = x;pst->_top++;
}
void StackPop(Stack* pst)
{assert(pst);assert(pst->_top > 0);--pst->_top;
}
int StackSize(Stack* pst)
{assert(pst);return pst->_top;
}
bool StackEmpty(Stack* pst)
{assert(pst);return pst->_top == 0 ? 1 : 0;
}
StackDataType StackTop(Stack* pst)
{assert(pst);assert(pst->_top > 0);return pst->_a[pst->_top - 1];
}//有效的括号
bool isValid(char* s) {Stack st;StackInit(&st);bool ret=false;//用于返回最终结果while(*s!='\0'){if(*s=='('||*s=='['||*s=='{')//前括号入栈{StackPush(&st,*s);++s;}if(*s==')'||*s==']'||*s=='}')//后括号出栈{if(StackEmpty(&st))//当栈为空，入栈的是后括号，无法匹配break;        //使用break不使用return是为了防止内存泄漏，因为中途返回不会调用销毁栈的函数StackDataType Top=StackTop(&st);//取栈顶元素出来匹配//匹配不成功if(Top=='('&&*s!=')')break;if(Top=='['&&*s!=']')break;if(Top=='{'&&*s!='}')break;//匹配成功StackPop(&st);++s;}}if(*s=='\0')//字符串遍历完{ret=StackEmpty(&st);//查看栈内是否还存在元素}StackDestory(&st);return ret;
}

 三、用队列实现栈：

要用队列实现栈，我们要用两个队列来实现。

入栈时，把元素放入非空队列（最开始都为空时，随便放一个）；

出栈时，把除队尾的所有元素都放入另一个队列里，然后让队尾元素出栈。

每次保证一个队列有数据，一个队列为空。

//手动实现一个队列
typedef int QueueDataType;
typedef struct QueueNode
{struct QueueNode* _next;QueueDataType _data;
}QueueNode;
typedef struct Queue
{QueueNode* _head;QueueNode* _tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq,QueueDataType x);
void QueuePop(Queue* pq);
QueueDataType QueueFront(Queue* pq);
QueueDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq->_head = NULL;pq->_tail = NULL;
}
void QueueDestory(Queue* pq)
{assert(pq);QueueDataType* tmp = NULL;while (pq->_head != NULL){tmp = pq->_head;pq->_head = pq->_head->_next;free(tmp);}pq->_tail = NULL;
}
void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL){printf("内存不足\n");exit(-1);}newNode->_data = x;newNode->_next = NULL;if (pq->_head == NULL){pq->_head = pq->_tail = newNode;}else{pq->_tail->_next = newNode;pq->_tail = newNode;}
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->_head);QueueNode* next = pq->_head->_next;free(pq->_head);pq->_head = next;if (pq->_head == NULL){pq->_tail = NULL;}
}
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->_head);return pq->_head->_data;
}
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->_tail);return pq->_tail->_data;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->_head == NULL ? 1 : 0;
}
int QueueSize(Queue* pq)
{assert(pq);QueueNode* cur = pq->_head;int size = 0;while (cur != NULL){size++;cur = cur->_next;}return size;
}//用两个队列实现栈
typedef struct {Queue _q1;Queue _q2;
} MyStack;MyStack* myStackCreate() {MyStack* st=(MyStack*)malloc(sizeof(MyStack));//为结构体分配内存QueueInit(&st->_q1);QueueInit(&st->_q2);return st;//后续可以通过st对栈进行操作
}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)){empty=&obj->_q2;nonEmpty=&obj->_q1;}int ret=QueueBack(nonEmpty);//获取非空队列的队尾作为栈顶元素while(QueueSize(nonEmpty)>1)//将非栈顶元素放入空队列，将非空队列的元素依次出栈，除栈顶元素{    QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}QueuePop(nonEmpty);//栈顶元素出栈return ret;
}int myStackTop(MyStack* obj) {//非空队列的最后一个元素就是栈顶元素//题目说了：每次调用 pop 和 top 都保证栈不为空if(!QueueEmpty(&obj->_q1)){return QueueBack(&obj->_q1);}else //if(!QueueEmpty(obj->_q2)){return QueueBack(&obj->_q2);}
}bool myStackEmpty(MyStack* obj) {if(QueueEmpty(&obj->_q1)&&QueueEmpty(&obj->_q2)){return true;}return false;
}void myStackFree(MyStack* obj) {QueueDestory(&obj->_q1);QueueDestory(&obj->_q1);free(obj);
}

 栈的相关函数的外部调用：

int main()
{MyStack* obj = myStackCreate();myStackPush(obj, 1);myStackPush(obj, 2);return 0;
}

四、用栈实现队列：

类比于用队列实现栈，这个题也可以用两个栈实现队列。

我们创建一个插入栈（_pushSt），一个删除栈（_PopSt）,入队列就将元素放入_pushSt，出队列就将 _pushSt 里的所有元素都放入 _popSt 后再出栈。

//手动实现一个栈
typedef int StackDataType;
typedef struct Stack
{StackDataType* _a;int _top;int _capacity;
}Stack;
void StackInit(Stack* pst);
void StackDestory(Stack* pst);
void StackPush(Stack* pst, StackDataType x);
void StackPop(Stack* pst);
int StackSize(Stack* pst);
bool StackEmpty(Stack* pst);
StackDataType StackTop(Stack* pst);void StackInit(Stack* pst)
{assert(pst);pst->_a = (StackDataType*)malloc(sizeof(StackDataType) * 4);pst->_top = 0;pst->_capacity = 4;
}
void StackDestory(Stack* pst)
{assert(pst);free(pst->_a);pst->_a = NULL;pst->_top = 0;pst->_capacity = 0;
}
void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst->_top == pst->_capacity){pst->_capacity *= 2;StackDataType* tmp = (StackDataType*)realloc(pst->_a, sizeof(StackDataType) * pst->_capacity);if (tmp == NULL){printf("内存不足\n");exit(-1);}else{pst->_a = tmp;}}pst->_a[pst->_top] = x;pst->_top++;
}
void StackPop(Stack* pst)
{assert(pst);assert(pst->_top > 0);--pst->_top;
}
int StackSize(Stack* pst)
{assert(pst);return pst->_top;
}
bool StackEmpty(Stack* pst)
{assert(pst);return pst->_top == 0 ? 1 : 0;
}
StackDataType StackTop(Stack* pst)
{assert(pst);assert(pst->_top > 0);return pst->_a[pst->_top - 1];
}//用两个栈实现队列
typedef struct {Stack _pushSt;Stack _popSt;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));//为队列分配空间StackInit(&q->_pushSt);StackInit(&q->_popSt);return q;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->_pushSt,x);//直接将元素压入_pshSt
}int myQueuePop(MyQueue* obj) {int ret=myQueuePeek(obj);//由于该操作和获取队头元素操作类似，所以直接调用获取队头元素StackPop(&obj->_popSt);return ret;
}
//获取队头元素
int myQueuePeek(MyQueue* obj) {//直接在_popSt里面拿if(StackEmpty(&obj->_popSt))//当_popSt里面没有元素{while(!StackEmpty(&obj->_pushSt))//当_pushSt里面有元素{StackPush(&obj->_popSt,StackTop(&obj->_pushSt));StackPop(&obj->_pushSt);}}return StackTop(&obj->_popSt);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->_pushSt) && StackEmpty(&obj->_popSt);
}void myQueueFree(MyQueue* obj) {StackDestory(&obj->_pushSt);StackDestory(&obj->_popSt);free(obj);
}

五、设计循环队列：

对于静态循环链表的设计，由于会存在队空与队满情况的冲突（队空与队满时，头指针与尾指针都指向一个位置）

如果没有多余空间：

当多余一个空间： 

队满情况： 

执行出队操作时的特殊情况：

 

返回队尾元素，且_rear指向数组头时的情况 ：

//静态循环队列
typedef struct {int* _a;int _front;int _rear;int _k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));q->_a=(int*)malloc(sizeof(int)*(k+1));//多分配一个空间，方便区别空与满q->_front=0;q->_rear=0;q->_k=k;//记录循环链表的容量return q;
}
//先声明，方便函数调用
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}else{obj->_a[obj->_rear]=value; if(obj->_rear==obj->_k){obj->_rear%=obj->_k;//_rear在最后一个位置需要向后移动时，回到数组头部}   else{obj->_rear++; }}return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}else{obj->_front++;if(obj->_front==obj->_k+1)//如果_front走到了数组最后一个位置的下一个位置时，回到数组头部{obj->_front%=obj->_k+1;}}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->_a[obj->_front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//队列内没有元素return -1;if(obj->_rear==0)//队尾指针指向在数组的第0号位置，队尾元素应该在数组的最后return obj->_a[obj->_k];return obj->_a[obj->_rear-1];   
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->_front==obj->_rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->_rear+1)%(obj->_k+1) == obj->_front;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->_a);free(obj);
}

六、读书分享：

《道德经·第五十章》：

出生入死。生之徒，十有三；死之徒”，十有三；人之生，动之于死地”，亦十有三。夫何故?以其生生之厚。
盖闻善摄生者", 陆行不遇兕虎，人军不被甲兵"。兕无所投其角”，虎无所用其爪”，兵无所容其刃。夫何故?以其无死地。

解释：

人出世为生，入地为死。属于长寿的，占十分之三；属于短命的，占十分之三；人的过分地奉养生命，妄为而走向死路的，也占了十分之三。为什么呢?因为奉养太过度了。
听说善于养护生命的人，在陆地上行走不会遇到犀牛和老虎，在战争中不会受到杀伤。犀牛用不上它的角，老虎用不上它的爪，兵器用不上它的刃。为什么呢?因为他没有进入死亡的范围。
 

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

机器学习-12-sklearn案例03-flask对外提供服务

机器学习-12-sklearn案例03-flask对外提供服务

整体思路 训练一个模型，把模型保存 写一个基于flask的web服务，在web运行时加载模型，并在对应的接口调用模型进行预测并返回 使用curl进行测试，测试通过 再创建一个html页面，接受参数输入，并返回。 目录结…
阅读更多...
西湖大学英语听力考试音频无线发射系统-英语听力发射系统浅析

西湖大学英语听力考试音频无线发射系统-英语听力发射系统浅析

西湖大学英语听力考试音频无线发射系统-英语听力发射系统浅析 由北京海特伟业科技任洪卓发布于2024年5月10日 西湖大学，这所矗立于时代前沿的高等学府，始终秉持着创新精神和追求卓越的坚定信念，不断致力于教学质量的提升与学术研究的深化。其…
阅读更多...
Sql Server 2016数据库定时备份

Sql Server 2016数据库定时备份

一、 配置备份计划任务 选中“维护计划“--右键--“维护计划向导” 完成
阅读更多...
详解Python测试框架Pytest的参数化

详解Python测试框架Pytest的参数化

🍅 视频学习：文末有免费的配套视频可观看 🍅 点击文末小卡片，免费获取软件测试全套资料，资料在手，涨薪更快 上篇博文介绍过，Pytest是目前比较成熟功能齐全的测试框架，使用率肯定也不…
阅读更多...
一次完整的GC流程

一次完整的GC流程

Java堆中内存区分 Java的堆由新生代（Young Generation）和老年代（Old Generation）组成。新生代存放新分配的对象，老年代存放长期存在的对象。 新生代（Young）由年轻区（Eden&a…
阅读更多...
语义分割——脑肿瘤图像分割数据集

语义分割——脑肿瘤图像分割数据集

引言 亲爱的读者们，您是否在寻找某个特定的数据集，用于研究或项目实践？欢迎您在评论区留言，或者通过公众号私信告诉我，您想要的数据集的类型主题。小编会竭尽全力为您寻找，并在找到后第一时间与您分享。 …
阅读更多...
2024年首季：AGV项目大盘点，有过1亿的项目

2024年首季：AGV项目大盘点，有过1亿的项目

导语 大家好，我是智能仓储物流技术研习社的社长，老K。专注分享智能仓储物流技术、智能制造等内容。 新书《智能物流系统构成与技术实践》 2024年第一季度，中国智慧物流行业迎来了一个重要的里程碑。 根据新战略移动机器人产业研究所的初步统计…
阅读更多...
Numpy求最大、最小值、求累乘、累和

Numpy求最大、最小值、求累乘、累和

Numpy求最大、最小值 代码举例： ​ 输出结果为： ​ 在这个例子中，我们首先导入了NumPy库，然后创建了一个3x3的矩阵A。接着，我们使用np.max()函数来求矩阵A的最大值，并将结果存储在变量max_value中&#xff…
阅读更多...
MyBatis——MyBatis入门程序

MyBatis——MyBatis入门程序

一、数据准备 二、开发步骤 1、引入依赖 <dependencies><dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.15</version></dependency><dependency><groupId>c…
阅读更多...
netty配置SSL、netty配置https（开发）

netty配置SSL、netty配置https（开发）

netty配置SSL、netty配置https&#xff08;开发&#xff09; 我们在开发下使用ssl&#xff0c;所用的证书将不被客户端信任。 转自&#xff1a;https://lingkang.top/archives/netty-pei-zhi-ssl 方案一 快速。使用netty提供的临时签发证书 private static SslContext sslC…
阅读更多...
python实现背单词程序

python实现背单词程序

欢迎关注我👆，收藏下次不迷路┗|｀O′|┛ 嗷~~ 目录 一.前言 二.代码 三.使用 四.分析 一.前言 背单词是学习英语的一个重要环节，它有很多好处，以下是其中一些主要的好处： 提高词汇量
阅读更多...
未授权访问：Memcached 未授权访问漏洞

未授权访问：Memcached 未授权访问漏洞

目录 1、漏洞原理 2、环境搭建 3、未授权访问 防御手段 今天继续学习各种未授权访问的知识和相关的实操实验&#xff0c;一共有好多篇&#xff0c;内容主要是参考先知社区的一位大佬的关于未授权访问的好文章&#xff0c;还有其他大佬总结好的文章&#xff1a; 这里附上大…
阅读更多...
如何访问远程MySQL数据库服务器？

如何访问远程MySQL数据库服务器？

访问远程MySQL数据库服务器是一项常见的任务&#xff0c;它允许我们在不同的地点通过网络连接到MySQL服务器&#xff0c;并进行数据库管理和数据处理操作。我们将重点介绍一种名为【天联】的组网技术&#xff0c;该技术提供了一系列优势&#xff0c;使远程访问MySQL数据库服务器…
阅读更多...
【AI+换脸换装】从OpenAI 探索色情露骨内容领域浅聊AI换脸换装

【AI+换脸换装】从OpenAI 探索色情露骨内容领域浅聊AI换脸换装

5月9日消息&#xff0c;据外电报道&#xff0c;OpenAI 周三发布了文档草案&#xff0c;阐述了它希望 ChatGPT 及其其他人工智能技术如何运作。冗长的Model Spec 文件的一部分透露&#xff0c;该公司正在探索进军色情和其他露骨内容领域。 看完这个&#xff0c;心里有点惊讶&am…
阅读更多...
HarmonyOS NEXT星河版之美团外卖点餐功能实战(下)

HarmonyOS NEXT星河版之美团外卖点餐功能实战(下)

文章目录 一、购物车逻辑1.1 购物车及加减菜1.2 菜品的加减---方案一1.3 菜品的加减---方案二1.4 购物车View完善1.5 清空购物车1.5 购物车数量和价格 二、小结 一、购物车逻辑 1.1 购物车及加减菜 在utils目录下新建CartStore.ets文件&#xff0c;如下&#xff1a; import …
阅读更多...
华为与达梦数据签署全面合作协议

华为与达梦数据签署全面合作协议

4月26日&#xff0c;武汉达梦数据库股份有限公司&#xff08;简称“达梦数据”&#xff09;与华为技术有限公司&#xff08;简称“华为”&#xff09;在达梦数据武汉总部签署全面合作协议。 达梦数据总经理皮宇、华为湖北政企业务总经理吕晓龙出席并见证签约&#xff1b;华为湖…
阅读更多...
Istio中的全局限流方案

Istio中的全局限流方案

Istio中的全局限流方案 在k8s网格&#xff08;istio&#xff09;环境中&#xff0c; 可以通过创建Envfoyfilter的方式来配置限流。 在istio官方文档中&#xff0c;提供了两种限流方式&#xff1a; 本地限流全局限流 本地限流的细节这里不再赘述, 主要讲解全局限流的配置方式…
阅读更多...
解双曲型非线性方程的Harden-Yee算法(TVD格式)

解双曲型非线性方程的Harden-Yee算法(TVD格式)

解双曲型非线性方程的Harden-Yee算法 先贴代码&#xff0c;教程后面有空再写 import matplotlib import math matplotlib.use(TkAgg) import numpy as np import matplotlib.pyplot as plt def Phiy(yy,epsi):#phi(y)if abs(yy) > epsi:phiyy abs(yy)else:phiyy (yy*yy…
阅读更多...
VTK 数据类型：规则网格

VTK 数据类型：规则网格

VTK 数据类型&#xff1a;规则网格 VTK 数据类型&#xff1a;规则网格分类三种规则网格需要的设置实例 VTK 数据类型&#xff1a;规则网格 分类 VTK 有 3 种规则网格&#xff1a; vtkImageData&#xff1a;几何结构和拓扑结构都是规则的。vtkRectilinearGrid&#xff1a;几何…
阅读更多...
AI大模型探索之路-训练篇20：大语言模型预训练-常见微调技术对比

AI大模型探索之路-训练篇20：大语言模型预训练-常见微调技术对比

系列篇章&#x1f4a5; AI大模型探索之路-训练篇1&#xff1a;大语言模型微调基础认知 AI大模型探索之路-训练篇2&#xff1a;大语言模型预训练基础认知 AI大模型探索之路-训练篇3&#xff1a;大语言模型全景解读 AI大模型探索之路-训练篇4&#xff1a;大语言模型训练数据集概…
阅读更多...
最新文章

Copyright @ 2022~2023