数据结构 栈
目录
前言
一，栈的基本介绍与定义
二，数组实现栈
三，链表实现栈
四，栈的应用
总结
前言
我们学习了链表，接下来我们就来学习栈，我将会从栈的介绍到实现栈与栈的全部的功能
一，栈的基本介绍与定义
栈（ Last In First Out :最先进来的最先出去)
简称：LIFO
1，栈的属性
最先进来的元素最后进去，可以抽象为我们现实中放东西，每次访问栈的元素的时候，只可以访问站的顶部（任何元素都是只可以从最顶部进行插入和删除等一系列的操作）
可以类似于羽毛球筒，先放进去最后拿出来
如果实在难以理解，可以去阅读我的文章，函数栈帧，这些都是必备的知识
2，栈的定义
栈是一个列表或者集合，它有这样的一种限制，插入，删除只能从一段进行，而这个操作的位置我们称为栈顶
基本操作：
1 push( 插入 ) 2 pop( 弹出 ) 3 top( 返回栈顶元素 ) 4 empty( 是否为空 )
时间复杂度O( n )
3，操作的实际情况
这个就是我们再实际操作栈的过程，每个函数都是有着自己的作用，我们只需要根据函数进行自己想要的操作就好了，STL库里面是有给stack这个类的，可以直接调用并使用
4，实际应用
————可以用来帮助我们执行函数
————递归
————编译器的撤销操作
————编译器里面的括号操作（ 如： { } [ ] ( ) ）
二，数组实现栈
1，插入与删除
伪代码思想
我创建一个数组，此时此刻当数组为空栈的时候，有一个top指针是再-1处的，然后我们插入数据的时候，也是只可以再栈顶插入，只要再A[ top ]处添加元素，我们栈是用来存储临时数据的，不会长期保存，所以我们并不用把刚刚开始初始化在0处的值给删除，直接把栈顶往后移动，利用下一次赋值占上去就好了，这个就是栈的性质
这里我们栈的时间复杂度是O( 1 )
最好的情况是O( 1 )，最坏的情况是O( n )，平均下来就是O( 1 )了
其他的功能
返回栈顶元素
Top( ){ return A[ top ]; }检查是否为空
Isempty( ){ if( top==-1)return true; else return fasle; }2，模拟实现
#include<iostream> using namespace std; #define MAX_SIZE 100 int A[MAX_SIZE]; int top = -1; void push(int x) { if (top == MAX_SIZE) { cout << "stack overflow" << endl; return; } A[++top] = x; } void pop() { if (top == -1) { cout << "NO element to pop" << endl; return; } top--; } int Top() { if (top == -1) { cout << "NO element in the stack" << endl; return 0; } return A[top]; } void IsEmpty() { if (top == -1) { cout << "Stack is empty" << endl; } else { cout << "Stack not is empty" << endl; } } void print() { int i = 0; for (i = top;i >= 0;i--) { cout << A[i] << endl; } } int main() { push(2); push(3); push(78); push(89); IsEmpty(); pop(); print(); return 0; }分别模拟了push插入 pop弹出 top返回栈顶元素 isempty是否为空
push插入： 就是利用数组下角标进行索引，然后把值放入到对应的位置，记得top的值要1改变
pop弹出： 就是利用top--来是实现打印的具体位置，记得栈是不需要删除原本在那里的值的
top返回栈顶： 就是利用return返回A[ top ]即可
isempty检查： 就是我们利用top的值，这个栈顶的值还是原来的那个值就是为空了
三，链表实现栈
我们使用链表的话，由于栈只可以在栈顶进行插入与删除，所以我们要选择一端作为栈顶，所以有两种方法，一种是头插法还有一种是尾插法，由于头插法的时间复杂度是O( 1 )而尾插法的时间复杂度是O( n )所以我们选择头插法
这个实现就是链表的头插法罢了
#include<iostream> #include<new> using namespace std; struct Node { int data; struct Node* Next; }; Node *head; void insert(int a) { Node* temp = new Node; temp->data = a; temp->Next = head; head = temp; } void print() { Node* a = head; while (a != NULL) { cout << a->data << " "; a = a->Next; } } int main() { Node* temp1 = new Node; Node* temp2 = new Node; Node* temp3 = new Node; temp1->data = 1; temp2->data = 2; temp3->data = 3; head = temp1; temp1->Next = temp2; temp2->Next = temp3; temp3->Next = NULL; insert(4); print(); }这个代码很好理解，也就是头插法，很简单
四，栈的应用
1，反转一个字符串
我们用c++来实现栈来打印这个字符串
再STL库里面是提供stack的，所以我们只需要引用这个头文件就好了
#include<iostream> #include<stack> using namespace std; char str[6] = "hello"; void Reverse() { stack<char>S; for (int i = 0;i < 5;i++) { S.push(str[i]); } for (int i = 0;i < 5;i++) { str[i] = S.top(); S.pop(); } } int main() { Reverse(); for (int i = 0;i < 5;i++) cout << str[i]; return 0; }我们即使没有学习过STL库，但是这里可以进行简单的记忆，stack<类型>名字，然后这是一个类，类跟结构体是差不多的，所以直接用成员运算符就好了，里面的函数的作用跟上面所讲的是一样的
当然这个不是最优解对于反转字符串，但是是很简答的，我们还有另外一个方法比这个方法更高效
这里用两个指针分别指向头和尾，然后进行交换，有奇数情况和偶数情况，然后进行交换就好了，这个效率比那个更高，这里就不写代码了，这里主要是讲栈，提供一个思路，虽然时间复杂度都是O( n )，但是空间复杂度这个方法更少
2，反转一个链表
#include<iostream> #include<stack> using namespace std; struct Node { int data; Node* Next; }; Node* head; void Reverse() { Node* temp = head; stack<Node*>S; while (temp != NULL) { S.push(temp); temp = temp->Next; } temp = S.top(); head = temp; while (!S.empty()) { temp->Next = S.top(); S.pop(); temp = temp->Next; } temp->Next = NULL; } void print() { Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->Next; } } int main() { head = NULL; Node* temp1 = new Node; temp1->data = 1; temp1->Next = NULL; Node* temp2 = new Node; temp2->data = 2; temp2->Next = NULL; Node* temp3 = new Node; temp3->data = 3; temp3->Next = NULL; Node* temp4 = new Node; temp4->data = 4; temp4->Next = NULL; temp1->Next = temp2; temp2->Next = temp3; temp3->Next = temp4; head = temp1; Reverse(); print(); }这里我们的stack设置的是Node*类型，那么为什么设置为这个呢？
链表中的每个节点是动态分配的指针对象
在链表结构中，通常每个节点是一个动态分配的结构体或类对象 (Node)，这些节点通过指针相互连接。Node*表示一个指向链表节点的指针。如果你只使用Node而不是Node*，你将需要存储整个节点对象，而不是存储指向它的指针。节省内存开销
如果你用stack<Node>，每次调用S.push(temp)时，整个Node对象都会被拷贝并存储到栈中。这不仅浪费内存，而且对拷贝构造函数或赋值操作符有较高要求。而stack<Node*>只存储指针，效率更高，因为它只存储地址，而不是拷贝整个对象。避免深拷贝问题
如果Node的成员变量中有动态分配的内存（如指针成员变量），使用stack<Node>可能会引发深拷贝问题（对象被复制时，动态内存区域需要正确地处理分配和释放）。而用Node*，栈只存储地址，避免了额外的复杂性。与链表的实现方式一致
在链表中，节点是通过Node*相互连接的，temp->Next的类型也是Node*。为了让栈与链表的数据结构统一，使用stack<Node*>是更合理的选择。总结：
1，你要存储的是这个节点，而不是这个节点的指针
2，如果真的是存储了节点，那么就加大了内存的开销，因为你有添加了一个副本，如果用指针就可以减少内存的开销
3，避免深度拷贝，就是为了减少复杂性，我们把这个栈里面直接存储地址，释放也很好释放
4，书写美观，因为你可以用->这个符号，可以统一
3，检查括号的匹配性
思路：我们只需要把左括号放入栈里面，然后检测右括号，如果最终栈为空或者由括号匹配不上就直接暴异常就好了，因为你放括号的顺序一定是和你匹配括号的顺序是一样的，这里就讲解思路，读者可以下去自己写写代码
总结
我们介绍了栈的基本定义和介绍
然后分别用数组和链表来实现栈
最后展现了栈的应用
总的来说，栈就是适合反转某个东西，因为你放进去永远与你拿出来是相反的，还可以利用栈来检查对称性