STL-栈stack(例题：括号匹配）

╰半橙微兮° 2022-05-27 05:06 140阅读 0赞

# \[一\]栈概念： #

## **1.总概：** ##

##  先进后出的线性表,就像一端不开口的羽毛球筒，先放进去的羽毛球只能最后拿出来。    ##

##  **2.栈顶：** ##

##  插入，删除元素的一端。 ##

##  **3.栈底：** ##

## **栈的尾端，见我的博客-数据结构篇之栈，自己写的数组栈才需要讨论栈底。** ##

##  **4.入栈，出栈：** ##

##  **入栈：在栈顶插入元素（意淫放羽毛球的操作）；出栈：删除一个元素（拿出一个羽毛球）。** ##

##  **5.空栈：** ##

## 栈中没有元素。 ##

# \[二\]<stack>功能介绍： #

## 1.头文件 ##

#include<stack>

## 2.定义一个栈 ##

stack<typename> One_Stack;   //定义一个栈，名称为 One_Stack,typename是数据类型，可以是int等

## 3.出栈入栈 ##

One_Stack.push(a_Elem);   //将a_Elem放入栈
    One_Stack.pop();   //出栈

## 4.取栈顶元素 ##

Stack_top_value = One_Stack.top（);   //top返回栈顶元素的值 ，赋值给Stack_top_value

## 5.获得栈内元素个数 ##

Stack_ElemNum = One_Stack.size();

## 6.交换两个栈 ##

One_Stack.swap(another_Stack);   //One_Stack,another_Stack两个栈内容交换

## 7.emplace()： ##

另一个入栈函数：emplace()，大部分情况和push()一样。

## 8.empty（） ##

栈空返回true，否则false，true，false不懂自行百度bool类型。

# \[三\]stack应用：括号匹配 #

/*by 不缩进对齐的渣男  2018/4/12*/
    #include<iostream>	
    #include<stack>
    #define Max_Size 100
    using namespace std;
    stack<char> Bracket;
    void Clear_Stack()    //stack没有清空的成员函数，所以用pop清
    {
    	while (!Bracket.empty())
    		Bracket.pop();
    }
    bool Matching_Bracket(const char* Signal)   //进行括号匹配
    {
    	for (int i = 0; Signal[i] != '\0'; i++)
    	{
    		switch (Signal[i])
    		{
    		case '[':            
    		case '{':
    		case '(':
    			Bracket.push(Signal[i]);      //左括号先进栈
    			break;                 
    		case ')':                       //line 22 to 39  就像消消乐，如果匹配，那么最靠近该类型右括号的肯定是相应类型的左括号，此时左右抵消
    			if (Bracket.top() == '(')      
    				Bracket.pop();           //抵消的操作，出栈这个匹配的左括号
    			else
    				return false;
    			break;
    		case ']':
    			if (Bracket.top() == '[')
    				Bracket.pop();
    			else
    				return false;
    			break;
    		case '}':
    			if (Bracket.top() == '}')
    				Bracket.pop();
    			else
    				return false;
    			break;
    		default:          //忽略其他字符
    			break;
    		}
    	}
    	if (Bracket.empty())
    		return true;
    	else
    		return false;
    }
    int main()
    {
    	int t;
    	char Signal[Max_Size];
    	
    	cin >> t;
    	while (t--)
    	{
    		cin >> Signal;
    		//cout << Signal << endl;
    		if (Matching_Bracket(Signal))       //整个过程只有左括号进栈，如果括号匹配，必定抵消后剩下空栈
    			cout << "yes" << endl;
    		else
    			cout << "no" << endl;
    		Clear_Stack();
    	}
    	return 0;
    }

渣男最近ddl压身，说好的stl-list一拖再拖orz，希望快了，不过考虑先出数据结构的栈和队列嘻嘻。