2018年10月31日
栈是一种后进先出(LIFO)的数据结构，如同摞书本一样，最先放的书本是最后才会拿到：
栈的数组实现
public class ArrayStack<Item> implements Iterable<Item> {
private Item[] a = (Item[]) new Object[1];
private int N;
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void push(Item item) {
if (N == a.length) {
resize(2 * a.length);
}
a[N++] = item;
}
public Item pop() {
if (isEmpty()) {
throw new NoSuchElementException("Stack underflow");
}
Item item = a[--N];
a[N] = null;
if (N > 0 && N == a.length / 4) {
resize(a.length / 2);
}
return item;
}
private void resize(int max) {
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
a = temp;
}
@Override
public Iterator<Item> iterator() {
return new ReverseArrayIterator();
}
private class ReverseArrayIterator implements Iterator<Item> {
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return a[--i];
}
@Override
public void remove() {
}
}
}
以上的实现中当栈中容量与数组容量相等时，会进行扩容；当栈中容量为数组容量四分之一时，会进行缩容，具体操作如下图：
最好时间复杂度：最理想的情况下，当前栈中元素数量比数组的容量小，此时就直接执行代码块
a[N++] = item;，即此时的时间复杂度为。
最坏时间复杂度：最糟糕的情况下，当前栈中元素数量与数组的容量相等，此时就要执行
resize方法进行扩容了，进入循环体，执行N次复制操作，此时的时间复杂度为。
-
平均时间复杂度：
当栈中元素小于数组容量时，此时进行压栈就有
N种情况，且每种情况的时间复杂度为N+1中情况，对其取平均值：
在大标记法中，可以省略系数与低阶项，所以其平均时间复杂度为
下面使用概率来分析，由于有
N+1中情况，每种情况的发生概率为，则其平均时间复杂度为：
均摊时间复杂度：根据上述代码，每出现一次扩容操作时，即此时压栈的时间复杂度为
N次压栈操作的时间复杂度均为N次上，得出均摊时间复杂度为
栈的链表实现
public class ListStack<Item> implements Iterable<Item> {
private Node first;
private int N;
private class Node {
Item item;
Node next;
}
public void push(Item item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}
public Item pop() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Item item = first.item;
first = first.next;
N--;
return item;
}
public Item peek() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return first.item;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove() {
}
}
}
push操作如图：
pop操作如图：
整体操作如下：
栈的应用
1，括号匹配
每个左括号必然对应其右括号，如[()]就是合法的，而[(])就是错误的；这个程序可以用栈来实现：
定义一个空栈，读入字符，如果字符是一个左括号，则将其压入栈中。如果字符是一个右括号，则当栈空时报错，否则，将栈顶元素弹出，如果弹出的字符不是对应的左括号，则报错。若全部字符读完后，栈不为空则报错。
public static boolean isComplete(String str) {
if (str.length() == 0) {
return false;
}
Deque<Character> sta = new ArrayDeque<>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '[') {
sta.push('[');
}
if (str.charAt(i) == '(') {
sta.push('(');
}
if (str.charAt(i) == '{') {
sta.push('{');
}
if (str.charAt(i) == ']') {
if (sta.isEmpty()) {
return false;
}
if (sta.pop() != '[') {
return false;
}
}
if (str.charAt(i) == ')') {
if (sta.isEmpty()) {
return false;
}
if (sta.pop() != '(') {
return false;
}
}
if (str.charAt(i) == '}') {
if (sta.isEmpty()) {
return false;
}
if (sta.pop() != '{') {
return false;
}
}
}
2，后缀(逆波兰)表达式
中缀表达式就是我们常见的表达式，如：
而后缀表达式的表示形式为：
前缀表达式的表示形式为：
在计算机中，利用后缀表达式进行计算没有必要知道任何优先规则，使用后缀表达式计算的过程及其程序：
private static Pattern ISNUMBER = Pattern.compile("[0-9]+");
/**
* 计算后缀表达式：2 3 * 2 1 - / 3 4 1 - * +
* 其中缀表达式：2 * 3 / ( 2 - 1 ) + 3 * ( 4 - 1 )
* 将数字压栈，一遇到运算符就将其取出运算，结果再压入栈
*/
public static void evaluatePostFix() {
String str = "2 3 * 2 1 - / 3 4 1 - * +";
String[] strings = str.split("\\s+");
Stack<Integer> sta = new Stack<>();
for (String s : strings) {
if (ISNUMBER.matcher(s).matches()) {
sta.push(Integer.parseInt(s));
} else {
int n1 = sta.pop();
int n2 = sta.pop();
int n3 = 0;
if (s.equals("+")) {
n3 = n2 + n1;
} else if (s.equals("-")) {
n3 = n2 - n1;
} else if (s.equals("*")) {
n3 = n2 * n1;
} else if (s.equals("/")) {
n3 = n2 / n1;
}
sta.push(n3);
}
}
System.out.println(sta.pop());
}
前缀式求值是先将前缀式逆序，后通过后缀式求值的方法，求值。但要注意的是操作数的运算顺序是与后缀表达式相反的。举个例子：
中缀表达式8-7；后缀表达式为87-，前缀表达式为-87，前缀表达式逆序78-，左操作数为8，右操作数为7
private static Pattern ISNUMBER = Pattern.compile("[0-9]+");
/**
* 计算前缀表达式：+ / * 2 3 - 2 1 * 3 - 4 1
* 其中缀表达式为：2 * 3 / ( 2 - 1 ) + 3 * ( 4 - 1 )
* 先将其反转，将数字压入栈，一遇到运算符就取出数字计算，将计算结果压入栈
*/
public static void evaluatePreFix() {
String str = "+ / * 2 3 - 2 1 * 3 - 4 1";
String[] strings = str.split("\\s+");
for (int i = 0; i < strings.length / 2; i++) {
String temp = strings[i];
strings[i] = strings[strings.length - i - 1];
strings[strings.length - i - 1] = temp;
}
Stack<Integer> sta = new Stack<>();
for (String s : strings) {
if (ISNUMBER.matcher(s).matches()) {
sta.push(Integer.parseInt(s));
} else {
int n1 = sta.pop();
int n2 = sta.pop();
int n3 = 0;
if (s.equals("+")) {
n3 = n1 + n2;
} else if (s.equals("-")) {
n3 = n1 - n2;
} else if (s.equals("*")) {
n3 = n1 * n2;
} else if (s.equals("/")) {
n3 = n1 / n2;
}
sta.push(n3);
}
}
System.out.println(sta.pop());
}
如何将中缀表达式转化为后缀表达式？
假设中缀表达式：
后缀表达式为：
过程如下：
程序如下：
/**
* 利用正则表达式判断是否为整数
* 以下只能匹配非负整数
*/
private static Pattern ISNUMBER = Pattern.compile("[0-9]+");
/**
* 将中缀表达式转为后缀表达式
* 结果为：2 3 * 2 1 - / 3 4 1 - * +
*/
public static void infixToPostfix() {
String str = "2 * 3 / ( 2 - 1 ) + 3 * ( 4 - 1 )";
String[] strings = str.split("\\s+");
Stack<String> sta = new Stack<>();
StringBuffer sb = new StringBuffer();
for (String s : strings) {
if (ISNUMBER.matcher(s).matches()) {
sb.append(s + " ");
} else {
switch (s) {
case ")":
while (!sta.isEmpty() && (!"(".equals(sta.peek()))) {
sb.append(sta.pop() + " ");
}
sta.pop();
break;
case "(":
sta.push(s);
break;
case "^":
while (!sta.isEmpty() && (!("^".equals(sta.peek()) ||
"(".equals(sta.peek())))) {
sb.append(sta.pop());
}
sta.push(s);
break;
case "*":
case "/":
while (!sta.isEmpty() && (!"+".equals(sta.peek())) &&
(!"-".equals(sta.peek())) && (!"(".equals(sta.peek()))) {
sb.append(sta.pop()+" ");
}
sta.push(s);
break;
case "+":
case "-":
while (!sta.isEmpty() && (!"(".equals(sta.peek()))) {
sb.append(sta.pop() + " ");
}
sta.push(s);
break;
default:
}
}
}
while (!sta.isEmpty()) {
sb.append(sta.pop()+" ");
}
System.out.println(sb.toString());
}
将中缀表达式转为前缀表达式，要先将其反转，当栈中数据全部弹出后，再将其反转即可：
/**
* 将中序表达式转为前序表达式
* 首先将其反转，将运算符压栈，遇到（就弹出
* 结果为：+/*23-21*3-41
*/
public static void infixToPrefix() {
String str = "2 * 3 / ( 2 - 1 ) + 3 * ( 4 - 1 )";
String[] strings = str.split("\\s+");
for (int i = 0; i < strings.length / 2; i++) {
String temp = strings[i];
strings[i] = strings[strings.length - i - 1];
strings[strings.length - i - 1] = temp;
}
System.out.println(Arrays.toString(strings));
Stack<String> sta = new Stack<>();
StringBuffer sb = new StringBuffer();
for (String s : strings) {
if (ISNUMBER.matcher(s).matches()) {
sb.append(s + " ");
} else {
switch (s) {
case "(":
while (!sta.isEmpty() && (!")".equals(sta.peek()))) {
sb.append(sta.pop() + " ");
}
sta.pop();
break;
case ")":
sta.push(s);
break;
case "^":
while (!sta.isEmpty() && (!("^".equals(sta.peek()) ||
"(".equals(sta.peek())))) {
sb.append(sta.pop());
}
sta.push(s);
break;
case "*":
case "/":
sta.push(s);
break;
case "+":
case "-":
while (!sta.isEmpty() && (!")".equals(sta.peek()))) {
sb.append(sta.pop() + " ");
}
sta.push(s);
break;
default:
}
}
}
while (!sta.isEmpty()) {
sb.append(sta.pop() + " ");
}
System.out.println(sb.reverse().toString());
}
