- 1SpringBoot整合Rabbitmq踩坑记录_springboot rabbitmq port修改不生效
- 2【Python】总结print()多种输出格式_python print 格式
- 32022-09-12Docker基础_creating rootnode subnodes
- 4数据处理（一）数据清洗_如果要按内逻辑清洗数据
- 5Flink流处理案例：实时数据聚合
- 6FPGA中LUT、 LATCH 、FF_lut ff
- 7C#创建Windows服务与服务的安装、卸载_c# serviceinstaller
- 8人工智能该如何学习？详细的AI学习路线与资料推荐_如何学习ai_ai 学习资料
- 9本地访问服务器端的Neo4j数据库_浏览器访问neo4j
- 10Alternative to Receptive field in Transformers and what factors impact it
栈_初始化栈的时空复杂度
赞
踩
栈可以理解为一个有底的瓶子，先进后出，后进先出，这是栈的特点。在栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入、删除数据。当然，也不能简单将其定性为“局限性”。因为特定的数据结构是为了对应特定场景，数组、链表暴露了很多操作接口显得比较灵活，但是使用起来可控性上不强，容易出问题。当某个数据集合只涉及在一端插入和删除数据、且满足先进先出、后进后出的特点时，首选栈。
实现
栈可以使用数组、链表来实现，数组实现的栈叫做顺序栈，链表实现的栈叫做链式栈。
基于数组实现：
public class ArrayStack { private String[] items; //数组 private int count; //栈中元素个数 private int n; //栈大小 //构造中初始化数组，申请大小为n的数组空间 public ArrayStack(int n) { this.n = n; this.items=new String[n]; this.count=0; } //入栈操作 public boolean push(String item){ //数组空间不足，入栈失败 if (count==n) return false; //将item放在下标为count的位置 items[count]=item; ++count; return true; } //出栈操作 public String pop(){ //空栈返回null if (count==0) return null; //返回下标为count-1的数组元素，且个数减一 String tmp = items[count - 1]; --count; return tmp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
基于链表实现：
public class LinkedListStack { private Node top=null; public void push(int value){ Node newNode = new Node(value, null); //判断是否空栈 if (top==null){ top=newNode; }else { newNode.next=top; top=newNode; } } public int pop(){ if (top==null) return -1; int value = top.data; return value; } public void printAll(){ Node p = top; while (p!=null){ System.out.println(p.data+" "); p=p.next; } } private static class Node{ private int data; private Node next; public Node(int data, Node next) { this.data = data; this.next = next; } public int getData(){ return data; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
不管是数组还是链表实现栈，在入栈、出栈的过程中，只需要临时变量存储空间，故时间复杂度为O（1）
基于动态扩容的顺序栈
基于数组实现栈，数组大小是固定的。链表不受这方面的限制，但是链表要存储指针消耗大量的内存。所有要想栈支持动态扩容，就需要数组支持动态扩容。
对于出栈，并不涉及重新申请内存、数据迁移，故时间复杂度为O（1）。对于入栈，当栈内空闲时的时间复杂度为O（1），当空间不够时还要重新申请内存、数据迁移，时间复杂度为O（n）。综合来看，入栈操作的时间复杂度最好为O（1），最差为O（n）。均摊时间复杂度一般都等于最好情况时间复杂度。
函数调用栈
操作系统给每个线程都分配了独立的内存空间，该内存被组织为“栈”结构来存储函数调用时的临时变量。每次进入一个函数，都要将临时变量作为栈帧入栈。当函数调用完成后，将这个函数对应的栈帧出栈。
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
main函数调用了add函数，获取计算结果、与临时变量a相加、打印res的值。
表达式求值应用栈
34+13*9+44-12/3这一句表达式，需要用到两个栈：①保存操作数；②保存运算符；从左向右遍历表达式，遇到数字就压入操作数栈、遇到运算符就与运算符栈的栈顶元素比较。如果当前运算符比栈顶运算符的优先级高，就将当前运算符入栈。否则，从运算符栈中取出栈顶运算符、从操作数栈的栈顶取出2个操作数，进行计算后再讲计算完的结果压入到操作数栈继续比较。
