栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说，它们也是线性结构，
与线性表不同的是它们所支持的基本操作是受到限制的，它们是操作受限的线性表，是一种
限定性的数据结构。 栈（stack）又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶（top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底（bottom）。
当栈中没有数据元素时称为空栈；向一个栈插入元素又称为进栈或入栈；从一个栈中删除元素又称为出栈或退栈。由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为后进先出表（Last In First Out，简称LIFO）。
public interface Stack {
//返回堆栈的大小
public int getSize();
//判断堆栈是否为空
public boolean isEmpty();
//数据元素e 入栈
public void push(Object e);
//栈顶元素出栈
public Object pop() throws StackEmptyException;
//取栈顶元素
public Object peek() throws StackEmptyException;
}
public class StackEmptyException extends RuntimeException{
public StackEmptyException(String err) {
super(err);
}
} Stack 的顺序存储实现：public class StackArray implements Stack {
private final int LEN = 8; //数组的默认大小
private Object[] elements; //数据元素数组
private int top; //栈顶指针
public StackArray() {
top = -1;
elements = new Object[LEN];
}
//返回堆栈的大小
public int getSize() {
return top + 1;
}
//判断堆栈是否为空
public boolean isEmpty() {
return top < 0;
}
//数据元素e 入栈
public void push(Object e) {
if (getSize() >= elements.length)
expandSpace();
elements[++top] = e;
}
private void expandSpace(){
Object[] a = new Object[elements.length * 2];
for (int i = 0; i < elements.length; i++)
a[i] = elements[i];
elements = a;
}
//栈顶元素出栈
public Object pop() throws StackEmptyException {
if (getSize() < 1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = elements[top];
elements[top--] = null;
return obj;
}
//取栈顶元素
public Object peek() throws StackEmptyException {
if (getSize() < 1)
throw new StackEmptyException("错误，堆栈为空。");
return elements[top];
}
} Stack 的链式存储实现：public class StackSLinked implements Stack {
private SLNode top; //链表首结点引用
private int size; //栈的大小
public StackSLinked() {
top = null;
size = 0;
}
//返回堆栈的大小
public int getSize() {
return size;
}
//判断堆栈是否为空
public boolean isEmpty() {
return size == 0;
}
//数据元素e 入栈
public void push(Object e) {
SLNode q = new SLNode(e, top);
top = q;
size++;
}
//栈顶元素出栈
public Object pop() throws StackEmptyException {
if (size < 1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = top.getData();
top = top.getNext();
size--;
return obj;
}
//取栈顶元素
public Object peek() throws StackEmptyException {
if (size < 1)
throw new StackEmptyException("错误，堆栈为空。");
return top.getData();
}
} 队列：它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）。向队尾插入元素称为进队或入队，新元素入队后成为新的队尾元素；从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。
由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队，也就是说先进队的元素必然先离队，所以称队列为先进先出表（First In First Out,简称FIFO）。 public interface Queue {
//返回队列的大小
public int getSize();
//判断队列是否为空
public boolean isEmpty();
//数据元素e 入队
public void enqueue(Object e);
//队首元素出队
public Object dequeue() throws QueueEmptyException;
//取队首元素
public Object peek() throws QueueEmptyException;
}
public class QueueEmptyException extends RuntimeException {
public QueueEmptyException(String err) {
super(err);
}
}
Queue 的顺序存储实现：public class QueueArray implements Queue {
private static final int CAP = 7;//队列默认大小
private Object[] elements; //数据元素数组
private int capacity; //数组的大小elements.length
private int front; //队首指针,指向队首
private int rear; //队尾指针,指向队尾后一个位置
public QueueArray() {
this(CAP);
}
public QueueArray(int cap){
capacity = cap + 1;
elements = new Object[capacity];
front = rear = 0;
}
//返回队列的大小
public int getSize() {
return (rear - front + capacity) % capacity;
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//数据元素e 入队
public void enqueue(Object e) {
if (getSize() == capacity - 1)
expandSpace();
elements[rear] = e;
rear = (rear + 1) % capacity;
}
private void expandSpace(){
Object[] a = new Object[elements.length * 2];
int i = front;
int j = 0;
//将从front 开始到rear 前一个存储单元的元素复制到新数组
while (i != rear){
a[j++] = elements[i];
i = (i + 1) % capacity;
}
elements = a;
capacity = elements.length;
front = 0;
rear = j; //设置新的队首、队尾指针
}
//队首元素出队
public Object dequeue() throws QueueEmptyException {
if (isEmpty())
throw new QueueEmptyException("错误：队列为空");
Object obj = elements[front];
elements[front] = null;
front = (front + 1) % capacity;
return obj;
}
//取队首元素
public Object peek() throws QueueEmptyException {
if (isEmpty())
throw new QueueEmptyException("错误：队列为空");
return elements[front];
}
}Queue 的链式存储实现：public class QueueSLinked implements Queue {
private SLNode front;
private SLNode rear;
private int size;
public QueueSLinked() {
front = new SLNode();
rear = front;
size = 0;
}
//返回队列的大小
public int getSize() {
return size;
}
//判断队列是否为空
public boolean isEmpty() {
return size == 0;
}
//数据元素e 入队
public void enqueue(Object e) {
SLNode p = new SLNode(e, null);
rear.setNext(p);
rear = p;
size++;
}
//队首元素出队
public Object dequeue() throws QueueEmptyException {
if (size < 1)
throw new QueueEmptyException("错误：队列为空");
SLNode p = front.getNext();
front.setNext(p.getNext());
size--;
if (size < 1)
rear = front; //如果队列为空,rear 指向头结点
return p.getData();
}
//取队首元素
public Object peek() throws QueueEmptyException {
if (size < 1)
throw new QueueEmptyException("错误：队列为空");
return front.getNext().getData();
}
}