Data Structure--栈和队列相关例题--括号匹配问题--用队列实现栈--用栈实现队列

矫情吗；* 2022-10-30 15:21 213阅读 0赞

## 1.括号匹配问题 ##

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串 s ，判断字符串是否有效。  
条件:  
左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。

//找到了左边的括号,就将其入栈,当找到了右边匹配的,则将左边的出栈,这样栈就为空,就成功匹配
    bool isValid(char * s){ 
    	stack st;
    
    	stackInit(&st);		//初始化
    	static char map[][2] = {  {  '(', ')' }, {  '[', ']' }, {  '{', '}' } };	//检测括号
    
    	while (*s){ 	//存在字符时
    
    		int i = 0;
    
    		for (; i<3; ++i){ 	//利用循环找到左边对应的括号
    			if (*s == map[i][0]){ 
    				stackPush(&st, *s);	//找到就入栈
    				++s;
    				break;	//结束循环
    
    			}
    		}
    		if (i == 3){ 	//如果没有找到,为3则没找到
    
    			if (stackEmpty(&st))	//判断如果为空,则直接返回
    				return false;
    			char topchar = stackTop(&st);	//定义一个字符指向栈顶
    
    			for (int j = 0; j<3; ++j){ 	//寻找有后面括号的字符
    
    				if (*s == map[j][1]){ 	//存在字符于后面的时候
    
    					if (topchar == map[j][0]){ 	//如果找到
    
    						stackPop(&st);	//让其出栈
    						++s;
    						break;
    					}
    					else
    						return false;		//没找到则返回错误
    
    				}
    			}
    		}
    
    	}
    	if (stackEmpty(&st))		//字符寻找完后,如果为空
    		return true;	//则证明成功匹配了,为真
    	return false;
    }

## 2.用队列实现栈 ##

对于这段代码利用了队列的接口,具体看这里的链接: [点击这里][Link 1]

typedef struct{ 
    
    	Queue q;	//初始开辟
    } MyStack;
    
    //创建元素
    MyStack* myStackCreate() { 
    
    	MyStack* ms = (MyStack*)malloc(sizeof(MyStack));	//动态开辟
    	queueInit(&ms->q);		//调用栈的初始化接口
    	return ms;
    }
    
    //实现入栈
    void myStackPush(MyStack* obj, int x) { 
    	queuePush(&obj->q, x);	//直接调用队列的入队就可以实现了
    }
    
    //实现出栈
    int myStackPop(MyStack* obj) { 
    
    	int ret;		//定义整型变量
    	int size = queueSize(&obj->q);		//调用队列的接口计算出大小
    	while (size>1){ 		//当存在很多的时候
    
    		int front = queueFront(&obj->q);	//队列队首元素
    		queuePop(&obj->q);		//出队
    		queuePush(&obj->q, front);	//front进行入队
    		--size;	//循环
    	}
    	ret = queueFront(&obj->q);		//进行入队
    	queuePop(&obj->q);	//出队
    	return ret;
    }
    
    //求栈顶
    int myStackTop(MyStack* obj) { 
    	return queueBack(&obj->q);		//队尾的元素
    }
    
    //判空
    bool myStackEmpty(MyStack* obj) { 
    	return queueEmpty(&obj->q);	//直接调用队列实现的操作
    }
    
    void myStackFree(MyStack* obj) { 
    	queueDestory(&obj->q);		//队列式销毁
    	free(obj);		//释放节点
    }

## 3.用栈实现队列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

对于这段代码利用了栈的接口,具体看这里的链接: [点击这里][Link 2]

typedef struct { 
    
    	stack pushST;		//定义两个栈
    	stack popST;
    } MyQueue;
    
    
    //创建
    MyQueue* myQueueCreate() { 
    
    	MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue));	//动态开辟
    	stackInit(&mq->pushST, 10);	
    	stackInit(&mq->popST, 10);		//对两个进行分别初始化
    	return mq;
    }
    
    //入队
    void myQueuePush(MyQueue* obj, int x) { 
    	stackPush(&mq->pushST, x);	//直接调用入栈操作
    }
    
    //出队
    int myQueuePop(MyQueue* obj) { 
    	int ret;		//定义整形数组
    	if (stackEmpty(&obj->popST)){ 	//判空
    
    		while (stackEmpty(&obj->pushST) != 1){ 	//判空并循环
    
    			int top = stackTop(&obj->pushST);	//找出栈顶
    			stackPop(&obj->pushST);				//出栈
    			stackPush(&obj->popST, top);		//进入到第二个栈内
    		}
    	}
    	ret = stackTop(&obj->popST);	//表示第二个栈的栈顶
    	stackPop(&obj->popST);			//出栈
    	return ret;						//返回值
    }
    
    //最前的元素(和上面的代码一致)
    int myQueuePeek(MyQueue* obj) { 
    	if (stackEmpty(&obj->popST)){ 	//判空
    
    		while (stackEmpty(&obj->pushST) != 1){ 		//循环并判空
    
    			int top = stackTop(&obj->pushST);		//找出栈顶
    			stackPop(&obj->pushST);					//出栈
    			stackPush(&obj->popST, top);			//进入第二个栈
    		}
    	}
    	return ret = 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);	//释放节点
    }

今天讲的有点难度,大家多注意细节,注意对于队列和栈互相转换的理解,已结对前面代码的理解,代价多看看多敲敲,一起加油!!!

[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/113874587
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/8af80211b3c34b358a3bea46787a13d2.png
[Link 2]: https://blog.csdn.net/weixin_46554582/article/details/113874048