大话数据结构六：特殊的线性表（栈）

1. 什么是栈？

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

2. 栈的特点：

1.） 栈又称为后进先出（Last In First out）的线性表，栈元素具有线性关系，即前驱后继关系。

2.） 栈的特殊之处在于：它的栈底是固定的，只允许在栈顶进行插入和删除操作。

3. 栈的顺序存储结构(Java数组实现)：

// 栈的数组实现, 底层使用数组:
public class ArrayStack<T> {
	private Object[] arr; // 数组首元素作为栈底,因为它变化小
	private int length;
	
	// 数据初始化
	public ArrayStack(){
		arr = new Object[16];
		length = 0;
	}
	
	// 元素入栈
	public boolean push(T data) {
		if (length >= arr.length) { // 判断是否需要进行数组扩容
			resize();
		}
		arr[length++] = data;
		return true;
	}
	
	// 元素出栈
	@SuppressWarnings("unchecked")
	public T pop() {
		if (length == 0) {
			return null;
		}
		return (T) arr[--length];
	}
	
	// 将数组中的数据置为null, 方便GC进行回收 
	public void clear() {
		for (int i = 0; i < length; i++) {
			arr[length] = null; 
		}
		length = 0;
	}

	// 数组扩充容量
	private void resize() {
		Object[] temp = new Object[arr.length * 3 / 2 + 1];
		for (int i = 0; i < length; i++) {
			temp[i] = arr[i];
			arr[i] = null;
		}
		arr = temp;
	}
	
	// 获取栈中元素个数
	public int length() {
		return length;
	}
	
	// 判断数组是否为空
	public boolean isEmpty() {
		return length == 0;
	}
	
	// 打印栈中元素
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < length; i++) {
			sb.append(arr[i].toString());
			if (i != length - 1) {
				sb.append(", ");
			}
		}
		return sb.toString();
	}
	
	public static void main(String[] args) {
		ArrayStack<Integer> stack = new ArrayStack<Integer>();  
		long start = System.currentTimeMillis();  
		for (int i = 0; i < 1000000; i++) {  
			stack.push(i); // 入栈
		}  
		long temp = System.currentTimeMillis();  
		System.out.println("push time: " + (temp - start));  
		while (stack.pop() != null){  
			 ; // 出栈
		}
		System.out.println("pop time: " + (System.currentTimeMillis() - temp));
	}
}

运行时间:
	push time: 257ms
	pop time: 5ms

4. 栈的链式存储结构(Java链表实现)：

// 结点元素
public class Node<T> {
	private Node<T> prev; // 记住当前结点的前一结点
	private T data; // 数据域

	public Node() {
	}

	public Node(T data, Node<T> prev) {
		this.data = data;
		this.prev = prev;
	}

	public Node<T> getPrev() {
		return prev;
	}

	public void setPrev(Node<T> prev) {
		this.prev = prev;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}
}

// 栈的链表实现, 底层使用单链表:
public class LinkedStack<T> {
	private Node<T> top; // 栈顶指针(链表尾结点)
	private int size; // 栈的长度

	// 数据初始化
	public LinkedStack() {
		top = null;
		size = 0;
	}
	
	// 结点入栈
	public boolean push(T data) {
		Node<T> newNode = new Node<T>(data,top); // 将top设置为新节点的前驱结点
		top = newNode; // 将新结点设置为栈顶指针
		size++;
		return true;
	}
	
	// 结点出栈
	public T pop() {
		if (top != null) {
			Node<T> tempNode = top; 
			top = top.getPrev(); // 将栈顶指针的前驱结点设置为栈顶指针
			size--;
			return tempNode.getData();
		}
		return null;
	}
	
	// 判断栈是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	
	// 获取栈的长度
	public int length() {
		return size;
	}
	
	// 打印栈中元素
	public String toString() {
		Node<T> node = top;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < size; i++) {
			sb.append(node.getData().toString());
			if (i != size - 1) {
				sb.append(", ");
			}
			node = node.getPrev();
		}
		return sb.reverse().toString();
	}
	
	public static void main(String[] args) {
		LinkedStack<Integer> stack = new LinkedStack<Integer>();
		long start = System.currentTimeMillis();  
		for (int i = 0; i < 1000000; i++) {  
			stack.push(i); // 入栈
		}  
		long temp = System.currentTimeMillis();  
		System.out.println("push time: " + (temp - start));  
		while (stack.pop() != null){  
			;  // 出栈
		}
		System.out.println("pop time: " + (System.currentTimeMillis() - temp));
	}
}

运行时间:
	push time: 986ms
	pop time: 15ms

5. 两种实现方式比较：

通过入栈和出栈时间比较可以看出,数组实现在性能上还是有明显优势的，这是因为数组实现的栈在增加和删除元素时并不需要移动大量的元素，只是在扩大数组容量时，需要进行拷贝。然而链表实现的栈在入栈时需要将数据包装成Node，出栈时需要从Node中取出数据，同时还要维护栈顶指针和前驱指针。

6. JDK API中的栈:

1.) java.util.Stack: 一个普通的顺序栈，底层基于数组实现。这个类是线程安全的。
2.) java.util.LinkedList: 一个双向链表，线程不安全，可以当做栈来使用。在多线程环境下可以使用Collections类的工具方法将其改造成线程安全类。

3.) 两个类都提供了push()，pop()，peek()等方法。