栈和队列
所谓的栈，是一个含有至少两个基本操作的抽象数据类型：插入新的元素；删除最近时间插入的元素。遵循FILO（First in，last out，先进后出）的原则。
所谓的队列，也是一个含有至少两个基本操作的抽象数据类型：插入新的元素；删除最久时间插入的元素。遵循FIFO（First in，first out，先进先出）的原则。
关于栈和队列的具体实现，我们即可以借助于数组，也可以采用链表来实现。
1） 栈的数组实现方式
public class MyStack<E> {
public int count;
public Object [] items;

public boolean isEmpty(){
return count==0;
}

public MyStack (){

items=new Object[20];
count=0;
}

public MyStack (int len){

items=new Object[len];
count=0;
}

/**
重新调整数组的大小
**/
private void resize(int size){
Object [] newItems=new Object[size];
for(int i=0;i<count;i++){
newItems[i]=items[i];
}
items=newItems;
}

public void push(E e){
if(count==items.length) resize(2*items.length);

items[count++]=e;
}

public E pop(){
if(count==0) return null;
E item=(E)items[count-1];
items[count-1]=null;
count--;
if(count>0&&count<=items.length/4) resize(items.length/2);
return item;
}

public E peek(){
if(count==0) return null;

E item=(E)items[count-1];

return item;
}
}
2） 栈的链式实现方式
public class MyStack<E> {
private class Node{
E item;
Node next;
}

Node head;

public boolean isEmpty(){
return head==null;
}

public void push(E t){
Node node=new Node();
node.item=t;
node.next=head;
head=node;
}

public E pop(){

if(head==null)
return null;
E t=head.item;
head=head.next;

return t;
}

public E peek(){
if(head==null)
return null;
else
return head.item;
}
}
3） 队列的数组实现
public class ArrayQueue<E> {
private int front;
private int rear;
private int count;
private int capacity;
private int capacityIncrement;


private Object[] itemArray;

public ArrayQueue(){
front=0;
rear=0;
count=0;
capacity=10;
capacityIncrement=5;
itemArray=new Object[capacity];
}

public boolean empty(){
return count==0;
}

public void insert(E e){
if(count==capacity){
capacity+=capacityIncrement;
Object [] newArray=new Object[capacity];
// for(int i=0;i<count;i++){
// newArray[i]=itemArray[i];
// }
if(front<rear){
//如果元素位于itemArray[front:rear-1]中
for(int i=front;i<rear;i++){
newArray[i]=itemArray[i];
}
}else{
//否则，将元素分成两个区间
//区间1：itemArray[0:rear-1]
for(int i=0;i<rear;i++){
newArray[i]=itemArray[i];
}
//区间2：itemArray[front:count-1]
for(int i=front;i<count;i++){
newArray[i]=itemArray[i];
}

front+=capacityIncrement;//然后，将front改为指向其新位置
}
itemArray=newArray;
}
itemArray[rear]=e;
rear=(rear+1)%capacity;
count++;
}

public E remove(){
if(count==0){
return null;
}
else{
E temp=(E) itemArray[front];
itemArray[front]=null;
front=(front+1)%capacity;
count--;

return temp;
}
}
}
4） 队列的链式实现方式
public class ListQueue<E> {
private class Node<E>{
E item;
Node<E> link;
}

private Node<E> front,rear;
private int count;

public boolean empty(){
return count==0;
}

public void insert(E e){
//如果队列为空
Node<E> newNode=new Node<E>();
newNode.item=e;

if(rear==null){
front=rear=newNode;
}else{
rear.link=newNode;
rear=newNode;
}
count++;
}

public E remove(){
if(count==0){
return null;
}else{
E e=front.item;
front=front.link;
if(front==null){
rear=null;
}

count--;

return e;
}
}

public ListQueue<E> clone(){
ListQueue<E> Q=new ListQueue<E>();

for(Node<E> t=front;t!=null;t=t.link)
Q.insert(t.item);
return Q;
}
}