数据结构与算法：栈和队列
一，栈
栈是限定仅在表尾进行插入和删除操作的线性表。允许插入，删除的一端称为栈顶(top),另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。
栈的基本操作
1.初始化：构造一个空的栈
2.销毁：销毁一个已存在的栈
3.插入：在栈顶位置插入一个新元素
4.删除：删除栈顶元素
5.获取：取栈顶数据元素
6.判空：判断当前栈是否为空
7.求长度：求出栈中数据元素的个数
8.正序遍历：依次访问栈中每个元素并输出
1.顺序栈；
1.栈的初始化；
//无参构造方法
public sequenceStack( )
{
top=-1;
stackArray=(T[])new Object[MaxSize];
}
//有参构造方法
public sequenceStack(int n)
{
if (n<=0) {
System .out.println(“数组...程序运行！");
System.exit(1);
}
top=-1;
stackArray=(T[])new Object[n];
}
2.入栈；
public void push(T obj)
{
if(top==stackArray.length-1){
T []p=(T[])new Object [top*2];
for(int i=0;i<=top;i++)
p[i]=stackArray[i];
stackArray=p;
}
top++;
stackArray[top]=obj;
}
3.出栈；
public T pop()
{
if(top==-1){
System.out.println(“空栈，无法删除元素");
return null;
}
top--;
return stackArray[top+1];
}
4.取栈顶元素；
public T getHead()
{
if(top==-1){
System.out.println("空栈，无法删除元素");
return null;
}
return stackArray[top];
}
5.判断栈空操作；
public boolean isEmpty()
{
return top==-1;
}
6.求栈的长度；
public int size()
{
return top+1;
}
7.遍历栈；
public void nextOrder()
{
for(int i=top;i>=0;i--)
System.out.println(stackArray[i]);
}
8.清空栈操作；
public void clear()
{
top=-1;
}
2.链栈
栈的链接存储结构称为链栈。
插入与删除仅在栈顶处执行；链式栈的栈顶在链头。链栈的基本操作如下所示：
1.入栈；
public void push(T obj) //入栈
{
top=new Node<T>(obj,top);
length++;
}
2.出栈；
public T pop() //出栈
{
if(top==null){
System.out.println(“空栈，无法删");
return null;
}
T x=top.data;
top=top.next;
length--;
return x;
}
3.取栈顶元素；
public T getHead() //取栈顶数据元素
{
if(top==null){
System.out.println(“栈空...！");
return null;
}
return top.data;
}
4.求元素个数，判空，销毁；
public int size() //求出栈中数据元素的个数
{
return length;
}
public boolean isEmpty( ) //判断当前栈是否为空
{
return top==null;
}
public void clear() //销毁一个已存在的栈
{
top=null;
}
二.队列
队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
（先进先出原则）
队列的基本操作
1.初始化：构造一个空的队列
2.销毁：销毁一个已存在的队列
3.插入：在队列尾位置插入一个新元素
4.删除：删除队列头元素
5.获取：取队列头元素
6.判空：判断当前队列是否为空
7.求长度：求出队列中数据元素的个数
8.正序遍历：依次访问队列中每个元素并输出
1.顺序队列+循环队列
将顺序队列的存储区假想为是一个头尾相连的圆环，通常把这种特殊结构的队列称为循环队列。
基本操作：
1.队列初始化；
public sequenceQueue()
{
front=rear=0;
queueArray=(T[])new Object[MaxSize];
}
2.入队；
public void EnQueue(T obj)
{
if((rear+1)%queueArray.length==front){
T[] p=(T[])new Object[queueArray.length*2];
if(rear==((T[])queueArray).length-1)
{
for(int i=1;i<=rear;i++)
p[i]=queueArray[i];
}
else{
int i,j=1; for(i=front+1;i<queueArray.length;i++,j++)
p[j]=queueArray[i];
for(i=0;i<=rear;i++,j++)
p[j]=queueArray[i];
front=0;
rear=queueArray.length-1;
}
queueArray=p;
}
rear=(rear+1)%queueArray.length;
queueArray[rear]=obj;
}
3.出队；
public T DeQueue()
{
if(isEmpty()){
System.out.println(“空队");
return null;
}
front=(front+1)%queueArray.length;
return queueArray[front];
}
4.取头元素操作；
public T getHead( )
{
if(isEmpty()){
System.out.println(“空队");
return null;
}
return queueArray[(front+1)%queueArray.length];
}
5.非空判断；
public boolean isEmpty( )
{
return front==rear;
}
6.求长度；
public int size()
{
return (rear-front+queueArray.length)%queueArray.length;
}
7.遍历队列；
public void nextOrder()
{
int i,j=front;
for(i=1;i<=size();i++)
{
j=(j+1)%queueArray.length;
System.out.println(queueArray[j]);
}
}
8.清空队列；
public void clear()
{ front=rear=0; }
2.链队列；
用链表表示的队列称为链队列。
1.初始化链队列；
public linkQueue()
{
length=0;
front=rear=new Node<T>(null);
}
2.入队；
public void EnQueue(T obj)
{
rear=rear.next=new Node<T>(obj,null);
length++;
}
3.出队；
public T DeQueue()
{
if(isEmpty( )){
System.out.println(“空队");
return null;
}
Node<T> p=front.next;
T x=p.data;
front.next=p.next;
length--;
if(front.next==null)
rear=front;
return x;
}
4.取队头元素；
public T getHead()
{
if(isEmpty( )){
System.out.println(“空队");
return null;
}
return front.next.data;
}
5.求队列的长度；
public int size()
{
return length;
}
6.判断队列是否为空；
public boolean isEmpty( )
{
return front.next==null;
}
7.输出元素；
public void nextOrder()
{
Node<T> p=front.next;
while(p!=null){
System.out.println(p.data);
p=p.next;
}
}
8.清空队列；
public void clear()
{
front.next=rear.next=null;
}
三.小结
1、栈是限定仅在表尾进行插入和删除操作的线性表。允许插入，删除的一端称为栈顶(top),另一端称为栈底(bottom)。
2、栈的特征是后进先出。
3、队列是一种运算受限制的线性表，允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
4、队列的特征是先进先出。
5、顺序存储结构的队列存在假溢出现象，故引入了循环队列。
6、循环队列的判空条件为front==，判满条件为：（rear+1）% queueArray.length == front 。