[数据结构与算法]数据结构-栈

3、栈

本文使用的数组参考数据结构-数组

3.1 定义一个栈接口

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

3.2 实现接口

public class ArrayStack<E> implements Stack<E> {
	//下面使用的接口均是数据结构-数组文章中使用的接口
    public Array<E> array;

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

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

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

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

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

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

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

    @Override
    public String toString() {
        return "ArrayStack{" +
                "array=" + array +
                '}';
    }
}

3.3 测试

public class Main {
    public static void main(String[] args) {
        ArrayStack<Integer> arrayStack  = new ArrayStack<>();

        for(int i = 0; i <5; i++) {
            arrayStack.push(i);
            System.out.println(arrayStack);
        }

        arrayStack.pop();
        System.out.println(arrayStack);
    }
}

3.4 栈的应用-括号匹配

import java.util.Stack;
public class Solution {
    public boolean isValid(String s) {
        //使用java自带的Stack，将Stack替换成自己实现的ArrayStack也可以
        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;
                char topC = stack.pop();
                if(c == '}' && topC!='{')
                    return false;
                 if(c == ')' && topC!= '(')
                    return false;
                 if(c == ']' && topC!= '[')
                    return false;
            }
        }
		//判断是否为空，为空则为true，否则是false
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValid("()[]"));
    }
}