栈

栈是一种先进后出的结构，比如你放书会把书放在最上面，最先放的书在最下面，而你拿书却是从最上面拿，最后放的最先拿到，栈正是怎么一种结构，我们规定最上面的位置叫做栈顶，我们向栈中添加元素是添加到栈顶，向栈中取出元素是从栈顶取出的，我们先来定义一个Stack接口，里面规定了一个栈包含的操作

  1. public interface Stack<E> {
  2.     //向栈中压入一个元素
  3.     void push(E e);
  4.     //将栈顶元素弹出
  5.     E pop();
  6.     //栈是否为空
  7.     boolean isEmpty();
  8.     //获得栈中元素的个数
  9.     int getSize();
  10.     //获得栈顶元素
  11.     E peek();
  12. }

下面我们将使用上面实现的Array来实现一个ArrayStack，我们把数组的最后位置定义为栈顶

  1. public class ArrayStack<E> implements Stack<E> {
  2.     private Array<E> data;
  4.     public ArrayStack(int capacity) {
  5.         data = new Array<>(capacity);
  6.     }
  8.     public ArrayStack() {
  9.         data = new Array<>();
  10.     }
  12.     @Override
  13.     public void push(E e) {
  14.         data.addLast(e);
  15.     }
  17.     @Override
  18.     public E pop() {
  19.         return data.removeLast();
  20.     }
  22.     @Override
  23.     public boolean isEmpty() {
  24.         return data.isEmpty();
  25.     }
  27.     @Override
  28.     public int getSize() {
  29.         return data.getSize();
  30.     }
  32.     @Override
  33.     public E peek() {
  34.         return data.getLast();
  35.     }
  37.     public String toString() {
  38.         StringBuilder res = new StringBuilder();
  39.         res.append("Stack: ");
  40.         res.append("[");
  42.         for (int i = 0; i < data.getSize(); i++) {
  43.             res.append(data.get(i));
  44.             if (i != data.getSize()-1) {
  45.                 res.append(", ");
  46.             }
  47.         }
  48.         res.append("] top");
  50.         return res.toString();
  51.     }
  52. }

上面的代码极其的简单，只要仔细的阅读就可以完全的理解，这里不多做解释。

下面介绍一个有关于栈的题目，此题来自于LeetCode第20题

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

这道题的解题思路是，如果遇到左括号’(‘, ‘[‘, ‘{‘，那么将左括号压入栈中，如果遇到右括号，那么将栈顶的左括号弹出，判断两个括号是否匹配，如果不匹配返回fasle，如果匹配进行下一轮，最后如果字符串遍历完毕，如果栈为空说明匹配成功，如果栈不为空，所以左边的括号多匹配失败，代码如下

  1. import java.util.Stack;
  3. class Solution {
  4.     public boolean isValid(String s) {
  5.         //创建一个空栈
  6.         Stack<Character> stack = new Stack<>();
  8.         //遍历字符串
  9.         for (int i = 0; i < s.length(); i++) {
  10.             char c = s.charAt(i);
  11.             //如果是左括号，则压入栈中
  12.             if (c == '(' || c == '[' || c == '{') {
  13.                 stack.push(c);
  14.             } else {
  15.                 //如果是右括号 先判断栈是否为空
  16.                 if (stack.isEmpty()) {
  17.                     return false;
  18.                 }
  20.                 //获得栈顶的左括号
  21.                 char charTop = stack.pop();
  22.                 //下面三种皆为不匹配的情况
  23.                 if (c == ')' && charTop != '(') {
  24.                     return false;
  25.                 }
  26.                 if (c == ']' && charTop != '[') {
  27.                     return false;
  28.                 }
  29.                 if (c == '}' && charTop != '{') {
  30.                     return false;
  31.                 }
  32.             }
  33.         }
  35.         //这里不能直接返回true 要根据栈是否为空决定返回值
  36.         return stack.isEmpty();
  37.     }
  38. }