Stack 栈

Stack 栈

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)级别的。链表头或者尾可以作为栈顶。

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

@Override
public E pop() {
    return list.removeFirst();
}
/**    或者    **/
// @Override
// public void push(E e) {
//     list.addLast(e);
// }

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

3.3、查询操作

  查询操作和数组实现相同,但是链表实现的既可以以链表头作为栈顶,也可以使用链表末尾作为栈顶。

@Override
public E peek() {
    return list.getLast();
}
/**    或者    **/
// @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: /archives/stackzhan