美文网首页
线性结构:栈

线性结构:栈

作者: WeberLisper | 来源:发表于2021-01-12 10:12 被阅读0次

思路

栈是一种先进后出(First In Last Out, FILO)的数据结构。相对上一篇的数组,它只能在最后添加或删除元素,因此它是数组的一个子集,可复用上一章的数组实现栈结构。

实现

先定义一个栈的接口

public interface Stack<E> {

    int size();

    boolean isEmpty();

    void push(E e);

    E pop();

    E peek();

}

其中pop会将栈顶元素推出,而peek只会读栈顶的值,不会改变栈。

实现数组栈:

public class ArrayStack<E> implements Stack<E> {
    private final Array<E> array;

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

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

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

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

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

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

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Stack ")).append('[');
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }
        res.append(']');
        return res.toString();
    }


}

复杂度分析

由于只能在栈顶操作,因此数组栈的所有方法的复杂度都为O(1)

力扣(20):有效的括号

解题思路是利用栈结构,当碰到左括号时压入栈,碰到又括号时看是否栈顶有与之匹配的左括号。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> 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;
                }
                if (c == ')' && stack.pop() != '(') {
                    return false;
                }
                if (c == ']' && stack.pop() != '[') {
                    return false;
                }
                if (c == '}' && stack.pop() != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

相关文章

  • python数据结构教程 Day3

    本节重点: 线性结构介绍 栈结构介绍 栈结构ADT实现 栈在问题中的应用 一、线性结构 定义: 线性结构是一种有序...

  • 栈的顺序存储结构

    栈的顺序存储结构 栈是一种重要的线性结构,可以这样讲,栈是线性表的一种具体形式。 栈这种后进先出的数据结构应用是非...

  • 3-玩转数据结构-栈和队列

    我们会介绍两个全新的线性数据结构,栈与队列。 栈Stack 栈也是一种线性结构;相比数组,栈对应的操作是数组的子集...

  • 栈和队列

    栈和队列是两种应用非常广泛的数据结构,它们都来自线性表数据结构,都是“操作受限”的线性表。 栈 栈(Stack):...

  • 数据结构之栈

    栈和队列都属于线性数据的逻辑存储结构 概念 栈(stack)是一种线性数据结构,栈中的元素只能先入后出(First...

  • 线性结构--栈

    特点: 栈是一种线性结构 相比数组,栈对应的操作是数组的子集 只能从一端添加元素,也只能从同一端取出元素 是一种后...

  • 线性结构:栈

    思路 栈是一种先进后出(First In Last Out, FILO)的数据结构。相对上一篇的数组,它只能在最后...

  • 数据结构(线性结构 栈与队列)

    栈与队列都是特殊的线性表,它们也是线性结构。用户可以采用顺序存储结构和链式存储结构两种方式来存储。栈和队列结构是各...

  • 04栈和队列(特殊的线性表)

    1.栈 1.栈 栈:栈是限定仅在表尾进行插入和删除操作的特殊的线性表。线性表按照存储结构分有顺序存储结构实现的顺序...

  • 数据结构与算法掌握这些就够了

    数据结构 线性结构数组、链表、栈、队列 非线性多维数组、树、图 1. 栈 后进先出,可以处理递归调用实际应用:字符...

网友评论

      本文标题:线性结构:栈

      本文链接:https://www.haomeiwen.com/subject/yjssaktx.html