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

一、概念

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

1. void push(E):进栈
2. E pop():退栈
3. E peek():查看栈顶元素
4. int getSize():返回栈的元素数量
5. 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;}@Overridepublic boolean push(E e) {try {stack.add(e);}catch (Exception exception){return false;}this.length++;return true;}@Overridepublic 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;}@Overridepublic E peek() {if(this.getLength()==0) return null;E e;try {e = stack.getValueByIndex(this.length - 1);}catch (Exception exception){return null;}return e;}@Overridepublic int getLength() {return this.length;}@Overridepublic 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。总结一下，我们一个需要注意这几个要求：

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