4.4.1、栈的定义

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

图片alt

4.4.2、栈的实现

4.4.2.1、栈API设计

类名 Stack
构造方法 Stack():创建Stack对象
成员变量 private Node head:记录首结点
private int N:当前栈的元素个数
成员内部类 private class Node:结点类
成员方法 public boolean isEmpty():判断是否为空
public int size(): 获取栈的元素个数
public T pop():弹出栈顶元素
public void push(T t):向栈压入元素t

4.4.2.2、栈实现和测试

实现类:

package cn.test.algorithm.datastruct;

import java.util.Iterator;

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

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

    //内部类
    private class Node {
        public T item;
        public Node next;

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

    //首结点
    private Node head;
    //元素个数
    private int N;


    public Stack() {
        head = new Node(null, null);
        N = 0;
    }

    //是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //栈的元素个数
    public int size() {
        return N;
    }

    //入栈
    public void push(T t) {
        //找到首结点的第一个结点
        Node oldFirst = head.next;
        //创建新结点
        Node newNode = new Node(t, null);
        //让首结点指向新结点
        head.next = newNode;
        //让新结点指向原来的第一个结点
        newNode.next = oldFirst;
        //元素+1
        N += 1;
    }

    //出栈
    public T pop() {
        //找到首结点的第一个结点
        Node oldFirst = head.next;
        //让首结点指向原来结点的下一个结点
        if (oldFirst == null) {
            return null;
        }
        head.next = oldFirst.next;
        //元素-1
        N -= 1;
        return oldFirst.item;
    }
}

测试类:

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.Stack;

public class StackTest {
    public static void main(String[] args) {
        Stack<String> stacks = new Stack<>();
        stacks.push("a");
        stacks.push("b");
        stacks.push("c");
        stacks.push("d");
        stacks.push("e");
        System.out.println("====================入栈测试=====================");
        System.out.println("栈里元素个数:" + stacks.size());
        System.out.println("栈里的数据");
        for (String item : stacks) {
            System.out.println(item);
        }

        System.out.println("====================出栈测试=====================");
        String result = stacks.pop();
        System.out.println("栈里元素个数:" + stacks.size());
        System.out.println("弹出元素值:" + result);
        for (String item : stacks) {
            System.out.println(item);
        }
        result = stacks.pop();
        System.out.println("栈里元素个数:" + stacks.size());
        System.out.println("弹出元素值:" + result);
        for (String item : stacks) {
            System.out.println(item);
        }
    }
}

执行结果:

====================入栈测试=====================
栈里元素个数:5
栈里的数据
e
d
c
b
a
====================出栈测试=====================
栈里元素个数:4
弹出元素值:e
d
c
b
a
栈里元素个数:3
弹出元素值:d
c
b
a

4.4.3、使用栈的案例

4.4.3.1、括号匹配问题

问题描述:给定一个字符串,里面可能包含”()”小括号和其他字符,编写程序检查字符串中的小括号是否成对出现。

例如:

  • (上海)(长安):成功
  • 上海((长安)):成功
  • ((上海)(长安)):成功
  • 上海(长安)):失败
  • ((上海)(长安:失败

实现类,这里使用到栈的类:

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.Stack;

public class BracketMatchTest {
    public static void main(String[] args) {
        String str1 = "(上海)(长安)";
        boolean match = isMatch(str1);
        System.out.println(str1 + "中的括号是否匹配:" + match);

        String str2 = "((上海)(长安";
        boolean match2 = isMatch(str2);
        System.out.println(str2 + "中的括号是否匹配:" + match2);
    }

    public static boolean isMatch(String str) {
        //创建栈对象
        Stack<String> chars = new Stack<>();
        //遍历字符串
        for (int i = 0; i < str.length(); i++) {
            String currChar = str.charAt(i) + "";
            //判断是否是左括号,如果是就入栈
            if (currChar.equals("(")) {
                chars.push(currChar);
            } else if (currChar.equals(")")) {
                //判断是否是右括号,如果是就出栈,如果为null,判断没有匹配的左括号,反之有
                String pop = chars.pop();
                if (pop == null) {
                    return false;
                }
            }
        }
        //遍历完成后判断栈是否为空,如果有就证明不匹配
        if (chars.isEmpty()) {
            return true;
        }
        return false;
    }
}

测试结果:

(上海)(长安)中的括号是否匹配:true
((上海)(长安中的括号是否匹配:false

4.4.3.2、逆波兰表达式

中缀表达式是一个通用的算术或逻辑公式表示方法。(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法 [1] 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面

中缀表达式 逆波兰表达式
a+b ab+
a+(b-c) abc-+
a+(b-c)*d abc-d*+
a*(b-c)+d abc-*d+

实现类:

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.Stack;

public class ReversePolishNotationTest {
    public static void main(String[] args) {
        //中缀表达式3*(17-15)+18/6的逆波兰表达式如下:
        String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};

        int res = calculate(notation);

        System.out.println("计算结果为:" + res);
    }

    //计算方法
    public static int calculate(String[] notation) {
        Stack<Integer> oprands = new Stack<>();
        Integer o1, o2;
        for (String value : notation) {
            switch (value) {
                case "+":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    oprands.push(o2 + o1);//这里顺序一定要是o2在o1前
                    break;
                case "-":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    oprands.push(o2 - o1);
                    break;
                case "*":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    oprands.push(o2 * o1);
                    break;
                case "/":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    oprands.push(o2 / o1);
                    break;
                default:

                    oprands.push(Integer.parseInt(value));
                    break;
            }
        }
        return oprands.pop();
    }
}

运行结果:

计算结果为:9