学步园

(1)栈 

package ChapterOne;  
  
public class Stack {  
    //栈数组  
    long stackArr[];  
    //栈的大小  
    int maxSize;  
    //栈的顶部  
    int top;  
    //初始化一个大小为size的栈  
    public Stack(int size){  
        maxSize = size;   
        stackArr = new long[size];  
        top = -1;  
    }  
    //出栈操作  
    public long pop(){  
        return stackArr[top--];  
    }  
    //进栈操作  
    public void push(long value){  
        stackArr[++top] = value;  
    }  
    //判断栈是否为空  
    public boolean isEmpty(){  
        return top == -1;  
    }  
    //判断栈是否已满  
    public boolean isFull(){  
        return top == maxSize-1;  
    }  
    //取栈顶元素  
    public long peek(){  
        return stackArr[top];  
    }  
    public static void main(String[] args) {  
        Stack stack = new Stack(10);  
        while(!stack.isFull()){  
            long v = (long) (Math.random()*100);  
            stack.push(v);  
            System.out.print(v+" ");  
        }  
        System.out.println();  
        while(!stack.isEmpty()){  
            long topValue = stack.pop();  
            System.out.print(topValue+" ");  
        }  
        System.out.println();  
    }  
} 
(2)队列 

package ChapterOne;  
  
public class Queue {  
    //队列数组  
    private long queueArr[];  
    //队列的前端下标  
    private int front;  
    //队列的尾端下标  
    private int rear;  
    //队列的大小  
    private int maxSize;  
    //队列中元素的个数  
    private int nItems;  
    //初始化一个大小为size的队列  
    public Queue(int size){  
        queueArr = new long[size];  
        maxSize = size;  
        front = 0;  
        rear = -1;  
        nItems = 0;  
    }  
    //插入操作  
    public void insert(long value){  
        //队列已满  
        if(rear == maxSize-1)  
            rear = -1;  
        queueArr[++rear] = value;  
        nItems++;  
    }  
    //删除操作  
    public long remove(){  
        long temp = queueArr[front++];  
        if(front == maxSize)  
            front = 0;  
        nItems--;  
        return temp;  
    }  
    //返回队列第一个元素  
    public long peakFront(){  
        return queueArr[front];  
    }  
    //判断是否为空  
    public boolean isEmpty(){  
        return nItems == 0;  
    }  
    //判断是否已满  
    public boolean isFull(){  
        return nItems == maxSize;  
    }  
    //返回队列中元素的个数  
    public int size(){  
        return nItems;  
    }  
      
    public void print(){  
        for(int i = front;i < front+nItems;i++){  
            System.out.print(queueArr[i]+" ");  
        }  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
        Queue q = new Queue(10);  
        while(!q.isFull()){  
            long value = (long)(Math.random()*100);  
            q.insert(value);  
        }  
        q.print();  
        while(!q.isEmpty()){  
            q.remove();  
            q.print();  
        }  
        q.print();  
        System.out.println(q.isEmpty());  
    }  
}  

(3)优先队列

package ChapterOne;  
  
public class PriorityQueue {  
  
    private int nItems;  
      
    private long pqArr[];  
      
    private int maxSize;  
      
    public PriorityQueue(int size){  
        maxSize = size;  
        pqArr = new long[size];  
        nItems = 0;  
    }  
      
    public void insert(long value){  
        int i;  
        if(nItems == 0)  
            pqArr[nItems++] = value;  
        else{  
            for(i = nItems-1;i >= 0;i--){  
                if(value < pqArr[i]){  
                    pqArr[i+1] = pqArr[i];  
                }  
                else  
                    break;  
            }  
            pqArr[i+1] = value;  
            nItems++;  
        }  
    }  
      
    public long remove(){  
        return pqArr[--nItems];  
    }  
      
    public boolean isEmpty(){  
        return nItems == 0;  
    }  
      
    public boolean isFull(){  
        return nItems == maxSize;  
    }  
      
    public void print(){  
        for(int i = 0;i < nItems;i++)  
            System.out.print(pqArr[i]+" ");  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
        PriorityQueue pq = new PriorityQueue(10);  
        while(!pq.isFull()){  
            long value = (long)(Math.random()*100);  
            pq.insert(value);  
        }  
        pq.print();  
    }  
}

(4)双链表
class Chain{
    Chain pre=null,next=null;
    int id;
    String name;
}

class List{
    private Chain header=new Chain();
    
    public Chain add(int id,String name){ //在链表尾添加节点
        Chain current=new Chain(); //创建链表头
        Chain temp=header;
    
        while(temp.next!=null) //循环至链表尾
            temp=temp.next;
        temp.next=current;
        current.pre=temp;    
        current.id=id;
        current.name=name;
        return current;
    }
    
    public Chain remove(int id){ //删除指定id的节点
        Chain temp=header;
        Chain current=null;
        while(temp.next!=null){
            temp=temp.next;
            if(temp.id==id){
                current=temp;
                break;
            }
        }
        if(current==null)
            return null;        
        
        current.pre.next=current.next;
        if(current.next!=null)
            current.next.pre=current.pre;
        return current;
    }
    
    public Chain remove(String name){ //删除指定name的节点
        Chain temp=header;
        Chain current=null;
        while(temp.next!=null){
            temp=temp.next;
            if(temp.name==name){
                current=temp;
                break;
            }
        }
        if(current==null)
            return null;
        
        current.pre.next=current.next;
        if(current.next!=null)
            current.next.pre=current.pre;
        return current;
    }    

    public Chain remove(){ //删除最后一个节点
        Chain temp=header;
        while(temp.next.next!=null){
            temp=temp.next;
        }
        temp.next=null;    
        return temp;
    }
    
    public void clear(){ //删除所有节点
        header.next=null;
    }
    
    public Chain insert(int id,String name,int pos){ //在指定位置插入节点
        Chain temp=header;
        Chain current=new Chain();
        int i=0;
        
        for(i=0;i<=pos;i++){
            if(temp.next!=null){
                temp=temp.next;
            }
            else{
                return null;
            }        
        }
        
        current.id=id;
        current.name=name;
        
        if(temp.next!=null){
            temp.next.pre=current;
            current.next=temp.next;
        }
        temp.next=current;
        current.pre=temp;
        return current;    
    }
    
    public void print_all(){
        Chain temp=header;
        
        System.out.println("--------------------------------------");
        while(temp.next!=null){
            temp=temp.next;
            System.out.println("ID: "+temp.id);
            System.out.println("Name: "+temp.name);
        }
        System.out.println("--------------------------------------");
    }
}

public class ChainList{
    public static void main(String[] args){
        List a=new List();
        
        a.add(1,"谭孟泷1") ;
        a.add(2,"谭孟泷2");
        a.add(3,"谭孟泷3");
        a.add(4,"谭孟泷4");
        a.insert(12,"大胖",2);
        

        a.print_all();
    }
}