概述

它是一种数据结构,数据既可以进入到栈中,又可以从栈中出去

栈是一种基于先进后出$(FILO)$的数据结构,是一种只能在一端进行插入和删除操作的特殊线性表,它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读取数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出)

我们称数据进入栈的动作为压栈,数据从栈中出去的动作为弹栈
栈概述.png

栈的实现

栈API设计
类名Stack
构造方法Stack():创建Stack对象
成员方法1.public boolean isEmpty():判断栈是否为空,是返回true,否返回false 2.public in size():获取栈中元素的个数 3.public T pop():弹出栈顶元素 4.public void push(T t):向栈中压入元素
成员变量1.private Node head:记录首节点 2.private int N:当前栈的元素个数
成员内部类private class Node:节点类
代码实现

Stack

public class Stack<T> implements Iterable<T> {

  /**
   * 记录头结点
   */
  private Node head;
  /**
   * 栈中元素的个数
   */
  private int N;


  private class Node {

    public T item;
    public Node next;

    public Node(T item, Node next) {
      this.item = item;
      this.next = next;
    }
  }

  public Stack() {
    //初始化头结点与元素个数
    this.head = new Node(null, null);
    this.N = 0;
  }

  /**
   * 判断当前栈中元素是否为0
   */
  public boolean isEmpty() {
    return N == 0;
  }

  /**
   * 获取栈中元素的个数
   */
  public int siza() {
    return N;
  }

  /**
   * 把t元素压入栈
   */
  public void push(T t) {
    //找到头结点指向的第一个节点
    Node OldFirst = head.next;
    //创建要插入的的节点
    Node newNode = new Node(t, null);
    //将头结点重新指向要插入的节点
    head.next = newNode;
    //将要插入的节点指向原来的第一个节点
    newNode.next = OldFirst;
    //元素个数++
    N++;
  }

  /**
   * 弹出栈顶的元素
   */
  public T pop() {
    //直接将头结点指向第二个节点,第一个节点指向null,但这里特别需要注意,如果栈里的个数没有了,就会指向空指针,不安全
    Node OldFirst = head.next;
    if (OldFirst == null) {
      return null;
    }
    head.next = OldFirst.next;
    //元素个数--
    N--;
    return OldFirst.item;
  }

  @Override
  public Iterator<T> iterator() {
    return new SIterator();
  }

  private class SIterator implements Iterator {

    private Node n;

    public SIterator() {
      this.n = head;
    }

    @Override
    public boolean hasNext() {
      return n.next != null;
    }

    @Override
    public Object next() {
      n = n.next;
      return n.item;
    }
  }
}

StackTest

public static void main(String[] args) {
    //创建栈对象
    Stack<String> stack = new Stack<>();
    //测试压栈
    stack.push("a");
    stack.push("b");
    stack.push("c");
    stack.push("1");
    stack.push("2");
    stack.push("3");
    for (String item : stack) {
      System.out.println(item);
    }
    System.out.println("***************************");
    //测试弹栈
    String result = stack.pop();
    System.out.println("弹出的元素是 =" + result);
    System.out.println("剩余的元素个数 =" + stack.siza());
  }

案例

括号匹配问题

问题描述

给定一个字符串,里边可能包含()小括号和其他字符,请编写程序检查该字符串中的小括号是否成对出现

例如:

(JAVA)(C++):正确

JAVA(C++)(Python)(HTML):正确

(C++(JAVA):错误

思路分析
  1. 创建一个栈用来存储左括号(
  2. 从左往右遍历字符串,每拿到每一个字符
  3. 判断该字符是不是左括号,如果是,继续入栈存储
  4. 判断该字符是不是右括号,如果不是,继续下一次循环
  5. 如果该字符是右括号,则从栈中弹出一个元素(
  6. 判断元素是否为null,因为如果不是,则证明有对应的左括号,如果不是,则证明整个栈已经为空,没有对应的左括号
  7. 循环结束后,判断栈中是否还有剩余的元素,如果没有,则全部匹配成功,如果有,则表明左括号没匹配完成,有剩余
代码实现
public static void main(String[] args) {
    String str = "(Java(C++)())";
    boolean match = isMatch(str);
    System.out.println(str + "中的括号是否匹配:" + match);
  }

  /**
   * 判断str中的括号是否匹配,如果匹配则返回true,如果不匹配则返回false
   */
  public static boolean isMatch(String str) {
    //创建栈对象,用来存储左括号
    Stack<String> chars = new Stack<>();
    //从左往右遍历整个链表
    for (int i = 0; i < str.length(); i++) {
      //将字符转换为字符串,因为栈是String类型,此转换方法效率最高
      String currChar = String.valueOf(str.charAt(i));
      //判断当前的字符是否是左括号,如果是左括号,则压入栈中
      if ("(".equals(currChar)) { //千万不要使用==运算符测试字符串的相等性,以免在程序中出现糟糕的 bug。从表面上看,这种 bug 很像随机产生的间歇性错误。
        chars.push(currChar);
      }    //继续判断当前字符是否是右括号,如果是,则从栈中弹栈,如果弹出结果不为null,则还存有左括号,如果结果为null,则证明栈为空,返回false
      else if (")".equals(currChar)) {
        String StringPop = chars.pop();
        if (StringPop == null) {
          return false;
        }
      }
    }
    //当遍历完了后,还需判断栈中是否为空,如果不为空,则还剩余左括号,同样返回false,如果为空,则都匹配完毕,返回true
    if (chars.isEmpty()) {
      return true;
    } else {
      return false;
    }
  }

逆波兰表达式求值问题

逆波兰表达式求值问题是我们计算机中经常遇到的一类问题,要研究明白这个问题,首先我们得搞清楚什么是逆波兰表达式,要搞清楚逆波兰表达式,我们要从中缀表达式说起

中缀表达式

中缀表达式就是我们平常生活中使用的表达式:$1+3*2$,$2-(1+3)$等,中缀表达式的特点就是:二元运算符总是置于两个操作数中间

中缀表达式是人们最喜欢的表达式方式,因为简单易懂,但是对于计算机来说就不是这样的了,因为中缀表达式的顺序不具有规律性,不同的运算符具有不用的优先级,如果计算机执行中缀表达式,需要解析表达式语句,做大量的优先级相关操作

逆波兰表达式(后缀表达式)

逆波兰表达式是波兰逻辑学家于1929年首次提出的一种表达式的表示方式,后缀表达式的特点:运算符总是放在跟它相关的操作数之后

中缀表达式逆波兰表达式
a+bab+
a+(b-c)abc-+
a+(b-c)*dabc-d*+
a*(b-c)+dabc-*d+
需求

给定一个只包含加减乘除四种运算的逆波兰表达式的数组表达式,求出该逆波兰表达式的结果

思路分析
  1. 创建一个栈对象oprands存储操作数
  2. 从左往右遍历逆波兰表达式,得到每一个字符串
  3. 判断该字符串是不是运算符,如果不是,把该字符串压入oprans栈中
  4. 如果是运算符,则从oprands栈中弹出两个操作数o1,o2
  5. 使用运算符计算o1与o2,得到结果result
  6. 把result再次压入oprands栈中
  7. 遍历结束后,拿住栈中最终的结果并返回
代码实现
public static void main(String[] args) {
    //中缀表达式3*(17-15)+18/6,逆波兰表达式如下
    String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};
    int result = caculation(notation);
    System.out.println("逆波兰表达式的结果=" + result);
  }

  public static int caculation(String[] notation) {
    //定义一个栈,用来存储操作数
    Stack<Integer> operans = new Stack<>();
    //从左往右遍历逆波兰表达式,得到每一个元素
    for (int i = 0; i < notation.length; i++) {
      String curr = notation[i];
      //判断当前元素是运算符还是操作数
      switch (curr) {
        //如果为运算符,则从栈中弹出两个操作数,完成计算后,再次将结果压入栈中
        case "+": {
          Integer number1 = operans.pop();
          Integer number2 = operans.pop();
          Integer result = number1 + number2;
          operans.push(result);
          break;
        }
        case "-": {
          Integer number1 = operans.pop();
          Integer number2 = operans.pop();
          Integer result = number2 - number1;
          operans.push(result);
          break;
        }
        case "*": {
          Integer number1 = operans.pop();
          Integer number2 = operans.pop();
          Integer result = number1 * number2;
          operans.push(result);
          break;
        }
        case "/": {
          Integer number1 = operans.pop();
          Integer number2 = operans.pop();
          Integer result = number2 / number1;
          operans.push(result);
          break;
        }
        default: {
          operans.push(Integer.parseInt(curr));
          break;
        }
      }
    }
    //如果遍历完了,弹出栈中最后的那一个结果即可
    return operans.pop();
  }

队列

队列是一种基于先进先出$(FIFO)$的数据结构,是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表,它按照先进先出的原则存储数据,先进入的数据,在读取数据时被先读取出来

队列的实现

队列的API设计
类名Queue
构造方法Queue():创建Queue对象
成员方法1.public boolean isEmpty():判断队列是否为空,是返回true,否返回false 2.public int size():获取队列中元素的个数 3.public T dequeue():从队列中拿出一个元素 4.public void enqueue(T t):往队列中插入一个元素
成员变量1.private Node head:记录首节点 2.private int N:当前栈的元素个数 3.private Node last:记录最后一个节点
成员内部类private class Node:节点类
代码实现

Queue

public class Queue<T> implements Iterable<T> {

  /**
   * 记录首节点
   */
  private Node head;
  /**
   * 记录尾结点
   */
  private Node last;
  /**
   * 记录队列中元素的个数
   */
  private int N;


  private class Node {

    public T item;
    public Node next;

    public Node(T item, Node next) {
      this.item = item;
      this.next = next;
    }
  }

  public Queue() {
    this.head = new Node(null, null);
    this.last = null;
    this.N = 0;
  }

  /**
   * 判断队列是否为空
   */
  public boolean isEmpty() {
    return N == 0;
  }

  /**
   * 返回队列中元素的个数
   */
  public int size() {
    return N;
  }

  /**
   * 向队列中插入元素t
   */
  public void enqueue(T t) {
    //如果尾结点为null
    if (last == null) {
      last = new Node(t, null);
      head.next = last;
    }//如果尾结点不为null
    else {
      Node OldLast = last;
      last = new Node(t, null);
      OldLast.next = last;
    }
    //元素个数+1
    this.N++;
  }

  /**
   * 从队列中拿出一个元素
   */
  public T dequeue() {
    //如果元素个数为0,直接返回null
    if (isEmpty()) {
      return null;
    }
    //将头结点指向新的第一个节点也就是原来的第二个节点
    Node OldFirst = head.next;
    head.next = OldFirst.next;
    //元素个数-1
    this.N--;
    //出队列是在删除元素,当元素全部被删除后,就相当于没有last这个节点了,所以需要重置一个last节点
    if (isEmpty()) {
      last = null;
    }
    return OldFirst.item;
  }

  @Override
  public Iterator<T> iterator() {
    return new QIterator();
  }

  private class QIterator implements Iterator {

    private Node n;

    public QIterator() {
      this.n = head;
    }

    @Override
    public boolean hasNext() {
      return n.next != null;
    }

    @Override
    public Object next() {
      n = n.next;
      return n.item;
    }
  }
}

QueueTest

public static void main(String[] args) {
    //创建一个队列对象
    Queue<String> Que = new Queue<>();
    //测试队列enqueue方法
    Que.enqueue("a");
    Que.enqueue("b");
    Que.enqueue("c");
    Que.enqueue("1");
    Que.enqueue("2");
    Que.enqueue("3");
    Que.enqueue("z");
    for (String str : Que) {
      System.out.println(str);
    }
    System.out.println("--------------------------");
    String result = Que.dequeue();
    System.out.println("出队列的元素为=" + result);
    System.out.println("剩余的元素个数=" + Que.size());
    //测试队列的dequeue方法
  }
Last modification:May 16th, 2021 at 12:32 pm