数据结构Java版（2）——栈Stack

一、概念

栈也是一种线性数据结构，最主要的特点是入栈顺序和出栈顺序是相反的，操作时只能从栈顶进行操作，在Java中给我们提供了一个泛型栈——Stack，其中最常用的方法有：

void push(E):进栈
E pop():退栈
E peek():查看栈顶元素
int getSize():返回栈的元素数量
isEmpty():检查栈是否为空

二、栈的实现

因为栈也是一种线性结构，所以这里可以利用之前我们写的数组，这里可以用接口的方式来实现我们自己的顺序栈，下面进行代码演示。

数据结构Java版（1）——数组-CSDN博客

栈的接口

public interface Stack_i <Elem>{
    public abstract boolean push(Elem e);
    public abstract Elem pop();
    public abstract Elem peek();
    public abstract int getLength();
    public abstract boolean isEmpty();
}

通过接口的方式，对stack中的方法进行重写，实现功能

public class ArrStack<E> implements Stack_i<E>{
    private MyArray<E> stack;
    private int length;

    public ArrStack() {
        this.stack = new MyArray<>(16);
        length = 0;
    }

    @Override
    public boolean push(E e) {
        try {
            stack.add(e);
        }catch (Exception exception){
            return false;
        }
        this.length++;
        return true;
    }

    @Override
    public E pop() {
        if(this.getLength()==0) return null;
        E e;
        try {
            e = stack.removeByIndex(this.length - 1);
        }catch (Exception exception){
            return null;
        }
        this.length--;
        return e;
    }

    @Override
    public E peek() {
        if(this.getLength()==0) return null;
        E e;
        try {
            e = stack.getValueByIndex(this.length - 1);
        }catch (Exception exception){
            return null;
        }
        return e;
    }

    @Override
    public int getLength() {
        return this.length;
    }

    @Override
    public boolean isEmpty() {
        return this.length==0;
    }
}

对自己的顺序栈进行代码测试

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class testMyStack {
    public static void test(ArrStack<Integer> stack, List<Integer> list){
        Random random = new Random();
        for(int i = 0;i < 10;i++){
            stack.push(random.nextInt(1000));
            System.out.println(stack.peek()+"——现在还有"+stack.getLength()+"个元素");
        }
        Integer temp;
        while ((temp = stack.pop())!=null){
            list.add(temp);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        ArrStack<Integer> stack = new ArrStack();
        test(stack,list);
        for (Integer i:list) {
            System.out.println(i);
        }
    }
}

输出结果

在测试中，我们使用循环对栈先进行入栈，入栈元素分别为377、338、269、107、129、66、101、760、977、786，之后我们又循环出栈到list集合中，出栈顺序为786、977、760、101、66、129、107、268、338、377，从案例中可以看出，栈这种数据结构的特点——先进后出。

三、栈可以解决的问题

1.括号匹配问题

例题：20. 有效的括号 - 力扣（LeetCode）

这种类型的题就适合用栈这种数据结构，这里我用数组集合的做法和栈的做法做比较：

数组做法：

import java.util.ArrayList;

class Solution {
    public static boolean isValid(String s) {
        ArrayList<Character> list = new ArrayList<>();
        int length = 0;
        while(length < s.length()) {
            if(list.size()==0){
                list.add(s.charAt(length++));
                continue;
            }
            if(list.get(list.size()-1).equals('(')&&s.charAt(length)==')'){
                list.remove(list.size()-1);
                length++;
                continue;
            }
            if(list.get(list.size()-1).equals('[')&&s.charAt(length)==']'){
                list.remove(list.size()-1);
                length++;
                continue;
            }
            if(list.get(list.size()-1).equals('{')&&s.charAt(length)=='}'){
                list.remove(list.size()-1);
                length++;
                continue;
            }
            list.add(s.charAt(length++));
        }
        return list.isEmpty();
    }
}

输出结果：

栈做法：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for(int i = 0;i < chars.length;i++){
            if(chars[i]=='('||chars[i]=='['||chars[i]=='{') stack.push(chars[i]);
            if(chars[i]==')'||chars[i]==']'||chars[i]=='}'){
                if(stack.isEmpty()){
                    return false;
                }
                char char_temp = stack.pop();
                if(char_temp=='('&&chars[i]!=')') return false;
                if(char_temp=='['&&chars[i]!=']') return false;
                if(char_temp=='{'&&chars[i]!='}') return false;
            }
        }
        return stack.size()==0;
    }
}

输出结果：

这里简单说明一下这道题的思路，因为要判断括号是否匹配，则左括号和右括号都是一一对应的，若出现了不对应的情况，则视为不匹配，我们可以遇到左括号时进栈而遇到右括号时出栈，此时，若括号匹配，则栈中现在只有左括号，我们只用判断出栈元素是否与当前循环元素匹配就行，循环结束后，栈应该为空。在这其中，只要有一次匹配失败，则返回false。总结一下，我们一个需要注意这几个要求：

入栈元素为左括号
遇到右括号出栈
判断出栈元素与当前循环元素是否匹配
循环结束后，栈是否为空