2.11. 链式栈¶
2.11.1. 链式栈实现¶
链式栈的实现非常简单。元素仅在列表头部插入和删除。不使用头节点，因为零个或一个元素的列表不需要特殊情况的代码。以下是完整的链式栈实现。
// Linked stack implementation
class LStack implements Stack {
private Link top; // Pointer to first element
private int size; // Number of elements
// Constructors
LStack() { top = null; size = 0; }
LStack(int size) { top = null; size = 0; }
// Reinitialize stack
public void clear() { top = null; size = 0; }
// Put "it" on stack
public boolean push(Object it) {
top = new Link(it, top);
size++;
return true;
}
// Remove "it" from stack
public Object pop() {
if (top == null) return null;
Object it = top.element();
top = top.next();
size--;
return it;
}
public Object topValue() { // Return top value
if (top == null) return null;
return top.element();
}
// Return stack length
public int length() { return size; }
// Check if the stack is empty
public boolean isEmpty() { return size == 0; }
}
// Linked stack implementation
class LStack<E> implements Stack<E> {
private Link<E> top; // Pointer to first element
private int size; // Number of elements
// Constructors
LStack() { top = null; size = 0; }
LStack(int size) { top = null; size = 0; }
// Reinitialize stack
public void clear() { top = null; size = 0; }
// Put "it" on stack
public boolean push(E it) {
top = new Link<E>(it, top);
size++;
return true;
}
// Remove "it" from stack
public E pop() {
if (top == null) { return null; }
E it = top.element();
top = top.next();
size--;
return it;
}
public E topValue() { // Return top value
if (top == null) { return null; }
return top.element();
}
// Return stack length
public int length() { return size; }
// Tell if the stack is empty
public boolean isEmpty() { return size == 0; }
}
这是链式栈的可视化表示。
2.11.1.1. 链式栈压入¶
2.11.2. 链式栈出栈¶
2.11.2.1. 基于数组的栈与基于链表的栈比较¶
基于数组的栈实现和链式栈实现的所有操作都只需常数时间，因此从时间效率的角度来看，两者都没有显著优势。 另一个比较的依据是所需的总空间，其分析与针对线性表实现的分析类似。 基于数组的栈必须在开始时声明一个固定大小的数组，只要栈未满，其中一部分空间就被浪费了。 链式栈可以收缩和增长，但每个元素都需要一个链接字段带来的额外开销。
在实现多个栈时，有时可以利用基于数组的栈的单向增长特性，用单个数组来存储两个栈。 如下图所示，一个栈从数组的一端向内增长，另一个从另一端向内增长，希望借此减少浪费的空间。 然而，只有当两个栈的空间需求呈负相关时，这种做法才效果好。 换句话说，理想情况下，当一个栈增长时，另一个栈会收缩。 当元素从一个栈取出并放入另一个栈时，这种做法尤其有效。 反之，如果两个栈同时增长，数组中部的空闲空间很快就会耗尽。
