761 字
2 分钟
栈的介绍与多种实现
栈基本介绍与实现
一、基本介绍
栈是一种抽象的数据结构，我们生活中常见的比方说汉诺塔，叠盘子，放羽毛球的筒子，子弹夹。
栈的经典特性就是我们必须要在称之为栈顶那那段插入与删除元素。
简单来说就是先进后出，或者后进先出（LIFO——last in first out）。
本质上来讲，栈是一种特殊的列表。
插入操作被称为Push(x)，删除操作被成为Pop()
还有一些比如Top()用于返回顶部元素。IsEmp()查看是否为空
这些的操作时间复杂度均为O(1)
二、模拟图解
我们来用Push函数操作一下
先压入2,后压入10，可以看到10会作为栈顶，在上面！
我们再执行一下Pop。
可以看到10被移除了栈。
三、实际应用场景
- 之前我们所说的，Function calls,函数调用就是基于栈
- 递归，递归本质也属于函数调用，不过调用的是自己
- 撤回操作，
ctrl+z这种在文本编辑器里面常用的操作也可以理解为基于栈。 - 编译器
四、利用数组实现栈（伪代码）
我们来用伪代码模拟一下
实现方式就是创建一个数组，取0->top的部分作为栈！
对于push操作得先自增再塞入值。对于pop操作，直接让top减一即可，因为后面再加元素的话会覆盖掉。
对于这种情况会有个担忧点：当我们的栈用尽了整个数组导致溢出后该怎么办？、
解决方法就是利用动态数组，我们可以把那个填满的老的数组拷贝到新的数组，接着删除那个老的数组。拷贝的时间复杂度是O(n)。
五、c语言实现
#include<stdio.h>#define MAX_SIZE 101int A[MAX_SIZE];int top =-1;void Push(int x){ if(top==MAX_SIZE-1){//用于处理栈溢出 printf("Error: stackoverflow \n"); return; } top++; A[top]=x;//这两步可以简化为A[++top]=x;}void Pop(){ if(top==-1){ printf("Error: No element to pop \n"); return; } top--;}int Top(){ return A[top];}void Print(){ int i; printf("Stack:"); for(i=0;i<=top;i++){ printf("%d",A[i]); } printf("\n");}
int main(){ Push(2);Print(); Push(5);Print(); Push(10);Print(); Pop();Print(); Push(12);Print();}六、使用链表实现
使用链表实现相对于数组实现的话有一个优点：那就是不会出现溢出，除非你非要炸掉所有内存🫨
实现插入
对于栈来说，时间复杂度一般是O(1)->O(n)
而我们使用尾插法的话，无论是插入还是删除，都得遍历节点，那么时间复杂度就是O(n)!
所以在尾部插入节点并不是一个好的选择！
struct Node{ int data; struct Node *link;};struct Node *top = NULL;//在栈里，我们习惯用top代替headvoid Push(int x){ struct Node *temp=(struct Node*)malloc(sizeof(struct Node)); temp->data=x; temp->link=top; top=temp;}
走到第十行是这样子的。如上图。
接着我们再设置top=temp即可断开原先的top链接，链上新节点。
总结一下插入：创建节点->链接上top所指节点->让top节点连接上所创建的新节点！
实现删除
我们要删除栈顶的节点。
void Pop(){ struct Node *temp; if(top==NULL)return;//处理空栈 temp=top; top=top->link; free(temp);}
总结：只需要创建一个指针指向栈顶->改变top指针->福瑞掉temp指针即可！😋
部分信息可能已经过时