引言
- 函数调用
- 编译原理：语法分析
- 括号匹配
问题：栈是操作受限的线性表，为什么不直接用数组或者链表？
数组和链表暴露了太多接口，操作虽然灵活，但不可控，容易出错。比如数组支持任意位置插入数组，如果插入位置写错将改变所有数组的内容。
而栈只能在一端插入和删除数据，并且后进先出。
顺序栈
使用数组实现栈
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] data;
int n;
int count;
public ArrayStack(int n) {
this.n = n;
count = 0;
data = new String[n];
}
public boolean push(String value) {
if (n == count)
return false;
data[count++] = value;
return true;
}
public String pop() {
if (count == 0)
return null;
return data[--count];
}
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(5);
List<String> data = new ArrayList<String>(Arrays.asList("a", "b", "c", "d", "e"));
for (String i : data) {
arrayStack.push(i);
}
boolean result = arrayStack.push("a");
System.out.println(!result);
Collections.reverse(data);
for (String i : data) {
System.out.println(i.equals(arrayStack.pop()));
}
System.out.println(arrayStack.pop() == null);
}
}
入栈时间复杂度：O(1)
出栈时间复杂度：O(1)
链式栈
使用链表实现栈
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class StackBasedOnLinkedList {
private Node top;
public void push(int value) {
Node newNode = new Node(value);
if (top == null)
top = newNode;
else {
newNode.next = top;
top = newNode;
}
}
public int pop() {
if (top == null)
return -1;
int result = top.data;
top = top.next;
return result;
}
public static class Node {
int data;
Node next;
public Node(int data) {
this.data= data;
}
}
public static void main(String[] args) {
StackBasedOnLinkedList stack = new StackBasedOnLinkedList();
List<Integer> data = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
for (int i : data) {
stack.push(i);
}
Collections.reverse(data);
for (int i : data) {
System.out.println(i == stack.pop());
}
System.out.println(stack.pop() == -1);
}
}