Java底层实现Stack栈

Stack 栈

Github LiYangSir
Home https://quguai.cn
Language Java

1、Stack栈概述

  栈这个数据结构有着自己的性质,也就是 先进后出,后进先出 的结构。最经典的就是调用函数这一块。不断向栈中加入缓存,最后执行完的函数会回调用放在栈顶的缓存。和它类似的就是队列的数据结构。队列有着先进先出,后进后出的结构。两者应用不同的场景。

  这里将栈设计为Java接口,目的是实现栈的底层有很多。例如数组、链表、二叉树等等。他们都将调用这个Stack接口。

涉及的函数方法:

涉及的函数不多,所以实现起来也会比较简单。

2、Stack栈的实现——基于动态数组

  至于动态数组包含什么方法,可以参考Array动态数组这一片文章。

2.1、Stack 接口

  包含获取Stack栈内元素的个数、是否为空、进出栈操作、以及查看栈顶元素。

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek(); //观察栈顶元素,但不取出
}

2.2、基本操作

  重载接口函数,返回底层数组下的大小和是否为空。

@Override
public int getSize() {
    return array.getSize();
}

@Override
public boolean isEmpty() {
    return array.isEmpty();
}

2.3 进出栈操作

  进栈操作主要是围绕先进后出,后进先出的原则,即向数组后添加元素和在数组后取出元素。之所以在数组后取出元素,在Array动态数组这一片文章中的时间复杂度分析得出,向数组后添加和取出元素都是O(1)级别的复杂度。所将数组末尾作为栈顶

@Override
public void push(E e) {
    array.addLast(e);
}

@Override
public E pop() {
    return array.removeLast();
}

2.4、查询操作

  查询操作就是查看栈顶的元素。由于默认数组末尾为栈顶,所以查询操作就是查看数组最后一位元素是啥。

@Override
public E peek() {
    return array.getLast();
}

3、Stack栈的实现——基于链表实现

  接口和数组实现一样,这也充分体现了接口的好处。只不过底层是链表的形式存储数据。

3.1、基本操作

  重载接口函数,返回底层数组下的大小和是否为空。和数组的实现相同。

@Override
public int getSize() {
    return list.getSize();
}

@Override
public boolean isEmpty() {
    return list.isEmpty();
}

3.2 进出栈操作

  进出栈操作和数组实现就不一样啦。虽然表面上看上去相同,实则不同。Array数组最好使用向数组末尾添加元素来降低复杂度。对于单链表来说,向头部进行所有操作的时间复杂度相同,都是O(1)级别的。但是向链尾进行的操作就是O(N)级别。所以一般都是以链表头作为栈顶

@Override
public void push(E e) {
    list.addFirst(e);
}

@Override
public E pop() {
    return list.removeFirst();
}

3.3、查询操作

  查询操作和数组实现相同,但是链表实现的一般以链表头作为栈顶。

@Override
public E peek() {
    return list.getFirst();
}

4、时间复杂度分析

  由于栈的结构比较简单,时间复杂度主要依靠底层的实现。根据下表可以得出,基于链表和基于数组的时间复杂度均为 O(1) 级别。
||动态数组|链表|
|:---:|:---:|:---:|
|进栈操作|O(1)|O(1)|
|出栈操作|O(1)|O(1)|
|查询操作|O(1)|O(1)|

5、栈的另一个实际应用——括号匹配

  在实际开发过程中,括号匹配是我们经常遇到的问题。{ ( [ ] ) } 这种就是可以正确的。对于这种 { [ ] ) } 就是不匹配的问题。应用栈的结构就可以轻松解决这个问题。对于 { [ ( 执行进栈操作。对于 ) } ]则进行出栈操作,判断出栈的元素是否和 ) } ]的对立符号是否匹配。
以匹配 { ( ) } 为例:

以匹配 { ( ] } 为例:

public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);  //将字符一个一个提出来
            if (c == '(' || c == '[' || c == '{')  //入栈的元素
                stack.push(c);
            else {
                if (stack.isEmpty())
                    return false;
                //观察出栈的元素是否和字符串中的字符对立。
                if (c == ')' && stack.pop() != '(') 
                    return false;
                if (c == ']' && stack.pop() != '[')
                    return false;
                if (c == '}' && stack.pop() != '{')
                    return false;
            }
        }
        return stack.isEmpty();
    }

更多精彩内容,大家可以转到我的主页:主页
或者关注我的微信公众号:TeaUrn
或者扫描下方二维码进行关注。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://quguai.cn/archives/j-a-v-a-di-ceng-shi-xian-s-t-a-c-k-zhan