一、栈
栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。允许操作的一端为栈顶（top），不允许操作的一端称为栈底（bottom）。栈中插入元素的操作称为入栈（push），删除元素的操作称为出栈（pop）。栈又称为后进先出（last in first out）表。
下列代码为栈接口SStack.java。
public interface SStack<T> {//栈借口，栈抽象数据类型
boolean isEmpty();//判断是否为空栈
void push(T x);
T pop();
T get();
}（一）顺序栈
采用顺序存储结构的栈称为顺序栈。下列代码为顺序栈的实现，SeqStack.java
public class SeqStack<T> implements SStack<T> {//顺序栈类，实现栈接口
private Object element[]; //存储栈数据元素的数组
private int top; //栈顶元素下标
public SeqStack (int size){//构造容量为size的栈
this.element = new Object[Math.abs(size)];
this.top = -1;
}
public SeqStack(){ this(64); }//构造默认容量的栈
public boolean isEmpty(){ return this.top == -1; }//判断栈是否为空，若空返回-1
public void push (T x){
if(x==null){//空对象不能入栈
return;
}
if(this.top==element.length-1){//若栈满，则扩充栈容量
Object[] temp = this.element;
this.element = new Object[temp.length*2];
for (int i= 0;i<temp.length;i++){
this.element[i]=temp[i];
}
}
this.top++;
this.element[this.top] = x;
}
public T pop()
{
return this.top==-1?null:(T)this.element[this.top--];
}
public T get(){
return this.top==-1?null:(T)this.element[this.top--];
}
}
（二）链式栈
采用链式存储结构的栈称为链式栈。
package stack;
public class LinkedStack<T> implements SStack<T> {
private Node <T> top;
public LinkedStack(){this.top=null;}
public boolean isEmpty(){ return this.top == null;}
public void push(T x){
if (x!=null)
this.top = new Node(x,this.top);
}
public T pop(){
if(this.top==null)
return null;
T temp = this.top.data;
this.top = this.top.next;
return temp;
}
public T get(){
return this.top==null?null:this.top.data;
}
private class Node<T> {
private T data;
private Node<T> next;
private Node(T dataPortion){
data = dataPortion;
next = null;
}
private Node(T dataPortion,Node<T> nextNode){
data = dataPortion;
next = nextNode;
}
}
}队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两段进行。向队列中插入元素的过程称为入队（enqueue），删除元素的过程称为出队（dequeue）。允许入队的一端称为队尾（rear），允许出队的一端称为队头（front）。插入和删除操作分别在队尾和队头进行，最先入队的元素总是最先出队，因此队列也称为先进先出(first in first out)表。队列的基本操作有创建队列、判断队列是否为空、入队和出队。
（一）顺序循环队列
循环队列遵循以下约定：
1.队头、队尾元素下标按照循环规律变化（使之达到最大值后再变回0），length表示数组长度：
front =(front+1)%length
rear=(rear+1)%length
2.约定rear含义及队列空条件
约定rear是下一个入队元素位子，队列空条件是front ==rear 设置初始空队列为front==0
3.约定队列满条件
约定队列满条件是队列中仍有一个空位置，front==(rear+1)%length
顺序循环队列类SeqQueue声明如下，实现队列借口QQueue。
public class SeqQueue<T> implements QQueue<T> {
private Object element[];//存储队列数据元素的数组
private int front ,rear;//front、rear分别为队列头尾下标
public SeqQueue(int length){
if(length<64)
length= 64;
this.element = new Object[Math.abs(length)];
front = rear = 0;//设置空队列
}
public SeqQueue(){this(64);}
public boolean isEmpty(){return this.front==this.rear;}//判断是否为空，若空返回ture
public void enqueue(T x){
if(x==null)
return;
if(this.front==(this.rear+1)%this.element.length){//队列满时，扩充容量
Object[] temp = this.element;
this.element = new Object[temp.length*2];
int i= this.front,j=0;
while(i!=this.rear){
this.element[j] = temp[i];
i = (i+1)%temp.length;
j++;
}
this.front=0;
this.rear=j;
}
this.element[this.rear] = x;
this.rear = (this.rear+1)%this.element.length;
}
public T dequeue(){
if(isEmpty())
return null;
T temp = (T)this.element[this.front];
this.front = (this.front+1)%this.element.length;
return temp;
}
}（二）链式队列
以不带头结点的单链表实现链式队列。设指针front和rear分别指向队头和队尾结点，入队操作将结点链在队尾结点之后，并使rear指向新的队尾结点；出队操作，当队列不为空时，取得队头结点值，删除该结点，并使front指向后继结点。
约定的情况：初始空队列的状态设置为front=rear=null，队列空条件是front=null&&rear==null。当第一个元素入队或最后一个元素出队时，均需要同时改变front和rear。入队和出队操作的时间复杂度都是O（1）。
public class LinkedQueue<T> implements QQueue<T> {
private Node<T> front,rear;
public LinkedQueue(){this.front=this.rear=null;}
public boolean isEmpty(){return this.front==null&&this.rear==null;}
public void enqueue(T x){
if(x==null)
return;
Node<T> q = new Node<T>(x,null);
if(this.front==null)
this.front =q;
else this.rear.next=q;
this.rear = q;
}
public T dequeue(){
if(isEmpty())
return null;
T temp = this.front.data;
this.front=this.front.next;
if(this.front==null)
this.rear=null;
return temp;
}
private class Node<T>{
private T data;
private Node<T> next;
private Node(T dataPortion){
data = dataPortion;
next = null;
}
private Node(T dataPortion,Node<T> nextNode){
data = dataPortion;
next = nextNode;
}
}
}