栈（也被称作堆栈，一种遵循先进后出原则的数据结构）_先进后出栈

1. 栈（Stack）

栈（又被称作堆栈，但与堆不是同一个概念）是用来存放对象的一种特殊的容器，它是最基本的数据结构之一，遵循“先进后出（Last-in-first-out，LIFO）”的原则。

栈有两个端点，起始的一端被称作栈底，另一端被称作栈顶（可以添加新元素的一端），栈底固定，而栈顶浮动，且栈内元素的增减只能在栈顶实现。一般会用一个指针指向栈顶的位置，以方便入栈和出栈的操作。

入栈和出栈是栈的两个最基本的接口，分别代表向栈内添加或删除元素。

1.1 入栈（push）

我们可以往栈中添加对象，此操作被称为“入栈”，一般我们习惯用 push 表示将一个对象压至栈顶。

对于入栈操作而言，如果栈的容量是固定的，那入栈操作就可能会有栈溢出的风险，在实际编写代码时需要注意到这一点。

1.2 出栈（pop）

同样的也可以删除栈中的元素，此操作被称为“出栈”，一般习惯用 pop 表示将一个对象从栈顶移除。

对于出栈操作而言，存在“栈空”的风险，即进行出栈操作时，栈内已经没有元素了。

1.3 栈的抽象数据类型（栈ADT）

1.4 栈接口

/** 
* 栈接口
*/
public interface Stack {
	void push(Object o);
	Object pop() throws ExceptionStackEmpty;
	int getSize();
	boolean isEmpty(); 
	Object top() throws ExceptionStackEmpty;
}
1
2
3
4
5
6
7
8
9
10

可以使用官方的java.util.Deque接口（），里面给出了push()、pop()等方法。

2. 利用数组实现栈

2.1 栈的实现

利用数组很容易就可以实现栈这种数据结构。我们可以定义一个容量为N的数组用于存放栈的元素，让此数组下标为0的位置为栈底，并用一个变量top指向当前的栈顶。

由于Java数组元素的下标都是从0开始的，可以将变量top初始化为-1（栈空）。具体实现如下所示：

public class ExceptionStackFull extends RuntimeException {

	public ExceptionStackFull(String error) {
		super(error);
	}

}
1
2
3
4
5
6
7

public class ExceptionStackEmpty extends RuntimeException {

	public ExceptionStackEmpty(String error) {
			super(error);
	}

}
1
2
3
4
5
6
7

/**
* 借助定长数组实现Stack接口 
*/
public class ArrayStack implements Stack {
	private static final int CAPACITY = 1024;
	private int capacity;
	private Object[] arrayStack; 
	private int top; // 栈顶元素的位置
	
	public ArrayStack() {
		this(CAPACITY); 
	}

	public ArrayStack(int capacity) {
		this.capacity = capacity;
		arrayStack = new Object[capacity];
		top = -1;
	} 
	
	@Override
	public int getSize() {
		return (top + 1);
	}

	@Override
	public boolean isEmpty() {
		return (top < 0);
	}

	// 栈的容量有限时入栈操作可能使栈溢出
	@Override
	public void push(Object obj) throws ExceptionStackFull {
		if (getSize() == capacity) {
			throw new ExceptionStackFull("意外：栈溢出");
		}
		// 先移动指向栈顶的变量top，再压入对象
		arrayStack[++top] = obj;
	} 
	
	@Override
	public Object top() throws ExceptionStackEmpty {
		if (isEmpty()) {
			throw new ExceptionStackEmpty("意外：栈空");
		}
		return arrayStack[top];
	}
	
	@Override
	public Object pop() throws ExceptionStackEmpty {
		Object elem;
		if (isEmpty()) {
			throw new ExceptionStackEmpty("意外：栈空");
		}
		elem = arrayStack[top];
		// 先移除对象，后移动指向栈顶的变量top
		arrayStack[top--] = null;
		return elem;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

2.2 利用数组实现栈的优势与缺点

1. 优势：
   1） 实现简单
   2） 各方法的时间复杂度均为O(1)
2. 缺点：
   1） 若数组容量为N，则空间复杂度为O(N)，当栈中的元素较少时会造成空间的浪费
   2） 入栈操作会有栈溢出的风险

3. 利用单链表实现栈

3.1 栈的实现

为解决栈溢出和空间浪费的问题，我们可以用 “可变的数组” —— 链表来实现栈。

利用单链表也可以实现栈这一数据结构，具体实现如下：

/**
 * 单链表节点类
*/
public class Node {
	private Object element; // 数据对象
	private Node next; // 指向后继节点
	
	public Node() {
		this(null, null);
	}
	
	public Node(Object element, Node next) {
		this.element = element;
		this.next = next;
	}
	
	public Object getElement() {
		return element;
	}
	
	public Object setElement(Object element) {
		Object oldElem = element;
		this.element = element;
		return oldElem;
	}
	
	public Node getNext() {
		return next;
	}
	
	public void setNext(Node next) {
		this.next = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * 借助单链表实现Stack接口
*/
public class LinkedListStack implements Stack {
	private Node top;
	private int size;
	
	public LinkedListStack() {
		top = null;
		size = 0;
	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return (size == 0);
	}

	@Override
	public Object top() throws ExceptionStackEmpty {
		if (isEmpty()) {
			throw new ExceptionStackEmpty("意外：栈空");
		}
		return top.getElement();
	}

	@Override
	public void push(Object obj) {
		Node node = new Node(obj, top);
		top = node;
		size++;
	}

	@Override
	public Object pop() throws ExceptionStackEmpty {
		if (isEmpty()) {
			throw new ExceptionStackEmpty("意外：栈空");
		}
		Object returnElement = top.getElement();
		top = top.getNext();
		size--;
		return returnElement;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

3.2 利用单链表实现栈的优势与缺点

1. 优势：
   1） 栈中实际有n个元素，空间复杂度即为O(n)，空间利用效率较高
   2） 入栈操作不会有栈溢出的风险
2. 缺点：
   1） 较数组实现来说，再实现难度上略有增加
   2） 为保证所有方法的时间复杂度均为O(1)，需要有一个变量由于记录栈中元素的数目，且需把单链表的首节点作为栈顶。

4. 栈的应用

4.1 Java 虚拟机（JVM）中的栈

Java 的每一个程序都要被编译为一个二进制指令序列，这些指令可以在一个特定的计算模型 ——Java 虚拟机（Java Virtual Machine, JVM）上执行。对于 JVM 的定义而言，栈这一数据结构也是至关重要的。

任一运行中的Java程序（更准确地说，应该是运行中的Java线程）都会配备一个私有的栈，称作Java方法栈（Java method stack）或简称Java栈（Java stack），用来记录各个方法在被调用过程中的局部变量等重要信息。

JVM 还设置了一个被称作程序计数器（Program counter）的变量PC，负责记录程序在 JVM 中运行时的当前位置。当方法 N 要调用方法 M 时，程序计数器当前的数值就会被存放在 N 的实例所 对应的帧中⎯⎯这样，待M执行完毕后，JVM才能知道应该返回到什么位置并继续执行下去。

上图是一个Java方法栈的实例，如图所示，JVM通过栈实现了方法的调用，同时将参数以值传递的方式传递给被调用的方法。

实际上，JVM 对栈的应用并不仅限于方法栈。在对算术表达式进行求值时，JVM 也使用了另一个栈——操作数栈（Operand stack）。

以“a+b”为例，为了计算其值，首先将 a 和 b 依次压入栈中，然后执行一条专门的指令。该指令要求将栈顶的两个元素弹出，对它们实施加法，并将结果重新压入栈中。

4.2 其他应用

除了在JVM中，栈在其它地方也有着广泛的应用，例如：

1. 撤销操作
2. 中断
3. 实现一组数据的倒置
4. 表达式中括号的匹配