4.4.1、栈的定义

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

4.4.2、栈的实现

4.4.2.1、栈API设计

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] 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面

实现类：

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