栈
- 栈（stack）又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一端进行插入 和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操 作的一端称为栈顶（top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底 （bottom）。
- 当栈中没有数据元素时称为空栈；向一个栈插入元素又称为进栈或入栈；从一个栈中删除元素又称为出栈或退栈。由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为后进先出表（Last In First Out，简称 LIFO）.如图所示：
Stack 接口
package com.wjy.Data_Structure.stack;
//Stack 接口
public interface Stack {
/**
* 返回堆栈的大小
*
* @return
*/
public int getSize();
/**
* 判断堆栈是否为空
*
* @return
*/
public boolean isEmpty();
/**
* 数据元素 e 入栈
*
* @param c
*/
public void push(Object e);
/**
* 栈顶元素出栈
*
* @return
* @throws StackEmptyException
*/
public Object pop() throws StackEmptyException;
/**
* 取栈顶元素
*
* @return
* @throws StackEmptyException
*/
public Object peek() throws StackEmptyException;
}
package com.wjy.Data_Structure.stack;
//堆栈为空时抛出此异常
public class StackEmptyException extends RuntimeException {
private static final long serialVersionUID = 1L;
public StackEmptyException(String err) {
super(err);
}
}
和线性表类似，堆栈也有两种基本的存储结构：顺序存储结构和链式存储结构。
栈的顺序存储实现
-
顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈 中的数据元素。由于堆栈是一种特殊的线性表，因此在线性表的顺序存储结构的基础上，选 择线性表的一端作为栈顶即可。根据数组操作的特性，选择数组下标大的一端，即线性表顺序存储的表尾来作为栈顶。
-
由于堆栈的操作都在栈顶完成，因此在顺序栈的实现中需要附设一个指针 top 来动态的
指示栈顶元素在数组中的位置。通常top可以用栈顶元素所在数组下标来表示，top= -1 时表 示空栈。
package com.wjy.Data_Structure.stack;
//Stack的顺序存储实现
public class StackArray implements Stack {
private final int LEN = 8; // 数组的默认大小
private Object[] elements; // 数据元素数组
private int top; // 栈顶指针
public StackArray() {
this.top = -1; // 表示空栈
this.elements = new Object[LEN];
}
private void expandSpace() {
Object[] a = new Object[elements.length * 2];
for (int i = 0; i < elements.length; i++)
a[i] = elements[i];
elements = a;
}
@Override
public int getSize() {
return top + 1;
}
@Override
public boolean isEmpty() {
return top < 0;
}
@Override
public void push(Object e) {
if (getSize() >= elements.length)
expandSpace();
elements[++top] = e;
}
@Override
public Object pop() throws StackEmptyException {
if (getSize() < 1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = elements[top];
elements[top--] = null;
return obj;
}
@Override
public Object peek() throws StackEmptyException {
if (getSize() < 1)
throw new StackEmptyException("错误，堆栈为空");
return elements[top];
}
}
栈的链式存储实现
- 链栈即采用链表作为存储结构实现的栈。由于堆栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可以。使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；使用不带头结点的 单链表时，结点的插入和删除都在链表的首结点上进行。
如图使用不带头结点的单链表
上图中top 为栈顶结点引用，始终指向当前栈顶元素所在结点。若 top 为 Null，则 表示空栈。入栈操作是在 top 所指结点之前插入新的结点，对照图 4-2 可以看到，当链表为 空和不为空时，入栈操作的实现都一样，可以使用以下语句来实现
SLNode q = new SLNode(e,top);
结点 q 的 next 域指向 top，不管 top 是否为 Null top = q; 同样对于出栈操作而言，不管堆栈在删除栈顶元素之后，栈是否为空，出栈操作都是将top后移。
package com.wjy.Data_Structure.stack;
import com.wjy.Data_Structure.linearlist.common.SLNode;
//Stack 的链式存储实现
public class StackSLinked implements Stack {
private SLNode top; // 链表首结点引用
private int size; // 栈的大小
public StackSLinked() {
top = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void push(Object e) {
SLNode q = new SLNode(e, top);
top = q;
size++;
}
@Override
public Object pop() throws StackEmptyException {
if (size < 1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = top.getData();
top = top.getNext();
size--;
return obj;
}
@Override
public Object peek() throws StackEmptyException {
if (size < 1)
throw new StackEmptyException("错误，堆栈为空。");
return top.getData();
}
}