一.什么是栈

栈（Stack）是一种遵循“后进先出”（LIFO, Last In First Out）原则的线性数据结构。栈通常有两种实现方式：顺序栈与链式栈，两者各有优劣。但同时从底层来看栈并不是一种新的数据结构，顺序栈的底层依靠数组，链式栈的底层依靠链表。（注意C++中的容器适配器stack，底层默认是deque（双向队列）是一个顺序栈，但是我们也可以将其设置成一个链式栈）

二.顺序栈及其代码实现

原理：基于数组实现，使用一段连续的内存空间来存储元素。
优点：实现简单，访问速度快（内存连续，对CPU缓存友好）。
缺点：需要预先分配固定大小的空间，或者在空间不足时进行扩容，扩容操作有一定开销。

代码实现如图（这里我们借助vector实现，也可以借助array实现，不过需要手动扩容，更繁琐）：

注意这里最好在使用pop_back或back前判断栈是否为空，否则会造成未定义行为。

class stack
{
private:
	vector<int>mpstack;

public:
	stack()
	{ }

public:
	//入栈操作
	void push(int val)
	{
		mpstack.push_back(val);
	}

	//出栈操作
	void pop()
	{
		if (mpstack.empty())
		{
			throw "mpstack is empty";
		}
		mpstack.pop_back();
	}

	//获取栈顶操作
	int top()
	{
		if (mpstack.empty())
		{
			throw "mpstack is empty";
		}
		return mpstack.back();
	}

	//判断栈是否为空
	bool empty()
	{
		return mpstack.empty();
	}
};

三.链式栈及其代码实现

原理：基于链表实现，每个元素（节点）包含数据和指向下一个节点的指针。
优点：动态分配内存，没有固定的容量限制，无需扩容。
缺点：每个节点需要额外的空间存储指针，内存不连续，访问效率略低于数组。

代码实现如图（这里借助了list实现，更为简单，只需将上面的代码中vector改成list即可）：

class stack
{
private:
	list<int>mpstack;

public:
	stack()
	{ }

public:
	//入栈操作
	void push(int val)
	{
		mpstack.push_back(val);
	}

	//出栈操作
	void pop()
	{
		if (mpstack.empty())
		{
			throw "mpstack is empty";
		}
		mpstack.pop_back();
	}

	//获取栈顶操作
	int top()
	{
		if (mpstack.empty())
		{
			throw "mpstack is empty";
		}
		return mpstack.back();
	}

	//判断栈是否为空
	bool empty()
	{
		return mpstack.empty();
	}
};

四.栈的应用场景

栈无论是在学习中，还是在工程中都极其重要，有十分广的应用场景。例如：

函数调用（即函数栈帧，详见：函数栈帧的创建与销毁）：程序在执行函数时，会使用一个“调用栈”来保存函数的局部变量、参数和返回地址等信息。函数调用结束时，对应的信息会从栈中弹出。
括号匹配问题（leetcode-20题）：编译器或解释器使用栈来检查代码中的括号（如 (), [], {}）是否正确配对和嵌套。遇到左括号时压入栈，遇到右括号时从栈中弹出一个左括号进行匹配。
撤销/重做功能：许多软件（如文本编辑器）使用栈来记录用户的操作历史，从而实现撤销（Undo）和重做（Redo）功能。
浏览器前进/后退：当你浏览网页时，访问过的页面URL会被压入一个栈中，点击“后退”按钮时，就从栈中弹出上一个页面的URL。
表达式求值：在计算数学表达式（尤其是将中缀表达式转换为后缀表达式）时，栈是核心工具。
深度优先搜索 (DFS)：在图或树的遍历算法（即非递归实现深度优先搜索，依靠栈实现）中，栈被用来记录访问路径，是实现深度优先搜索的关键。

五.栈的经典问题

1.有效的括号（leetcode20）

核心思路：定义一个栈，遇到左括号就一直入栈，遇到右括号就出栈两个，判断出栈的两个是否匹配。

class Solution {
public:
    bool isValid(string s) {
        stack<char>stk;
        
        if(s.length()==1||s[0]==')'||s[0]==']'||s[0]=='}')
        {
            return false;
        }
       for(auto ch:s)
       {
            if(ch=='('||ch=='['||ch=='{')
            {
                stk.push(ch);
            }
            else if(!stk.empty())
            {
                if(stk.top()=='('&&ch==')'||stk.top()=='['&&ch==']'||stk.top()=='{'&&ch=='}')
                {
                    stk.pop();

                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
       }
     if(stk.empty())
     {
       return true;
        
     }
     else
     {
        return false;
     }
    }
};

2.逆波兰表达式求值（leetcode150）

思路与括号匹配问题很像：定义一个栈，遍历是数字就入栈，是符号就出栈两个，将出栈的两个进行该符号的运算，并将结果再入栈。

class Solution {
public:
int calc(int right,int left,char sigh)
        {
            switch(sigh)
            {
                case '+':
                return left+right;
                  case '-':
                return left-right;  
                case '*':
                return left*right;  
                case '/':
                return left/right;  
              
            }
            return 0;
        }
    int evalRPN(vector<string>& tokens) {
        
        
        stack<int> intstack;
        for(string &str:tokens)
        {
            if(str.size()==1
            &&(str[0]=='+'
            ||str[0]=='-'
            ||str[0]=='*'
            ||str[0]=='/'))
            {
                int right=intstack.top();
                intstack.pop();
                int left=intstack.top();
                intstack.pop();
                intstack.push(calc(right,left,str[0]));
                
            }
            else
            {
                intstack.push(stoi(str));
            }
        }
        return intstack.top();
    }
};

3.中缀转后缀表达式

将普通的表达式转变为逆波兰表达式：核心思路：定义一个栈用于存放字符，定义数字，直接输出，如果栈为空或遍历到（，直接入栈，其他的符号入栈时进行优先级比较，认为所有的符号优先级都比（大，遇到），输出栈中的元素直到（出栈，最后剩余的元素直接全部出栈。

bool Priority(char ch, char topch)
{
	if ((ch == '*' || ch == '/') && (topch == '+' || topch == '-'))
		return true;
	if (topch == '(' && ch != ')')
		return true;
	return false;
}

string MiddleToEndExpr(string exper)
{
	string result;
	stack<char> s;
	for (char ch : exper)
	{
		if (ch >= '0' && ch <= '9')
		{
			result.push_back(ch);
		}
		else
		{


			while (1)
			{
				if (s.empty() || ch == '(')
				{
					s.push(ch);
					break;
				}
				char topch = s.top();
				if (Priority(ch, topch))
				{
					s.push(ch);
					break;
				}
				else
				{
					s.pop();

					if (topch == '(')
						break;
					result.push_back(topch);
				}
			}


		}

	}
	while (!s.empty())
	{
		result.push_back(s.top());
		s.pop();

	}
	return result;
}