数据结构与算法--栈
数据结构与算法--栈
我们可能都有这样的经历：小时候交作业，放到老师的讲台上。先交的作业的肯定会在最底下，最后几个交的同学可能就有点小动作了，总是喜欢把自己的作业塞到底下或者中间，因为最后交的作业必然位于最上面，也就是最显眼的地方，老师批改时，拿出的第一份作业就是他的。这样一摞作业，最后放的在最顶上，会被先拿走；先放的在最底下，最后才被拿走。像这类先进后出（LIFO即Last In First Out）的数据结构称为栈。
栈有个栈顶的说法，栈顶是允许数据操作的地方，一般的操作就是push和pop，分别叫做进栈和出栈。栈本身是一个线性表，所以也有顺序存储和链式存储两种结构。
顺序栈--数组实现
栈的顺序存储结构可以用数组实现。那么数组的哪一头作为栈顶呢？显然数组的尾部作为栈顶比较好，因为在数组的尾部插入、移除数据都十分容易（时间复杂度为O(1)），而在数组头部a[0]进行数据操作，将会有大量的元素移动...
push操作实际上就是在数组尾部（栈顶）添加元素，而pop则是把最新添加元素从数组尾部弹出。还可以定义一个peek方法，只是获得栈顶的元素而不弹出。至于代码的实现，直接拿以前线性表顺序存储结构的代码稍微改改就行，比如add方法直接改成push就能用。
package Chap4;
import java.util.Iterator;
public class MyStack<Item> implements Iterable<Item> {
// 初始化为长度为1，方便第一次push的时候可以访问a[0]这个下标
private Item[] a = (Item[]) new Object[1];
private int N;
public MyStack(Item... items) {
for (int i = 0; i < items.length; i++) {
push(items[i]);
}
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
private void resize(int max) {
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
// 将容量大于N的数组传给a
a = temp;
}
public void push(Item item) {
if (N == a.length) {
resize(a.length * 2);
}
a[N++] = item;
}
public Item pop() {
Item item = a[--N];
// 自减去后现在N为N-1
a[N] = null;
if (N == a.length / 4) {
resize(a.length / 2);
}
return item;
}
public Item peek() {
return a[N - 1];
}
// N=0但是a.length不为0，可以再次add
public void clear() {
for (int i = 0; i < N; i++) {
a[i] = null;
}
N = 0;
}
@Override
public Iterator<Item> iterator() {
return new ReveredIterator();
}
private class ReveredIterator implements Iterator<Item> {
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[--i];
}
}
@Override
public String toString() {
Iterator<Item> it = iterator();
if (!it.hasNext()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
while (true) {
Item item = it.next();
sb.append(item);
if (!it.hasNext()) {
return sb.append("]").toString();
}
sb.append(", ");
}
}
public static void main(String[] args) {
MyStack<String> a = new MyStack<>();
a.push("I");
a.push("have");
a.push("a");
a.push("dream.");
System.out.println(a);
a.pop(); // dream.
a.push("pig.");
System.out.println(a.peek());
System.out.println(a);
// 变成空栈
a.clear();
System.out.println(a.size()); // 0
}
}
链栈--链表实现
栈当然可以用链表实现。由于单链表有一个first指针始终指向链表的第一个结点。我们很容易想到将其用为栈顶指针。这样链表的头部就是栈顶。
直接使用以前写过的单链表代码，去掉last尾指针就好。
package Chap4;
import java.util.Iterator;
public class MyStack2<Item> implements Iterable<Item> {
private class Node {
Item data;
Node next;
}
// 指向第一个节点
private Node first;
private int N;
public MyStack2(Item... items) {
for (Item item : items) {
push(item);
}
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
// 表头插入元素
public void push(Item item) {
Node oldfirst = first;
first = new Node();
first.data = item;
first.next = oldfirst;
N++;
}
// 删除表头元素
public Item pop() {
Item item = first.data;
Node next = first.next;
// 这两行有助于垃圾回收
first.data = null;
first.next = null;
first = next;
N--;
return item;
}
public Item peek() {
return first.data;
}
public void clear() {
while (first != null) {
Node next = first.next;
// 下面两行帮助垃圾回收
first.next = null;
first.data = null;
first = next;
}
N = 0;
}
@Override
public String toString() {
Iterator<Item> it = iterator();
if (!it.hasNext()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
while (true) {
Item item = it.next();
sb.append(item);
if (!it.hasNext()) {
return sb.append("]").toString();
}
sb.append(", ");
}
}
@Override
public Iterator<Item> iterator() {
return new Iterator<Item>() {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.data;
current = current.next;
return item;
}
};
}
public static void main(String[] args) {
MyStack2<String> a = new MyStack2<>("I", "have", "a", "dream.");
System.out.println(a);
a.pop();
a.push("pig.");
System.out.println(a.peek());
a.clear();
System.out.println(a.isEmpty());
}
}
比较顺序栈和链栈，操作数据的时间复杂度都是O(1)。由于顺序栈的实现采用了适应容量的手段，所以我们也不用担心数据量过大导致上溢。但是每次resize调整容量，每次都会增大一倍空间，当数据量较大时，这会是个很大的数字！如果我们拿捏不准数据具体有多少，浪费内存空间几乎时避免不了的。但链栈不用担心这个问题，它是新添加一个结点，才开辟一份内存，但是由于每个结点都含有指针域Node，这也会增大一部分内存开销。所以在这两种实现结构如何选择，主要看待处理的数据量。一般来说，如果数据不可预测且量比较大，使用链栈更好，如果数据在可控范围内且量不大，使用顺序栈也许好一些。
两栈共享空间
使用resize方法调整容量的手段可谓有利有弊。总的来说还是利大于弊的。浪费些内存总比有时候溢出好啊。如果规定了容量为500，那么就怎么也存不进第501个元素，很蛋疼。如果不使用resize手段，有没有其他方法呢？可使用一个数组存放两个栈的内容，中间未使用的区域两个栈中任一个都可以自由使用，这称为两栈共享空间。这要求我们两个栈的数据类型一致（肯定嘛，放在同一个数组里当然得一致）。示意图如下
使用两个指针分别表示两栈的栈顶，top1为栈1的栈顶，位于数组的左半部分；top2为栈2的栈顶，在数组的右半部分。
空栈的情况：
- 栈1空，则top1在数组头部以前，为-1，随着元素的添加，top1向后挪动，值递增。
- 栈2空，则top2在数组尾部之后，为a.length，随着元素的添加，top2向左挪动，值递减。
- 两栈都空，top1为-1，top2为a.length。
满栈的情况：
- 普通情况：top1和top2相邻（相遇），即满足
top1 + 1 == top2。想象一下，此时两栈之间已经没有共享空间了。无法再添加元素。
- 栈1满，栈2空。
top1 = a.length - 1而top2 = a.length同样满足普通情况下的等式条件。 - 栈2满，栈1空。
top1 = -1而top2 = 0同样满足普通情况下的等式。
综上满栈的时候使用条件top1 + 1 == top2判断即可。
先上代码
package Chap4;
public class SharedStack<Item> {
private Item[] a;
// 栈顶
private int top1;
private int top2;
public SharedStack(int maxsize) {
if (maxsize <= 0) {
maxsize = 512;
}
a = (Item[]) new Object[maxsize];
top1 = -1;
top2 = a.length;
}
public SharedStack() {
this(512);
}
public boolean isEmpty(int stackNumber) {
if (stackNumber == 1) {
return top1 == -1;
} else if (stackNumber == 2) {
return top2 == a.length;
}
return true;
}
public int size(int stackNumber) {
if (stackNumber == 1) {
return top1 + 1;
} else if (stackNumber == 2) {
return a.length - top2;
}
return 0;
}
public void push(int stackNumber, Item item) {
// 栈已满的状态，不能再添加
// 先判断这句，下面的就能正确处理了
if (top1 + 1 == top2) {
throw new RuntimeException("栈已满！");
} else if (stackNumber == 1) {
a[++top1] = item;
} else if (stackNumber == 2) {
a[--top2] = item;
}
}
// 选择弹出哪个栈的数据
public Item pop(int stackNumber) {
Item item = null;
if (stackNumber == 1) {
// 栈1空了
if (top1 == -1) {
throw new RuntimeException("栈1已空！");
} else {
item = a[top1--];
}
} else if (stackNumber == 2) {
// 栈2空了
if (top2 == a.length) {
throw new RuntimeException("栈2已空！");
} else {
item = a[top2++];
}
}
return item;
}
public String displayStack(int stackNumber) {
if (stackNumber == 1) {
if (top1 == -1) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int j = top1; j >= 0; j--) {
sb.append(a[j]);
if (j == 0) {
return sb.append("]").toString();
} else {
sb.append(", ");
}
}
} else if (stackNumber == 2) {
if (top2 == a.length) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int j = top2; j < a.length; j++) {
sb.append(a[j]);
if (j == a.length - 1) {
return sb.append("]").toString();
} else {
sb.append(", ");
}
}
}
return null;
}
public void clear(int stackNumber) {
if (stackNumber == 1) {
for (int j = top1; j >=0 ; j--) {
a[j] = null;
}
top1 = -1;
} else if (stackNumber == 2) {
for (int j = top2; j < a.length; j++) {
a[j] = null;
}
top2 = a.length;
}
}
public void clearAll() {
for (int i = 0; i < a.length; i++) {
a[i] = null;
}
top1 = -1;
top2 = a.length;
}
public static void main(String[] args) {
SharedStack<String> a = new SharedStack<>();
a.push(1, "a");
a.push(1, "b");
a.push(1, "c");
a.push(1, "d");
a.push(2, "4");
a.push(2, "3");
a.push(2, "2");
a.push(2, "1");
a.pop(2); // 1
a.pop(1); // d
System.out.println(a.size(2)); // 3
System.out.println(a.size(1)); // 3
System.out.println(a.displayStack(1)); // [c, b, a]
System.out.println(a.displayStack(2)); // [2, 3, 4]
a.clear(1);
a.push(1,"a");
System.out.println(a.displayStack(1)); // [a]
a.clearAll();
System.out.println(a.size(2)); // 0
}
}
主要思想都是利用传入的stackNumber参数选择一个栈进行操作。clearAll则清空所有栈到初始化状态。
push方法，注意是++top1和--top2，一开始这两个指针并没有指向数组（位于数组之外的两端），所以要先自增。而pop方法中使用top1--和top2++后自增是因为top1和top2指向的就是将要被弹出栈的元素。再就是注意push方法刚开始要先判断是否满栈，之后进行下面的操作时才不会出错。pop方法也要在自增自减的之前，判断是否已是空栈。
特别注意栈长度的计算，由于使用了栈顶指针，而通过栈顶指针计算栈的长度十分简单，就不必单独创建两个变量来存放栈的长度了。对于栈1，显然top1 + 1正是栈的长度这对于top1 == -1表示栈空时同样适用；对于栈2，a.length - top2正是栈的长度，这对于top2 == a.length栈空时同样适用。
可以看到两栈共享空间还是有总容量的限制，如果栈1和栈2同时增长，很快就会达到容量从而不能再添加元素到任何一个栈。但是光看一个栈，它的容量确实是动态变化的，只要还有共享空间可以使用。由此可见，两栈共享空间的结构最适合于一个栈增长另一个栈缩短的情况，这样容量还能暂时稳定在一个范围内。
by @sunhaiyu
2017.8.16
