栈（又被称作堆栈，但与堆不是同一个概念）是用来存放对象的一种特殊的容器，它是最基本的数据结构之一，遵循“先进后出（Last-in-first-out，LIFO）”的原则。
栈有两个端点，起始的一端被称作栈底，另一端被称作栈顶（可以添加新元素的一端），栈底固定，而栈顶浮动，且栈内元素的增减只能在栈顶实现。一般会用一个指针指向栈顶的位置，以方便入栈和出栈的操作。
入栈和出栈是栈的两个最基本的接口，分别代表向栈内添加或删除元素。
我们可以往栈中添加对象，此操作被称为“入栈”，一般我们习惯用 push 表示将一个对象压至栈顶。
对于入栈操作而言，如果栈的容量是固定的，那入栈操作就可能会有栈溢出的风险，在实际编写代码时需要注意到这一点。
同样的也可以删除栈中的元素，此操作被称为“出栈”，一般习惯用 pop 表示将一个对象从栈顶移除。
对于出栈操作而言，存在“栈空”的风险，即进行出栈操作时，栈内已经没有元素了。
| 方法 | 功能描述 |
|---|---|
| push(x) | 若栈未满，则将对象x压至栈顶，否则报错 |
| pop() | 若栈非空，则将栈顶的对象移除，并将其返回，否则报错 |
| getSize() | 返回当前栈中对象的数目 |
| isEmpty() | 用于检测栈是否为空 |
| top() | 若栈非空，则返回栈顶的对象（但并不移除），否则报错 |
/**
* 栈接口
*/
public interface Stack {
void push(Object o);
Object pop() throws ExceptionStackEmpty;
int getSize();
boolean isEmpty();
Object top() throws ExceptionStackEmpty;
}
可以使用官方的java.util.Deque接口（），里面给出了push()、pop()等方法。
利用数组很容易就可以实现栈这种数据结构。我们可以定义一个容量为N的数组用于存放栈的元素，让此数组下标为0的位置为栈底，并用一个变量top指向当前的栈顶。
由于Java数组元素的下标都是从0开始的，可以将变量top初始化为-1（栈空）。具体实现如下所示：
public class ExceptionStackFull extends RuntimeException {
public ExceptionStackFull(String error) {
super(error);
}
}
public class ExceptionStackEmpty extends RuntimeException {
public ExceptionStackEmpty(String error) {
super(error);
}
}
/**
* 借助定长数组实现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;
}
}
为解决栈溢出和空间浪费的问题，我们可以用 “可变的数组” —— 链表来实现栈。
利用单链表也可以实现栈这一数据结构，具体实现如下：
/**
* 单链表节点类
*/
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;
}
}
/**
* 借助单链表实现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;
}
}
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 依次压入栈中，然后执行一条专门的指令。该指令要求将栈顶的两个元素弹出，对它们实施加法，并将结果重新压入栈中。
除了在JVM中，栈在其它地方也有着广泛的应用，例如：