自己动手写Stack

什么是栈

我觉得栈是一个很简单的概念，栈是一种后进先出的数据结构(Last In And First Out)，大家都见过装羽毛球的筒吧，你会发现当你装完羽毛球之后第一个拿出来的肯定是最后一个放进去的。其实这就是栈，它是一种线性结构，我们学习了数组其实就很容易理解栈了。

为什么呢？我们可以先想一下，对于栈这样的数据结构，我们能对它进行什么样的操作。其实也就是入栈（将一个羽毛球放进去），出栈（将一个羽毛球拿出来），判断栈是否为空（羽毛球筒里面有没有羽毛球），计算栈的大小（计算羽毛球筒里有多少个羽毛球），获取栈顶元素（获取羽毛球筒中最上面的羽毛球）。无非就是这几个操作。所以我们现在可以定义栈的接口了，如下面代码。

/**
 * @author Lin
 * @date 2019-04-15 12:34
 **/
public interface Stack<E> {

  /**
   * 获取栈的大小
   * @return 大小
   */
  int getSize();

  /**
   * 判断栈是否为空
   * @return 布尔
   */
  boolean isEmpty();

  /**
   * 将元素放入栈
   * @param e 元素
   */
  void push(E e);

  /**
   * 出栈
   * @return 出栈的元素
   */
  E pop();

  /**
   * 获得栈最上面的元素
   * @return 元素
   */
  E peek();
}

栈与数组的关系

之前我的一篇博客介绍了如何实现动态数组，那个动态数组中我们实现了添加删除元素，计算数组大小，判断数组是否为空，获取数组的元素等方法。其实我们对栈的操作也就是对数组操作的子集，计算大小，判断为空我们可以直接使用数组的方法，添加元素对于栈来说就是在末尾添加元素，删除就是删除末尾元素，而获取元素就是获取最后一个元素。所以我们可以直接定义我们的ArrayStack类了（这个类是实现了刚刚的Stack接口的）

/**
 * @author Lin
 * @date 2019-04-15 13:18
 **/
public class ArrayStack<E> implements Stack<E> {

  /**
   * 通过数组实现栈
   */
  private Array<E> array=new Array<>();

  @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();
  }

  //上篇博客中没有getLast和getFirst方法
  //这里是我后面添加的，其实实现这个方法很简单，只要固定index就行了
  @Override
  public E peek() {
    return array.getLast();
  }

  //这里重写toString方法为了后面测试能清楚显示
  @Override
  public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    stringBuilder.append("Stack [");
    for (int i = 0; i < this.getSize(); i++) {
      if (i != this.getSize() - 1) {
        stringBuilder.append(array.get(i)).append(",");
      }else {
        stringBuilder.append(array.get(i)).append("]pop");
      }
    }
    return stringBuilder.toString();
  }
}

栈的一些应用场景

word和一些IDE中的撤销功能

将用户的操作放入栈中，当实行撤销操作的时候把用户最近的操作撤销。

程序调用的系统栈

比如我们调用A方法需要调用B方法，调用B方法的时候我们需要调用C方法，这时候我们C方法执行完了之后我们系统是不知道我们下面应该执行什么方法的，所以这时候栈就登场了，当我们执行A方法需要调用B方法的时候我们将这时候跳转执行前的方法和代码行数记录到栈中（这时候我们执行的是A方法的第二行代码调用了B
方法，所以我们把A2存入栈中）。同理，我们运行B方法的时候在第二行调用了C方法，我们就把B2存入栈中，之后我们C方法执行完之后系统就看栈中有没有还需要返回的方法，如果有就跳回指定的方法的代码行数，比如C方法执行完，我们栈中有B2，我们就跳回B2执行并且把栈顶元素删除，接着我们B方法执行完了，我们看栈中还有A2，我们就跳转到A2执行代码并且把A方法执行完查看栈中没有元素的时候我们就把整个A方法执行完成了。

关于栈的算法题目

在leetcode中有一道使用栈解决的简单题目

题目是这样的：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

思考一下题目，其实就可以和栈结合起来了，我们将给出的串进行遍历获取字符，我们判断字符是否为”{“,”[“,”(“,为这三个我们就把字符存入栈中，如果不是我们就把它和栈素比较是否匹配，如果不匹配那么直接返回false。大致思是这样，具体细节代码注释里有详细解释。
代码如下：

class Solution {
  public boolean isValid(String s) {
    //创建一个stack
    Stack<Character> stack=new Stack<>();
    //声明栈顶元素
    Character topCharacter;
    //循环遍历字符串
    for (int i=0;i<s.length();i++){
      //获取某个字符
      Character character=s.charAt(i);
      //如果该字符等于'{'或'['或'('的时候存入栈中
      if (character=='{'||character=='['||character=='('){
        stack.push(character);
        //直接进入下一层循环
        continue;
      }
      //如果不是，那么就是与之相对的了
      else {
        //首先判断栈是否为空
        //因为如果栈中没有元素且这个字符是右边的括号
        //那么这个字符串肯定不符合要求
        if (stack.isEmpty()){
          return false;
        }else {
          //获取栈顶元素
          topCharacter=stack.pop();
          //判断栈顶元素是否和该元素匹配，如不匹配直接false
          if (character=='}'&&topCharacter!='{'){
            return false;
          }else if (character==']'&&topCharacter!='['){
            return false;
          }else if (character==')'&&topCharacter!='('){
            return false;
          }
        }
      }
    }
    //如果循环都是正确的，那么还要判断栈是否为空
    //因为"{","["这种类型的情况都是错误的
    //但是前面没有考虑到，所以只要判断后面直接没有元素匹配
    //也就是栈是否不为空
    return stack.isEmpty();
  }

}