数据结构 栈
目次前言
一，栈的基本先容与定义
二，数组实现栈
三，链表实现栈
四，栈的应用
总结
前言
我们学习了链表，接下来我们就来学习栈，我将会从栈的先容到实现栈与栈的全部的功能
一，栈的基本先容与定义
栈（ Last In First Out :最先进来的最先出去)
简称：LIFO
1，栈的属性
最先进来的元素末了进去，可以抽象为我们现实中放东西，每次访问栈的元素的时候，只可以访问站的顶部（任何元素都是只可以从最顶部进行插入和删除等一系列的操纵）
https://i-blog.csdnimg.cn/direct/ecb0794e744c4dbc8125df746eeff4d1.png可以类似于羽毛球筒，先放进去末了拿出来
假如实在难以明白，可以去阅读我的文章，函数栈帧，这些都是必备的知识
2，栈的定义
栈是一个列表或者集合，它有如许的一种限制，插入，删除只能从一段进行，而这个操纵的位置我们称为栈顶
基本操纵：
1 push( 插入 ) 2 pop( 弹出 ) 3 top( 返回栈顶元素 ) 4 empty( 是否为空 )
时间复杂度O( n )
3，操纵的实际环境
https://i-blog.csdnimg.cn/direct/634c8385389e4578b1815862acb393d0.png
这个就是我们再实际操纵栈的过程，每个函数都是有着本身的作用，我们只需要根据函数进行本身想要的操纵就好了，STL库内里是有给stack这个类的，可以直接调用并使用
4，实际应用
————可以用来帮助我们实验函数
————递归
————编译器的撤销操纵
————编译器内里的括号操纵（ 如： { } [ ] ( ) ）
二，数组实现栈
1，插入与删除
伪代码头脑
https://i-blog.csdnimg.cn/direct/2dffccd521ef44488d8a13793b0dcc6a.png
我创建一个数组，此时此刻当数组为空栈的时候，有一个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;
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;
}
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 << 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 )以是我们选择头插法
https://i-blog.csdnimg.cn/direct/92f87e7b657845ff8d5be54ed18996ba.png
这个实现就是链表的头插法罢了
#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，反转一个字符串
https://i-blog.csdnimg.cn/direct/127bbc46e98740f4bfc0e8dac762eab7.png
我们用c++来实现栈来打印这个字符串
再STL库内里是提供stack的，以是我们只需要引用这个头文件就好了
#include<iostream>
#include<stack>
using namespace std;
char str = "hello";
void Reverse() {
stack<char>S;
for (int i = 0;i < 5;i++) {
S.push(str);
}
for (int i = 0;i < 5;i++) {
str = S.top();
S.pop();
}
}
int main() {
Reverse();
for (int i = 0;i < 5;i++)
cout << str;
return 0;
}我们即使没有学习过STL库，但是这里可以进行简单的记忆，stack<类型>名字，然后这是一个类，类跟结构体是差不多的，以是直接用成员运算符就好了，内里的函数的作用跟上面所讲的是一样的
当然这个不是最优解对于反转字符串，但是是很简答的，我们还有另外一个方法比这个方法更高效
https://i-blog.csdnimg.cn/direct/b8c48ad90440446f9b205c905da46a82.png
这里用两个指针分别指向头和尾，然后进行交换，有奇数环境和偶数环境，然后进行交换就好了，这个服从比谁人更高，这里就不写代码了，这里重要是讲栈，提供一个思路，虽然时间复杂度都是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，检查括号的匹配性
思路：我们只需要把左括号放入栈内里，然后检测右括号，假如终极栈为空或者由括号匹配不上就直接暴非常就好了，由于你放括号的顺序一定是和你匹配括号的顺序是一样的，这里就讲解思路，读者可以下去本身写写代码
总结
我们先容了栈的基本定义和先容
然后分别用数组和链表来实现栈
末了展现了栈的应用
总的来说，栈就是得当反转某个东西，由于你放进去永世与你拿出来是相反的，还可以使用栈来检查对称性
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]