关于数据结构与算法:Java数据结构与算法分析-栈

GitHub 源码分享

我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures

1. 栈（Stack）

栈又叫堆栈，是一种运算受限制的线性表，限定只能在一端进行插入和删除操作，该端称为栈顶（Top），绝对的另一端叫栈底（Bottom）。

依据栈的定义可知，最先进入栈的元素在栈底，最初进入栈的元素在栈顶。而删除元素刚好相同，即删除程序从栈顶到栈底

对栈的操作只有两种：

• 入栈（push）：又叫进栈或压栈，即向栈插入一条新的元素，该元素为新的栈顶元素。
• 出栈（pop）：又叫退栈，即从栈顶删除（取出）最初入栈的元素，而其相邻元素成为新的栈顶元素。

栈是一个先进后出（FILO – First In Last Out）的有序列表。在上图中形容了栈的模型，咱们对栈的操作只有 push 和pop，栈顶元素是该栈惟一可见的元素。

2. 代码实现

因为栈是一个表，因而任何实现表的办法都能实现栈。显然咱们之前用到的《数组》和《链表》都能够实现栈。上面代码是应用数组实现的一个栈。

size示意栈内元素的大小，栈顶元素为 elementData[size – 1]，栈底元素为 elementData[0]。入栈时执行 size++，出站时执行 size–

public class StackDemo {public static void main(String[] args) {System.out.println("------------------- 入站");
        Stack<String> stack = new Stack<>(10);
        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");
        stack.push("e");
        stack.print();

        System.out.println("元素大小:" + stack.size());
        System.out.println("栈容量:" + stack.capacity());

        System.out.println("------------------- 出站");
        System.out.println("出站元素:" + stack.pop());
        System.out.println("出站元素:" + stack.pop());
        stack.print();
        System.out.println("元素大小:" + stack.size());
        System.out.println("栈容量:" + stack.capacity());
    }

    private static class Stack<E> {
        private int size; // 元素大小
        private final int capacity; // 栈的容量
        transient Object[] elementData; // 元素数据

        public Stack(int capacity) {if (capacity <= 0) {throw new IllegalArgumentException("Illegal Capacity:" + capacity);
            } else {
                this.capacity = capacity;
                elementData = new Object[capacity];
            }
        }

        /**
         * 获取栈的元素大小
         *
         * @return
         */
        public int size() {return size;}

        /**
         * 获取栈的容量
         *
         * @return
         */
        public int capacity() {return capacity;}

        /**
         * 入栈
         *
         * @param e
         * @return
         */
        public boolean push(E e) {if (size >= capacity) {return false;}
            elementData[size++] = e;
            return true;
        }

        /**
         * 出栈
         *
         * @return
         */
        public E pop() {if (size <= 0) {return null;}
            return (E) elementData[--size];
        }

        /**
         * 打印元素数据
         */
        public void print() {System.out.print("站内元素:");
            for (int i = 0; i < size; i++) {System.out.printf("%s\t", elementData[i]);
            }
            System.out.println();}
    }
}

输入后果：

------------------- 入站
站内元素: a    b    c    d    e    
元素大小: 5
栈容量: 10
------------------- 出站
出站元素: e
出站元素: d
站内元素: a    b    c    
元素大小: 3
栈容量: 10

3. 栈的利用 – 均衡符号

编译器检查程序的语法错误时，经常会因为短少一个符号（如脱漏一个花括号等）引起编译器上列出上百行的诊断，而真正的谬误并没有找出。在这种状况下，如果能有一个工具可能检测括号必须成对呈现那就好了，这便能够应用栈进行解决。

上面代码应用了 Java 自带的 Stack 类进行实现。字符串 [() ] 是非法的，而 [(] ) 是谬误的。

代码实现：

public class StackDemoBalancedChar {public static void main(String[] args) {BalancedChar balancedChar = new BalancedChar();
        String str = "[()][{}][][((()))]";
        boolean ok = balancedChar.isOk(str);
        System.out.printf("字符串：%s\t----> %s", str, ok);
    }

    private static class BalancedChar {private final char[] openArray = {'(', '[', '{'};  // 左括号
        private final char[] closeArray = {')', ']', '}'}; // 右括号

        /**
         * 判断字符串是否正确
         *
         * @param str
         * @return
         */
        public boolean isOk(String str) {
            // 应用 Java 自带的 Stack 类
            Stack<Character> stack = new Stack<>();

            boolean ok = true; // 判断字符串是否正确

            for (char c : str.toCharArray()) {

                // 若不是均衡符则疏忽
                if (!isBalancedChar(c)) {continue;}

                // 如果是左括号，则入栈
                if (isOpen(c)) {stack.push(c);
                    continue;
                }

                // 如果是右括号，而栈为空则报错
                if (stack.empty()) {
                    ok = false;
                    break;
                }
                // 如果是右括号，从栈中取出一个元素，并与以后元素判断是否是一对，若不是一对则报错
                Character open = stack.pop();
                if (!isTwain(open, c)) {ok = false;}
            }

            return ok && stack.empty();}

        /**
         * 是否为左括号
         *
         * @param c
         * @return
         */
        public boolean isOpen(char c) {return inArray(openArray, c);
        }

        /**
         * 是否为右括号
         *
         * @param c
         * @return
         */
        public boolean isClose(char c) {return inArray(closeArray, c);
        }

        /**
         * 是否是均衡符
         */
        public boolean isBalancedChar(char c) {return isOpen(c) || isClose(c);
        }

        /**
         * 是否在数组中
         *
         * @param charArray
         * @param c
         * @return
         */
        public boolean inArray(char[] charArray, char c) {for (char c1 : charArray) {if (c1 == c) {return true;}
            }
            return false;
        }

        /**
         * 是否一对均衡符
         *
         * @param open
         * @param close
         * @return
         */
        public boolean isTwain(char open, char close) {switch (open) {
                case '(':
                    if (close == ')') {return true;}
                case '[':
                    if (close == ']') {return true;}
                case '{':
                    if (close == '}') {return true;}
                default:
                    return false;
            }
        }

    }
}

输入后果：

字符串：[()][{}][][((()))]    ----> true