当前位置:   article > 正文

栈_初始化栈的时空复杂度

初始化栈的时空复杂度

栈可以理解为一个有底的瓶子,先进后出,后进先出,这是栈的特点。在栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入、删除数据。当然,也不能简单将其定性为“局限性”。因为特定的数据结构是为了对应特定场景,数组、链表暴露了很多操作接口显得比较灵活,但是使用起来可控性上不强,容易出问题。当某个数据集合只涉及在一端插入和删除数据、且满足先进先出、后进后出的特点时,首选栈。

实现

栈可以使用数组、链表来实现,数组实现的栈叫做顺序栈,链表实现的栈叫做链式栈。

基于数组实现:

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个操作数,进行计算后再讲计算完的结果压入到操作数栈继续比较。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/900641
推荐阅读
相关标签
  

闽ICP备14008679号