IT评测·应用市场-qidao123.com技术社区

标题: 数据结构栈 [打印本页]

作者: 乌市泽哥 时间: 2025-1-24 20:21
标题: 数据结构栈
目次
前言
一，栈的基本先容与定义
二，数组实现栈
三，链表实现栈
四，栈的应用
总结

前言

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

一，栈的基本先容与定义

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

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

总结

我们先容了栈的基本定义和先容
然后分别用数组和链表来实现栈
末了展现了栈的应用
总的来说，栈就是得当反转某个东西，由于你放进去永世与你拿出来是相反的，还可以使用栈来检查对称性

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)