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

栈是一种遵循先进后出原则的数据结构，在实际开发中有着广泛的应用（例如Java虚拟机中的操作数栈）。本文主要介绍了栈的定义、利用数组实现栈、利用链表实现栈等内容。

JuBlog

5648人浏览 · 2020-11-18 21:59:03

JuBlog · 2020-11-18 21:59:03 发布

1. 栈（Stack）

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

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

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

1.1 入栈（push）

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

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

入栈操作

1.2 出栈（pop）

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

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

出栈操作

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

方法	功能描述
push(x)	若栈未满，则将对象x压至栈顶，否则报错
pop()	若栈非空，则将栈顶的对象移除，并将其返回，否则报错
getSize()	返回当前栈中对象的数目
isEmpty()	用于检测栈是否为空
top()	若栈非空，则返回栈顶的对象（但并不移除），否则报错

1.4 栈接口

/** 
* 栈接口
*/
public interface Stack {
	void push(Object o);
	Object pop() throws ExceptionStackEmpty;
	int getSize();
	boolean isEmpty(); 
	Object top() throws ExceptionStackEmpty;
}

可以使用官方的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);
	}

}

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;
	}

}

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

优势：
1）实现简单
2）各方法的时间复杂度均为O(1)
缺点：
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;
	}
}

/**
 * 借助单链表实现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;
	}

}