栈

栈的实现

链表

代码实现：

public class Main{
	Node top = null; //栈顶，也就是链表的头节点

	/**
	一般没必要这样写，太麻烦，直接定义全局变量就行
	class MyStack{
		Node top = null;
		int size;
	}
	**/

	//结点类
	class Node{
		Node next;
		int val;
		public Node(int val){
			this.val = val;
		}
	}

	……
}

数组（需要考虑扩容）

扩容：数组放满时，新建一个容量为当前数组容量两倍的扩容数组，再把当前数组的值全部复制到扩容数组内。

扩容的方法：

System.arraycopy(array,0,arrayBig,array.length); //把旧数组复制到新数组

代码实现：

public class Main{
	int[] data;	 // 数组栈
	int top;	 // 栈顶下标。top = -1 时栈空
	int maxSize; // 堆栈最大容量

	/**
	一般没必要这样写，太麻烦，直接定义全局变量就行
	class MyStack{
		int[] data;
		int top;
		int maxSize; 
		public MyStack(int maxSize){
			this.maxSize = maxSize;
			data = new int[maxSize];
		}
	}
	**/
	
	// 方法。实例化数组栈
	public void createStack(int n){
		maxSize = n;
		data = new int[maxSize];
	}
	
	// 拓展方法。数组扩容（一般用不到）
	public void reSize(){
		int[] dataBig = new int[maxSize*2];
		System.arraycopy(data,0,dataBig,data.length);
		data = dataBig;
	}

	……
}

栈的一些API

实例化栈类

Stack<Integer> os = new Stack<>();	// 老方法
Deque<Integer> ns = new LinkedList<>(); //官方推荐，实际上是双端队列类，也可以当成栈使用

入栈

os.push(3);
ns.push(3); or ns.addFirst(3);

出栈(删除栈顶元素并返回)

os.pop();
ns.pop(); or ns.removeFirst();

判断栈是否为空

if(os.empty())
if(ns.isEmpty()) or if(ns.peekFirst == null)

得到栈顶元素

Integer top = os.peek();
Integer top = ns.peek() or ns.peekFirst()

得到栈的大小

int size = os.size();
int size = ns.size();