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