目录

前言

一，栈的基本介绍与定义

二，数组实现栈

三，链表实现栈

 四，栈的应用

总结

---

前言

我们学习了链表，接下来我们就来学习栈，我将会从栈的介绍到实现栈与栈的全部的功能

---

一，栈的基本介绍与定义

栈（ 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，检查括号的匹配性

思路：我们只需要把左括号放入栈里面，然后检测右括号，如果最终栈为空或者由括号匹配不上就直接暴异常就好了，因为你放括号的顺序一定是和你匹配括号的顺序是一样的，这里就讲解思路，读者可以下去自己写写代码

---

总结

我们介绍了栈的基本定义和介绍

然后分别用数组和链表来实现栈

最后展现了栈的应用

总的来说，栈就是适合反转某个东西，因为你放进去永远与你拿出来是相反的，还可以利用栈来检查对称性