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

本文主要是介绍数据结构-栈stack（链栈，顺序栈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、栈的概念

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

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

二、顺序栈

1.顺序栈图解

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();     //栈满返回1int 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.链栈图解（渣渣灵魂画手又来了）

暂停插播一句

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

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;}elsereturn 0;
}
int Stack::Get_Top_Node(int& Get_Top_Elem)
{if (Top){Get_Top_Elem = Top->Data;return 0;}elsereturn 0;
}
int Stack::Empty()
{return Top == NULL ? 1 : 0;    //top如果是空说明栈空啦~
}

四、应用(很重要）

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

2）括号匹配：点击打开链接

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

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();elseflag = 0;break;case '}':KuoHao.GetTop(GetTop_Elem);if (GetTop_Elem == '{')KuoHao.Pop();elseflag = 0;break;case ']':KuoHao.GetTop(GetTop_Elem);if (GetTop_Elem == '[')KuoHao.Pop();elseflag = 0;break;default:break;}i++;}if (flag&&KuoHao.StackEmpty())cout << "括号匹配" << endl;elsecout << "error" << endl;return 0;

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