堆栈（stack）是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入和删除操作的一端称为栈顶，最下面的那一端称为栈底。栈顶是动态的，它由一个称为栈顶指针的位置指示器指示。当栈中没有数据元素时，为空栈。堆栈的插入操作称为进栈或入栈，堆栈的删除操作称为出栈或退栈。
栈的主要特点是“后进先出”，即后进栈的元素先被处理。因此，栈又被称为后进先出（last in first out，LIFO）表。它的实现方式主要有顺序栈、链栈两种。
堆栈的抽象数据类型
- 数据元素：可以为任意类型，只要同属于一种数据类型即可；
- 数据关系：数据元素之间呈线性关系；
- 数据操作：对堆栈的基本操作定义在IStack中，代码如下：
public interface IStack<E> {
E push(E item); //入栈
E pop(); //出栈
E peek(); //取栈顶元素
int size(); //返回栈中元素的个数
boolean empty(); //判断栈是否为空
}
顺序栈
用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈。类似于顺序表，用一维数组来存放顺序栈中的数据元素。栈顶指示器top设在数组下标为最大的那一端，top随着插入或删除而变化。即当栈为空时，top=-1；其他时候，top为栈顶元素的索引号。
public class SeqStack<E> implements IStack<E> {
private int maxsize; // 顺序栈的容量
private E[] data; // 数组，用于存储顺序栈中的数据元素
private int top; // 指示顺序栈的栈顶
// 初始化栈
@SuppressWarnings("unchecked")
public SeqStack(Class<E> type, int size) {
data = (E[]) Array.newInstance(type, size);
maxsize = size;
top = -1;
}
// 入栈操作
public E push(E item) {
if (!isFull()) {
data[++top] = item;
return item;
}
else
return null;
}
// 出栈操作
public E pop() {
E item = null;
if (!empty()) {
item = data[top--];
}
return item;
}
// 获取栈顶数据元素
public E peek() {
E item = null;
if (!empty()) {
item = data[top];
}
return item;
}
//求栈的长度
public int size() {
return top+1;
}
// 判断顺序栈是否为空
public boolean empty() {
if (top == -1) {
return true;
} else {
return false;
}
}
// 判断顺序栈是否为满
public boolean isFull() {
if (top == maxsize - 1) {
return true;
} else {
return false;
}
}
}
链栈
用链式存储结构存储的栈称为链栈，链栈通常用单链表来表示。它的结点结构与单链表的结构一样，都是由数据域data和引用域next两部分组成。由于链栈的操作只在一段进行（栈顶），为了操作方便，我们将栈顶设在链表的头部，即将栈顶指示器指向链表的头部，所有对栈的数据元素的增加和删除操作都在链表头部进行。
public class StackNode<E> {
private E data; // 数据域
private StackNode<E> next; // 引用域
//构造函数
public StackNode(){}
public StackNode(E data) {
this.data = data;
}
public StackNode(E data, StackNode<E> next) {
super();
this.data = data;
this.next = next;
}
//数据域get属性
public E getData() {
return data;
}
//数据域set属性
public void setData(E data) {
this.data = data;
}
//引用域get属性
public StackNode<E> getNext() {
return next;
}
//引用域get属性
public void setNext(StackNode<E> next) {
this.next = next;
}
}
public class LinkStack<E> implements IStack<E> {
private StackNode<E> top; // 栈顶指示器
private int size; // 栈中结点的个数
// 初始化链栈
public LinkStack() {
top = null;
size = 0;
}
// 入栈操作
public E push(E item) {
StackNode<E> newnode = new StackNode<E>(item);
if (!empty())
newnode.setNext(top);
top = newnode;
++size;
return item;
}
// 出栈操作
public E pop() {
E item=null;
if (!empty())
{
item = top.getData();
top = top.getNext();
size--;
}
return item;
}
// 获取栈顶数据元素
public E peek() {
E item=null;
if (!empty())
{
item=top.getData();
}
return item;
}
// 求栈的长度
public int size() {
return size;
}
// 判断顺序栈是否为空
public boolean empty() {
if ((top == null) && (size == 0))
{
return true;
}
else
{
return false;
}
}
}
总结与分析
- 位于java.util.Stack具有顺序栈的功能，LinkedList类提供了在列表开始与结尾添加、删除和显示数据元素的方法，使用这些方法把一个LinkedList当做链栈使用。