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