棧和隊列
所謂的棧，是一個含有至少兩個基本操作的抽象數據類型：插入新的元素；刪除最近時間插入的元素。?遵循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;
}
}