Stack 的链表实现与数组实现

作者 QIFAN 日期 2017-01-10

使用数组和 LinkedList 实现 Stack 。




Stack 是一种遵循 LIFO (后入先出)规则的一种数据结构。

Stack

使用范围相比 Array 来说比较受限,一般说来,可考虑 Stack 的情况有:

  • 先入后出
  • size 比较小(定长)

应用:反转字符串

Stack API

通过想象 Stack 的使用场景,我们会发现以下操作需求:

public class StackInterface<T> {
// 进栈
public void push(T item);
// 出栈
public T pop();
// 返回栈顶
public T peek();
// 是否为空
public boolean isEmpty();
}

Array 实现

public class ArrayStack<T> implements StackInterface<T> {
T[] stack;
int topIndex;
public ArrayStack(int capacity) {
// java 不允许直接创建通用数组
stack = (T[]) new Object[capacity];
topIndex = -1;
}
public void push(T item) {
if (topIndex == stack.length - 1) {
resizing();
}
stack[++topIndex] = item;
}
public T pop() {
if (isEmpty()) {
return null;
}
T item = stack[topIndex];
// avoid loitering
stack[topIndex--] = null;
return item;
}
public T peek() {
return stack[topIndex];
}
public boolean isEmpty() {
return topIndex == -1;
}
}

这里的 resize() 与在数组结构中提到的一样:

  • case 1 增长: push 时数组已满。将数组长度扩大两倍,再将原数组中的元素复制到新数组中。时间复杂度为 $O(n)$
  • case 2 收缩:
    当当前元素数量只有数组长度的四分之一时,将数组长度缩小为原来的二分之一。(思考:为什么是四分之一?)

Loitering
注意到我 pop() 时这一步:

stack[topIndex--] = null;

这里英文叫做 Loitering ,我翻译成“占着茅坑不拉屎”。就是为了不让指针指向已废弃的对象,这也是为了系统更好的“垃圾回收”。

若用数组实现 Stack 的功能,各项操作的时间复杂度为:

  • push() $O(1)$ 摊销常数
  • pop() $O(1)$
  • peek() $O(1)$

LinkedList 实现

public class LinkedListStack<T> implements StackInterface<T> {
Node<T> first;
public LinkedListStack() {
first = null;
}
public void push(T item) {
if (isEmpty()) {
first = new Node(item, null);
}
first = new Node(item, first);
}
public T pop() {
if (isEmpty()) {
return null;
}
T item = first.data;
first = first.next;
return item;
}
public T peek() {
if (isEmpty()) {
return null;
}
return first.data;
}
public boolean isEmpty() {
return first == null;
}
static class Node<T> {
private T data;
private Node<T> next;
Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
}

不难看出,Stack 的 push() 对应着 LinkedList 的 addFirst()pop() 对应着 deleteFirst()

若用 LinkedList 实现 Stack 的功能,各项操作的时间复杂度为:

  • push() $O(1)$
  • pop() $O(1)$
  • peek() $O(1)$

不同实现方式时间空间分析

回顾一下两种实现方式的时间复杂度

操作 数组 LinkedList
push() $O(1)^*$ 摊销常数 $O(1)$
pop() $O(1)$ $O(1)$
peek() $O(1)$ $O(1)$

看上去似乎是 LinkedList 更优一些,再来看一下空间,顺便回顾一下空间计算。

对于含有 N 个元素的 Stack。

  • 数组实现
    $O(N)$ 空间。更精确一些,一个对象引用占 8 个字节,所以是 ~$8N$
  • LinkedList 实现
    这里含有一个嵌套类 Node ,一个 Node 对象占 40 字节(计算方式见下),N 个元素就是 ~$40N$ 。
    16 对象头部
    8 内部类额外头部空间
    8 data 引用
    + 8 next 引用
    ------------------------
    40

在内存上,数组实现明显更优一些。

完整代码

ArrayStack.java | LinkedListStack.java


相关文章:
算法分析方法 | 数组结构 | 链式结构


更新历史

  • 2017.01.10 第一版
  • 2017.01.11 添加完整代码文件