定义
先入后出，有点类似将书放在抽屉里，先放进去的书，如果想拿到他，必须将他上面书拿完才可以，粗俗的形容可以这么比喻：“吃了吐”叫栈，“吃了拉”叫队列，话粗理不粗。栈是一种“操作受限”的线性表，只允许一段插入和删除数据。
从功能上看，数组或链表确实可代替栈，但是在特定的情况中，数组和链表暴露的接口太多，操作上虽然灵活，但是很多条件不可控，使用上当然容易出现问题。
当某个数据集合只涉及在一段插入和删除数据，并且满足先进后出的特性，我们就应该首选栈这种数据结构。
实现
根据其定义和特点，栈主要包含两个操作，入栈和出栈。数组和链表都可以实现，用数组实现的栈叫做 顺序栈，用链表实现的栈叫做 链式栈。后面会贴上具体的实现代码和测试用例。
栈存储数据只需要一个大小为 n 的数组就足够了，在操作数据的过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)，至于入栈和出栈的时间复杂度也是 O(1)。
练习
数组实现栈(支持动态扩容)
需要注意点：
- 当数据不断增加，大小达到阈值，也就是容器满了，此时大小需要扩容到原来的两倍。
- 当数据不断减小，大小达到整个大小四分之一时，此时大小需要缩小为原来的 1/2。
class ArrayStack<T> implements Iterable<T>{
private T[] data;
private int totalCount;
private int count;
ArrayStack(int capacity) {
data = (T[]) new Object[capacity];
totalCount = capacity;
}
private boolean push(T t) {
if (count == totalCount) {
resize(totalCount * 2);
}
data[count] = t;
count++;
System.out.println("push: " + t + " data:\t" + Arrays.toString(data));
return true;
}
private T pop() {
if (count == 0) return null;
T t = data[count - 1];
data[count - 1] = null;
count --;
if (count == totalCount / 4 && totalCount / 2 != 0) {
resize(totalCount / 2);
}
System.out.println("pop: " + t + " data:\t" + Arrays.toString(data));
return t;
}
boolean isEmpty() {
return count == 0;
}
int size() {
return count;
}
T peek() {
if (count == 0) {
return null;
}
T t = data[count - 1];
System.out.println("peek: " + t + " data:\t" + Arrays.toString(data));
return t;
}
private void resize(int newSize) {
T[] newData = (T[]) new Object[newSize];
for (int i = 0; i < count; i++) {
newData[i] = data[i];
}
totalCount = newData.length;
System.out.println("扩容前：" + data.length);
data = newData;
System.out.println("重新调整大小:\t" + data.length + " data:\t" + Arrays.toString(data));
}
public static void main(String[] args) {
ArrayStack<Integer> data = new ArrayStack<Integer>(4);
data.push(1);
data.push(2);
data.push(3);
data.push(4);
data.push(5);
data.push(6);
System.out.println("size:\t" + data.size());
System.out.println("isEmpty:\t" + data.isEmpty());
for (Integer datum : data) {
System.out.print(datum);
}
System.out.println();
data.pop();
data.pop();
data.pop();
data.pop();
data.peek();
data.peek();
data.peek();
}
@Override
public Iterator<T> iterator() {
return new ArrayIterator();
}
class ArrayIterator implements Iterator<T> {
int i = count;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public T next() {
return data[--i];
}
@Override
public void remove() {
}
}
}
这里如果需要支持加强 for 循环，则需要创建自定义实现 Iterator 类。
运行结果：
push: 1 data: [1, null, null, null]
push: 2 data: [1, 2, null, null]
push: 3 data: [1, 2, 3, null]
push: 4 data: [1, 2, 3, 4]
扩容前：4
重新调整大小: 8 data: [1, 2, 3, 4, null, null, null, null]
push: 5 data: [1, 2, 3, 4, 5, null, null, null]
push: 6 data: [1, 2, 3, 4, 5, 6, null, null]
size: 6
isEmpty: false
654321
pop: 6 data: [1, 2, 3, 4, 5, null, null, null]
pop: 5 data: [1, 2, 3, 4, null, null, null, null]
pop: 4 data: [1, 2, 3, null, null, null, null, null]
扩容前：8
重新调整大小: 4 data: [1, 2, null, null]
pop: 3 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
链表实现栈
需要注意的是临界值的判断。
class LinkedStack<T> implements Iterable<T> {
Node<T> head = null;
int count = 0;
void push(T t) {
Node<T> node = createNode(t);
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
count++;
System.out.println("push:\t" + t + " data:\t" + head.toString());
}
T pop() {
if (head == null) {
return null;
}
T t = head.value;
head = head.next;
if (head != null) {
System.out.println("pop:\t" + t + " data:\t" + head.toString());
} else {
System.out.println("pop:\t" + t + " data:\tnull");
}
count--;
return t;
}
boolean isEmpty() {
return count == 0;
}
int size() {
return count;
}
T peek() {
if (head == null) {
return null;
}
T t = head.value;
System.out.println("peek:\t" + t + " data:\t" + head.toString());
return t;
}
Node<T> createNode(T t) {
return new Node<T>(t, null);
}
public static void main(String[] args) {
LinkedStack<Integer> stack = new LinkedStack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println("size:\t" + stack.size());
System.out.println("isEmpty:\t" + stack.isEmpty());
for (Integer integer : stack) {
System.out.println(integer);
}
stack.peek();
stack.peek();
stack.peek();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (T t : this) {
sb.append(t).append(" ");
}
sb.append("\n");
return sb.toString();
}
void clear() {
head = null;
count = 0;
}
@Override
public Iterator<T> iterator() {
return new LinkedIterator();
}
class LinkedIterator implements Iterator<T> {
Node<T> first = head;
int n = count;
@Override
public boolean hasNext() {
return n > 0;
}
@Override
public T next() {
T t = first.value;
first = first.next;
n--;
return t;
}
@Override
public void remove() {
}
}
}
运行结果：
push: 1 data: 1
push: 2 data: 2 1
push: 3 data: 3 2 1
push: 4 data: 4 3 2 1
size: 4
isEmpty: false
4321
peek: 4 data: 4 3 2 1
peek: 4 data: 4 3 2 1
peek: 4 data: 4 3 2 1
pop: 4 data: 3 2 1
pop: 3 data: 2 1
pop: 2 data: 1
pop: 1 data: null
栈在括号匹配中的应用
括号一般都是一一对应的，那可以用栈保存未匹配的左括号，从左到又进行扫描。
class StackTest1 {
public static void main(String[] args) {
LinkedStack<String> stack = new LinkedStack<String>();
stack.push("[");
stack.push("{");
stack.push("『");
stack.push("「");
stack.push("」");
stack.push("』");
stack.push("}");
stack.push("]");
System.out.println(stack.toString());
System.out.println("is correct:\t" + isCorrect(stack));
}
private static boolean isCorrect(LinkedStack<String> stack) {
boolean isCorrect = true;
LinkedStack<String> stack1 = new LinkedStack<String>();
for (String s : stack) {
stack1.push(s);
}
Iterator<String> iterator = stack.iterator();
Iterator<String> iterator1 = stack1.iterator();
while (iterator.hasNext() && iterator1.hasNext()) {
if (!equals(iterator.next(), iterator1.next())) {
return false;
}
}
return isCorrect;
}
private static boolean equals(String one, String two) {
return ("[".equals(one) && "]".equals(two)) || ("[".equals(two) && "]".equals(one)) ||
("{".equals(one) && "}".equals(two)) || ("{".equals(two) && "}".equals(one)) ||
("「".equals(one) && "」".equals(two)) || ("「".equals(two) && "」".equals(one)) ||
("『".equals(one) && "』".equals(two)) || ("『".equals(two) && "』".equals(one));
}
}
浏览器在栈的应用
一般浏览器支持回退和前进功能，其实可以通过栈来实现这个功能。
- 使用两个栈，一个存储后退的数据，一个存储前进的数据
- 每次打开新的网址，后退栈压入，前进栈清空
- 每次回退网站，后退栈出栈，前进栈压入
- 在已经后退基础上前进，后退栈压入，前进栈出栈
- 每次前进和后退都需要判断各自栈是否可以进行数据操作
class StackTest2 {
String currentPage = "";
LinkedStack<String> backStack;
LinkedStack<String> forwardStack;
StackTest2() {
backStack = new LinkedStack<String>();
forwardStack = new LinkedStack<String>();
}
void open(String url) {
if (currentPage != null) {
backStack.push(url);
forwardStack.clear();
}
showPage(url, "open");
}
boolean canGoBack() {
return !backStack.isEmpty();
}
boolean canGoForward() {
return !forwardStack.isEmpty();
}
void goBack() {
if (canGoBack()) {
String back = backStack.pop();
forwardStack.push(currentPage);
showPage(back, "go back");
}
}
void goForward() {
if (canGoForward()) {
String forward = forwardStack.pop();
backStack.push(currentPage);
showPage(forward, "go forward");
}
}
void showCurrentPage() {
System.out.println("current page url:\t" + currentPage);
}
void showPage(String url, String desc) {
this.currentPage = url;
System.out.println("current page url:\t" + this.currentPage + " desc:\t" + desc);
}
public static void main(String[] args) {
StackTest2 stack = new StackTest2();
stack.open("http://www.baidu.com");
stack.open("http://news.baidu.com/");
stack.open("http://news.baidu.com/ent");
stack.goBack();
stack.goBack();
stack.goForward();
stack.open("http://www.qq.com");
stack.goForward();
stack.goBack();
stack.goForward();
stack.goBack();
stack.goBack();
stack.goBack();
stack.goBack();
stack.showCurrentPage();
}
}
参考自极客时间
网友评论