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

目录

一、原题链接：

二、有效的括号：

​编辑代码实现：

 三、用队列实现栈：

四、用栈实现队列：

五、设计循环队列：

六、读书分享：

一、原题链接：

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);
}

六、读书分享：

《道德经·第五十章》：

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

解释：

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

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

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

相关文章

理解Go语言中的测试种类

理解Go语言中的测试种类

测试金字塔将测试分为不同的类别，如下图所示 单元测试在金字塔的底部。大部分测试都是单元测试，它们编写成本代、执行速度快且执行结果高度确定。通常，越往金子塔的上层走，测试变得越复杂，运行速度越慢，并且越难保证执行结果的确定性。 一个常见的技巧是明确说明要运行哪…
阅读更多...
maven的安装与配置（超详细）

maven的安装与配置（超详细）

在Java开发中，配置Maven环境有几个重要的原因： 依赖管理：Maven 是一个强大的依赖管理工具，它能够帮助开发人员轻松地管理项目所需的各种第三方库和组件。通过在项目的 Maven 配置文件（pom.xml）中定义依赖&…
阅读更多...
怎么把手机ip地址变成了外省

怎么把手机ip地址变成了外省

在日常使用中，有时我们可能因为某些原因需要快速切换手机的IP地址，特别是当需要从一个省份切换到另一个省份的IP时。这种需求可能来源于网络访问限制、地理位置相关服务的使用、或者网络安全等方面的考虑。那么，怎么把手机IP地址变成外省呢&a…
阅读更多...
Ps 滤镜：蒙尘与划痕

Ps 滤镜：蒙尘与划痕

Ps菜单：滤镜/杂色/蒙尘与划痕 Filter/Noise/Dust & Scratch 蒙尘与划痕 Dust & Scratch滤镜可用于修复图像中的小瑕疵、尘埃或划痕，特别适合用于清理扫描的照片或老照片中的损伤，以及其他因拍摄条件不理想或相机传感器上的尘埃所造成…
阅读更多...
前端开发指导

前端开发指导

前端开发指导 本文介绍了配置前端开发环境需要的软件、配置项等，指导如何开始进行UDM部门前端开发的全流程。本文以Windows系统下在Microsoft Virtual Studio Code中开发为基础。 一、综述 目标：零基础或者新员工依照此文档，能够完成开发环境的搭建及熟悉测试环境的搭建。…
阅读更多...
【Java难点】多线程-终极【更新中...】

【Java难点】多线程-终极【更新中...】

Java内存模型之JMM 为什么需要JMM 计算机存储结构：从本地磁盘到主存到CPU缓存，也就是从硬盘到内存，到CPU。一般对应的程序的操作就是从数据库查数据到内存然后到CPU进行计算。 CPU和物理主内存的速度不一致，所以设置多级缓存&am…
阅读更多...
SinoDB数据库出现长事务的解决方法

SinoDB数据库出现长事务的解决方法

SinoDB数据库出现长事务的具体现象：   长事务会引发逻辑日志耗尽，导致数据库进入叫做“长事务阻塞Blocked:LONGTX”的状态中，数据库服务响应停止。这时候，数据库状态通过onstat – 命令通常有如下提示： Sinoregal Si…
阅读更多...
DSP ARM FPGA 实验箱_音频处理_滤波操作教程：3-9 音频信号的滤波实验

DSP ARM FPGA 实验箱_音频处理_滤波操作教程：3-9 音频信号的滤波实验

一、实验目的 掌握Matlab辅助设计滤波器系数的方法，并实现音频混噪及IIR滤波器滤除，并在LCD上显示音频信号的FFT计算结果。 二、实验原理 音频接口采用的是24.576MHz（读兆赫兹）晶振，实验板上共有3个音频端口&#x…
阅读更多...
计算机视觉：三维重建技术

计算机视觉：三维重建技术

书籍：Computer Vision：Three-dimensional Reconstruction Techniques 作者：Andrea Fusiello 出版：Springer 书籍下载-《计算机视觉：三维重建技术》​本书探讨了用于通过图像确定实体物体的几何属性的理论和计算技术…
阅读更多...
将来会是Python、Java、Golang三足鼎立吗？

将来会是Python、Java、Golang三足鼎立吗？

在开始前我有一些资料，是我根据网友给的问题精心整理了一份「 Java的资料从专业入门到高级教程」， 点个关注在评论区回复“888”之后私信回复“888”，全部无偿共享给大家！！！ 软件工程里没有银弹&#xff…
阅读更多...
Java方法的重载

Java方法的重载

方法重载 1. 为什么需要方法重载 public class TestMethod{public static void main (String[] args){int a 10;int b 20;int ret add(a,b);System.out.println("ret "ret);double a2 10.5;double b2 20.5;double ret2 add(a2,b2);System.out.println("…
阅读更多...
layui select 绑定onchange事件失效

layui select 绑定onchange事件失效

layui select 绑定onchange事件失效 问题背景解决方案 问题背景 在日常工作中，可能会用到页面 freemaker 以及 layui 前端框架，这个时候直接在 select 上面绑定 onchange 事件往往是不生效的，错误的方式 这种方式给 select 绑定的 onchange…
阅读更多...
OpenCV学习（一）银行卡号识别

OpenCV学习（一）银行卡号识别

B站教学链接： 银行卡号识别（OpenCV-Python） 代码：Card_Number_Recognition 1.方法 使用模板匹配的方法来识别银行卡号数字。具体来说，先通过图像预处理将图像中的银行卡号分割出来，再与提供的模板进行…
阅读更多...
elementui的table行展开，左侧的icon有的需要有的不需要

elementui的table行展开，左侧的icon有的需要有的不需要

百度了一些方法，都不好用，最后还是纯css解决，以下是效果： 代码实现： :deep(.el-table__row:nth-child(1) .el-table__expand-icon){ display: none; }
阅读更多...
node pnpm修改默认包的存储路径

node pnpm修改默认包的存储路径

pnpm与npm的区别 PNPM和NPM是两个不同的包管理工具。 NPM（Node Package Manager）是Node.js的官方包管理工具，用于安装、发布和管理Node.js模块。NPM将包安装在项目的node_modules目录中，每个包都有自己的依赖树。 PNPM&#xf…
阅读更多...
如何使用 ERNIE 千帆大模型基于 Flask 搭建智能英语能力评测对话网页机器人（详细教程）

如何使用 ERNIE 千帆大模型基于 Flask 搭建智能英语能力评测对话网页机器人（详细教程）

ERNIE 千帆大模型 ERNIE-3.5是一款基于深度学习技术构建的高效语言模型，其强大的综合能力使其在中文应用方面表现出色。相较于其他模型，如微软的ChatGPT，ERNIE-3.5不仅综合能力更强，而且在训练与推理效率上也更高。这使得ERNIE-3…
阅读更多...
ESP32引脚入门指南(五）：从理论到实践(SPI)

ESP32引脚入门指南(五）：从理论到实践(SPI)

ESP32 微控制器因其丰富的外设接口而备受赞誉，其中SPI（Serial Peripheral Interface）是一种常见的通信协议。本文将深入探讨ESP32的SPI、HSPI（High-Speed SPI）和VSPI（Very High-Speed SPI）接口&…
阅读更多...
3DGS+3D Tiles融合已成 ，更大的场景，更细腻的效果～

3DGS+3D Tiles融合已成 ，更大的场景，更细腻的效果～

最近国外同行Kieran Farr发布了一个他制作的3D GussianSplatting(高斯泼溅)Google Map 3D Tiles的融合叠加的demo案例（如下所示）。 准确来说这是一个数据融合的实景场景，该实景场景使用了倾斜三维和3D GussianSplatting两种实景表达技术&…
阅读更多...
CSS跳动文字

CSS跳动文字

<div class"loading-mask"><div class"loading-text"><span style"--i:1">加</span><span style"--i:2">载</span><span style"--i:3">中</span><span style"--i:…
阅读更多...
JCR一区 | Matlab实现1D-2D-GASF-CNN-GRU-MATT的多通道输入数据分类预测

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

JCR一区 | Matlab实现1D-2D-GASF-CNN-GRU-MATT的多通道输入数据分类预测 目录 JCR一区 | Matlab实现1D-2D-GASF-CNN-GRU-MATT的多通道输入数据分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 基本介绍 Matlab实现1D-2D-GASF-CNN-GRU-MATT的多通道输入数据分类预…
阅读更多...
最新文章

Copyright @ 2022~2023