文章目录

栈Stack手写一个栈利用栈解决括号匹配问题时间复杂度分析

栈Stack

栈也是一种线性结构，相比数组，栈对应的操作是数组的子集 栈是一种后进先出的数据结构，只能从一端添加元素，也只能从一端取出元素，这一端称为栈顶

手写一个栈

创建一个栈接口，包含哪些具体方法。

public interface Stack<E> { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek(); }

利用动态数组，实现一个栈结构

public class ArrayStack<E> implements Stack<E> { Array<E> array; public ArrayStack(int capacity) { array = new Array<E>(capacity); } public ArrayStack() { // 或者this(10); array = new Array<E>(); } /** * 获取元素个数 * * @return */ @Override public int getSize() { 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(); } /** * 获取容量 * * @return */ public int getCapacity() { return array.getCapacity(); } /** * 查看栈顶元素 * * @return */ @Override public E peek() { return array.getLast(); } @Override public String toString() { StringBuilder result = new StringBuilder(); result.append("Stack : ["); for (int i = 0; i < array.getSize(); i++) { result.append(array.get(i)); if(i!=array.getSize()-1){ result.append(", "); } } result.append("] top"); return result.toString(); } }

测试：

public class Test { public static void main(String[] args) { ArrayStack<Integer> stack = new ArrayStack<>(); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); } }

利用栈解决括号匹配问题

/** * 栈解决括号匹配问题 */ public class Solution { public boolean isValid(String s) { Stack<Character> characterStack = new Stack<>(); char[] chars = s.toCharArray(); for (int i = 0; i < chars.length; i++) { char c = chars[i]; if (c == '(' || c == '[' || c == '{') { characterStack.push(c); } else { if (characterStack.isEmpty()) { return false; } Character popChar = characterStack.pop(); if (c == ')' && popChar != '(') { return false; } if (c == ']' && popChar != '[') { return false; } if (c == '}' && popChar != '{') { return false; } } } return characterStack.isEmpty(); } }

时间复杂度分析

因为栈的操作都是针对栈顶元素，就算是有扩容操作，按照均摊复杂度来计算，也是 O(1) 的