数据结构-栈stack（链栈，顺序栈）

柔光的暖阳◎ 2022-05-27 08:22 229阅读 0赞

# 一、栈的概念 #

1）介绍栈STL时已经有写，大家可以翻翻，**传送门：**[点击打开链接][Link 1]

2）没有提过栈底，栈底：在顺序栈中指的是 -1下标，大家自己往下看嘻嘻。

# 二、顺序栈 #

## 1.顺序栈图解 ##

![2018041509515954][]

## 2.特点 ##

**1）空间有限，因为是一次性分配数组空间，有栈满情况。**

**2）出栈入栈是下标top变化，实际出栈只是下标后退一位，实际数值还在数组中，浪费内存。**

## 3.扔一段代码 ##

/*顺序栈*/
    #include<iostream>
    using namespace std;
    #define MaxSize 100
    template <class T>
    class Stack
    {
    private:
    	T Data[MaxSize];
    	int Top;
    public :
    	Stack();
    	int Push(T Elem);    //入栈
    	int Pop();          //出栈
    	int StackEmpty();    //栈空返回1 
    	int StackFull();     //栈满返回1
    	int GetTop(T& TopData);   //取栈顶元素
    };
    template<class T>
    Stack<T>::Stack() :Top(-1) {};
    template<class T>
    int Stack<T>::Push(T Elem)
    {
    	if (StackFull())   //栈满
    		return 0;
    	else
    	{
    		Data[++Top] = Elem;
    		return 1;
    	}
    }
    template<class T>
    int Stack<T>::Pop()
    {
    	if (StackFull())   //栈空
    		return 0;
    	else
    	{
    		--Top;
    		return 1;    //出栈成功
    	}
    }
    template<class T>
    int Stack<T>::StackEmpty()
    {
    	return Top == -1 ? 1 : 0;   //空返回1
    }
    template<class T>
    int Stack<T>::StackFull()
    {
    	return Top == MaxSize - 1 ? 1 : 0;   //满返回1
    }
    template<class T>
    int Stack<T>::GetTop(T& TopData)
    {
    	if (StackEmpty())   //栈空返回代表无栈顶值
    		return 0;
    	else
    	{
    		TopData = Data[Top];
    		return 1;
    	}
    }

# 三、链栈 #

## 1.链栈图解（渣渣灵魂画手又来了） ##

![20180415100358193][]

## 暂停插播一句 ##

这个图对理解链表也有帮助，而且数据结构以链表为基础，链表不熟悉自行传送门:[点击打开链接][Link 2]

## 2.特点： ##

1）和斐林试剂一样现（分）配现用，所以上不封顶没有栈满

2）请时刻注意**栈空是不能操作出栈和取栈顶的** ：）

## 3.扔代码 ##

#include<iostream>	
    using namespace std;
    struct Node
    {
    	int Data;
    	Node* Next;
    };
    class Stack
    {
    private:
    	Node * Top;   //栈顶，入栈是空间一一分配，不考虑栈满
    public:
    	Stack();      //初始栈
    	~Stack();     //析构栈
    	int Push(int Elem_Node);     //入栈
    	int Pop(int& Be_Pop_Elem);     //出栈
    	int Get_Top_Node(int& Get_Top_Elem);    //取栈底
    	int Empty();   //判栈空
    };
    Stack::Stack()
    {
    	Top = NULL;
    }
    Stack::~Stack()
    {
    	Node* Temp_Top = Top;
    	while (Temp_Top)
    	{
    		Top = Top->Next;      //top不断后移，并且定义一个temp储存前方即将删除的节点
    		delete Temp_Top;
    		Temp_Top = Top;
    	}
    }
    int Stack::Push(int Elem_Node)
    {
    	Node* Push_Node = new Node;    //创建新节点
    	Push_Node->Next = Top;      //链接在旧栈顶前面
    	Push_Node->Data = Elem_Node;
    	Top = Push_Node;   //新栈顶
    	return 1;
    }
    int Stack::Pop(int& Be_Pop_Elem)
    {
    	if (Top)
    	{
    		Node* Temp_Top = Top;
    		Be_Pop_Elem = Top->Data;
    		Top = Top->Next;      //top后移，需要先保存旧栈顶以便删除
    		delete Temp_Top;
    		return 1;
    	}
    	else
    		return 0;
    }
    int Stack::Get_Top_Node(int& Get_Top_Elem)
    {
    	if (Top)
    	{
    		Get_Top_Elem = Top->Data;
    		return 0;
    	}
    	else
    		return 0;
    }
    int Stack::Empty()
    {
    	return Top == NULL ? 1 : 0;    //top如果是空说明栈空啦~
    }

# 四、应用(很重要） #

## 1）思想上：递归，例题汉诺塔,传送门：[点击打开链接][Link 3] ##

## 2）括号匹配：[点击打开链接][Link 1] ##

### 应用上面顺序栈类来做下，代码如下： ###

int main()
    {
    	Stack<char> KuoHao;
    	char KuoHao_str[MaxSize];
    	int flag = 1, i = 0;
    	char GetTop_Elem;
    	cin >> KuoHao_str;
    	while (flag&&KuoHao_str[i] != '\0')
    	{
    		switch (KuoHao_str[i])
    		{
    		case '[': case '(': case '{':
    			KuoHao.Push(KuoHao_str[i]);
    			break;
    		case ')':
    			KuoHao.GetTop(GetTop_Elem);
    			if (GetTop_Elem == '(')
    				KuoHao.Pop();
    			else
    				flag = 0;
    			break;
    		case '}':
    			KuoHao.GetTop(GetTop_Elem);
    			if (GetTop_Elem == '{')
    				KuoHao.Pop();
    			else
    				flag = 0;
    			break;
    		case ']':
    			KuoHao.GetTop(GetTop_Elem);
    			if (GetTop_Elem == '[')
    				KuoHao.Pop();
    			else
    				flag = 0;
    			break;
    		default:
    			break;
    		}
    		i++;
    	}
    	if (flag&&KuoHao.StackEmpty())
    		cout << "括号匹配" << endl;
    	else
    		cout << "error" << endl;
    	return 0;

ps：就把上面类代码和实现代码放一起编译就好，怕有人懵逼

## 3）逆波兰表达式：[点击打开链接][Link 4] ##

[Link 1]: https://blog.csdn.net/szu_crayon/article/details/79907455
[2018041509515954]: /images/20220527/e102ccb51fc546cc831c871a79dbba38.png
[20180415100358193]: /images/20220527/88bb1ab955d94d98a1aaa55db09ae088.png
[Link 2]: https://blog.csdn.net/szu_crayon/article/details/79831580
[Link 3]: https://blog.csdn.net/szu_crayon/article/details/79872139
[Link 4]: https://blog.csdn.net/szu_crayon/article/details/79944742