资讯专栏INFORMATION COLUMN

我理解的数据结构(二)—— 栈(Stack)

lcodecorex / 2404人阅读

摘要:以数组的最后一个元素当成栈顶元素。解题思路首先,我们可以把左括号直接压入栈,不论是小括号中括号还是大括号。拿出栈顶元素,如果与之右括号不匹配,则返回。如果字符串比较完成,没有返回,则判断栈是否为空。

我理解的数据结构(二)—— 栈(Stack) 一、栈基础

栈是一种线性结构

相比较数组,栈对应的操作是数组的子集

只能从一端添加元素,也只能从同一端取出元素,这一端称为栈顶

栈是一种后进先出的数据结构,LIFO(Last In First Out)

二、栈的应用

Undo操作(撤销)

程序调用所使用的系统栈

三、栈的实现
其实,实现一个栈结构非常简单,我们只需要复用上一节我们自己封装的数组就可以快速的实现一个栈的创建。
以数组的最后一个元素当成栈顶元素。
1. 首先,我们先创建一个栈的借口,里面声明我们需要实现的方法:
public interface Stack {
    boolean isEmpty();
    int getSize();
    // 移除栈顶元素
    E pop();
    // 查看栈顶元素
    E peek();
    // 压入栈
    void push(E ele);
}

注:这里我们有一个peek方法,就是查看栈顶元素,所以我们需要给我们自己封装的数组类添加一个查看最后一个元素的方法:

// 获取最后一个元素
public E getLast() {
    return get(size - 1);
}
2. 封装我们自己的栈
public class ArrayStack implements Stack {

    private ArrayNew array;

    public ArrayStack(int capacity) {
        array = new ArrayNew<>(capacity);
    }

    public ArrayStack() {
        array = new ArrayNew<>();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

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

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

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

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

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        res.append("Stack: [");
        for (int i = 0; i < getSize(); i++) {
            res.append(array.get(i));
            if (getSize() - 1 != i) {
                res.append(", ");
            }
        }
        res.append("] top");
        return res.toString();
    }

}

注:其中的ArrayNew即是我们在上一节自己封装的数组类,不知道的同学可以去查看:
我理解的数据结构(一)—— 不要小看了数组

因为我在ArrayNew中已经实现了动态数组,所以不用考虑栈长度的问题,这样我们就自己封装了一个栈(注释在Stack接口中和ArrayNew类中足够详细)。
四、用栈去解决《有效的括号》
这是一道leetcode上,编号为20的题目,具体题目描述如下:
给定一个只包括 "(",")","{","}","[","]" 的字符串,判断字符串是否有效。

有效字符串需满足:
    1.左括号必须用相同类型的右括号闭合。
    2.左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

解题思路

首先,我们可以把左括号直接压入栈,不论是小括号、中括号还是大括号。

如果拿到的是右括号,则需要做匹配判断。

拿出栈顶元素,如果与之右括号匹配,则pop出栈顶元素。

拿出栈顶元素,如果与之右括号不匹配,则返回false

如果字符串比较完成,没有返回false,则判断栈是否为空。

为空,返回true,括号匹配成功

不为空,返回false

解题代码如下:
public boolean isValid(String s) {

    ArrayStack stack = new ArrayStack<>();

    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;
            }

            char topChar = stack.pop();
            if (c == ")" && topChar != "(") {
                return false;
            }
            if (c == "]" && topChar != "[") {
                return false;
            }
            if (c == "}" && topChar != "{") {
                return false;
            }
        }

    }

    return stack.isEmpty();
}
五、栈的复杂度分析
方法 复杂度
push O(1) 均摊
pop O(1) 均摊
peek O(1)
getSize O(1)
isEmpty O(1)
因为栈的时间复杂度都是O(1),所以栈的性能是很高的。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/29276.html

相关文章

  • 理解数据结构)—— Stack

    摘要:以数组的最后一个元素当成栈顶元素。解题思路首先,我们可以把左括号直接压入栈,不论是小括号中括号还是大括号。拿出栈顶元素,如果与之右括号不匹配,则返回。如果字符串比较完成,没有返回,则判断栈是否为空。 我理解的数据结构(二)—— 栈(Stack) 一、栈基础 栈是一种线性结构 相比较数组,栈对应的操作是数组的子集 只能从一端添加元素,也只能从同一端取出元素,这一端称为栈顶 栈是一种后...

    Charlie_Jade 评论0 收藏0
  • 【Java实现】和队列就是这么简单

    摘要:一前言上一篇已经讲过了链表实现单向链表了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用栈和队列如果写错的地方希望大家能够多多体谅并指正哦,如果有更好的理解的方式也希望能够在评论下留言,让大家学习学习二数据结构栈就是这么简单数据结构 一、前言 上一篇已经讲过了链表【Java实现单向链表】了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用:栈和队列 如果写错的地方希望大家...

    Ethan815 评论0 收藏0
  • 应用——用JavaScript描述数据结构

    摘要:一实现一个栈类基于堆栈的特性,可以用数组做线性表进行存储。出栈出栈同样是利用数组的方法,在数组尾部推出数据。聚合最后,将所有功能聚合后,如下所示,一个堆栈的数据结构就搞定了。堆栈的经典算法应用,首推就是汉诺塔。 栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。 一、实现一个栈类Stack 基于堆...

    Hydrogen 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<