java栈

栈是一个先进后出的数据结构，想要自己实现一个栈，要求这个栈具有push()，pop()——返回栈顶并出栈，peek()——返回栈顶不出栈，isEmpty()等方法。

1.1、手动实现一个栈的多种方式

采用数组来实现栈

import java.util.Arrays;

/**
 * @author George
 * @project testDemo
 * @package abc
 * @date 2021/9/25 19:59
 * @since 1.0
 */
class Stack1<T> {

    // 实现栈的数组
    private Object[] stack;
    // 数组大小
    private int size;

    Stack1(){
        stack=new Object[10];
    }

    // 判断数组是否为空
    public boolean isEmpty(){
        if (size==0){
            return true;
        }else{
            return false;
        }
    }

    // 返回栈顶元素
     public T peek(){
        T t=null;
        if (size>0){
            t= (T) stack[size-1];
        }
        return t;
     }

     // 返回栈顶并出栈
     public T pop(){
        T t=peek();
        if(size>0){
            stack[size-1]=null;
            size--;
        }
        return t;
     }

     // 扩容
    public void expandCapacity(int size){
        int len=stack.length;
        if (size>len){
            size=size*3/2+1;
            stack= Arrays.copyOf(stack,size);
        }
    }

    public void push(T t){
        expandCapacity(size+1);
        stack[size]=t;
        size++;
    }
}

public class ArrayStack {
    public static void main(String[] args) {
        Stack1<String> stringStack1=new Stack1<>();
        System.out.println(stringStack1.peek());
        System.out.println(stringStack1.isEmpty());
        stringStack1.push("java");
        stringStack1.push("chenyc2021@qq.com");
        stringStack1.push("gogogo");
        System.out.println(stringStack1.pop());
        System.out.println(stringStack1.isEmpty());
        System.out.println(stringStack1.peek());
    }
}

采用链表来实现

/**
 * @author George
 * @project testDemo
 * @package abc
 * @date 2021/9/26 0:49
 * @since 1.0
 */
class Stack2<T> {
    // 定义一个链表
    class Node<T> {
        private T t;
        private Node next;
    }

    private Node<T> head;

    // 构造函数
    Stack2() {
        head = null;
    }

    // 入栈
    public void push(T t) {
        if (t == null) {
            throw new NullPointerException("参数不能为空");
        }
        if (head == null) {
            head = new Node<T>();
            head.t = t;
            head.next = null;
        } else {
            Node<T> temp = head;
            head = new Node<T>();
            head.t = t;
            head.next = temp;
        }
    }

    // 出栈
    public T pop() {
        T t = head.t;
        head = head.next;
        return t;
    }

    // 栈顶元素
    public T peek() {
        T t = head.t;
        return t;
    }

    //判断栈是否为空
    public boolean isEmpty() {
        if (head == null) {
            return true;
        } else {
            return false;
        }
    }
}

public class LinkStack {
    public static void main(String[] args) {
        Stack2 stack = new Stack2();
        System.out.println(stack.isEmpty());
        stack.push("Java");
        stack.push("is");
        stack.push("beautiful");
        System.out.println(stack.peek());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
    }
}

采用LinkedList实现栈

 import java.util.LinkedList;

/**
 * @author George
 * @project testDemo
 * @package abc
 * @date 2021/9/26 9:39
 * @since 1.0
 */

class Stack3<T>{
    // 构建一个linkedLIst集合
    private LinkedList<T> ll=new LinkedList<>();

    // 判断栈是否为空
    public boolean isEmpty(){
        return ll.isEmpty();
    }

    // 入栈
    public void push(T t){
        ll.addFirst(t);
    }

    //出栈
    public T pop(){
        return ll.removeFirst();
    }

    // 栈顶元素
    public T peek(){
        T t=null;
        if (!ll.isEmpty()){
            t=ll.getFirst();
        }
        return t;
    }

}
public class LinkedStack {
    public static void main(String[] args) {
        Stack3<String> stringStack3=new Stack3<>();
        System.out.println(stringStack3.isEmpty());
        System.out.println(stringStack3.peek());
        stringStack3.push("java");
        stringStack3.push("is");
        stringStack3.push("beautiful");
        System.out.println(stringStack3.peek());
        System.out.println(stringStack3.pop());
        System.out.println(stringStack3.isEmpty());
        System.out.println(stringStack3.peek());
    }
}

1.2、栈的应用

在java中，栈是一种很重要的数据结构，如以下的很多场景都应用到了栈

符号匹配
中缀表达式变为后缀表达式
计算后缀表达式
实现函数的嵌套调用
HTML和XML中的标签匹配
网页浏览器中以访问界面的历史记录

例如：

符号匹配
在编写程序的过程中，我们经常会遇到诸如圆括号“()”与花括号“{}”，这些符号都必须是左右匹配的，这就是我们所说的符合匹配类型，当然符合不仅需要个数相等，而且需要先左后右的依次出现，否则就不符合匹配规则，如“)(”，明显是错误的匹配，而“()”才是正确的匹配。有时候符合如括号还会嵌套出现，如“9-(5+(5+1))”,而嵌套的匹配原则是一个右括号与其前面最近的一个括号匹配，事实上编译器帮我检查语法错误是也是执行一样的匹配原理，而这一系列操作都需要借助栈来完成，接下来我们使用栈来实现括号”()”是否匹配的检测。
判断原则如下（str=”((5-3)*8-2)”）：

a.设置str是一个表达式字符串，从左到右依次对字符串str中的每个字符char进行语法检测，如果char是，左括号则入栈，如果char是右括号则出栈(有一对匹配就可以去匹配一个左括号，因此可以出栈)，若此时出栈的字符char为左括号，则说明这一对括号匹配正常，如果此时栈为空或者出栈字符不为左括号，则表示缺少与char匹配的左括号，即目前不完整。

b.重复执行a操作，直到str检测结束，如果此时栈为空，则全部括号匹配，如果栈中还有左括号，是说明缺少右括号。

实现代码如下：

public class CheckExpression {

  public static String isValid(String expstr)
  {
      //创建栈
      LinkedStack<String> stack = new LinkedStack<>();

      int i=0;
      while(i<expstr.length())
      {
          char ch=expstr.charAt(i);
          i++;
          switch(ch)
          {
              case '(': stack.push(ch+"");//左括号直接入栈
                  break;
              case ')': if (stack.isEmpty() || !stack.pop().equals("(")) //遇见右括号左括号直接出栈
                  return "(";
          }
      }
      //最后检测是否为空,为空则检测通过
      if(stack.isEmpty())
          return "check pass!";
      else
          return "check exception!";
  }

  public static void main(String args[])
  {
      String expstr="((5-3)*8-2)";
      System.out.println(expstr+"  "+isValid(expstr));
  }
}