java使用數(shù)組和鏈表實(shí)現(xiàn)隊(duì)列示例

更新時(shí)間：2014年01月29日 11:13:08 作者：

隊(duì)列是一種特殊的線性表，它只允許在表的前端(front)進(jìn)行刪除操作，只允許在表的后端（rear）進(jìn)行插入操作,下面介紹一下java使用數(shù)組和鏈表實(shí)現(xiàn)隊(duì)列的示例

（1)用數(shù)組實(shí)現(xiàn)的隊(duì)列：

  
//先自己定義一個(gè)接口  
public interface NetJavaList {  
  public void add(Student t);    //繼承該接口的類必須實(shí)現(xiàn)的方法  
  public Student get(int index);//隊(duì)列的加入，取出，隊(duì)列的大小  
  public int size();  

}  

定義一個(gè)學(xué)生類

復(fù)制代碼代碼如下:

class Student {  
    private String name ;   //私有屬性 名字，學(xué)分  
    private int score ;  
    public Student(String name , int score){  
        this.name = name ;  
        this.score = score ;  
    }  
    public void printInfo(){  
        System.out.println("姓名"+name + "學(xué)分"+score ) ;  
    }  
}  

實(shí)現(xiàn)自定義接口

復(fù)制代碼代碼如下:

public class STList implements NetJavaList{  
private Student[] str = new Student[0] ;  
    //增加隊(duì)列的元素  
    public void add(Student t) {  
        Student[] src = new Student[str.length+1];  
        for(int i=0;i<str.length;i++){  
            src[i]=str[i] ;  
        }  
        src[str.length]=t ;  
        str = src ;  
    }  

    //得到隊(duì)列中的某個(gè)元素  
    public Student get(int index) {  
        Student t = str[index];  
        return t;  
    }  

    //返回隊(duì)列的長(zhǎng)度  
    public int size() {  

        return str.length;  
    }  

}  

寫個(gè)主函數(shù)類實(shí)現(xiàn)下隊(duì)列

復(fù)制代碼代碼如下:

public class Manager {  
    public static void main(String[] args) {  
        STList sil = new STList() ;  
        for(int i=0;i<5;i++){  
        Student st = new Student("name"+i,i*10);      
        sil.add(st);  
        }  
       printList(sil) ;  

    }  
//輸出隊(duì)列中的所有元素  
  public static void printList(STList t){  
      for(int i=0;i<t.size();i++){  
          Student f =t.get(i);  
          f.printInfo();  
      }  

  }  
}  

（2）鏈表實(shí)現(xiàn)的隊(duì)列
先定義一個(gè)節(jié)點(diǎn)類；

復(fù)制代碼代碼如下:

public class LinkNode {  
private Object obj ; //節(jié)點(diǎn)內(nèi)的數(shù)據(jù)對(duì)象  
private LinkNode next ; //對(duì)下一個(gè)節(jié)點(diǎn)的引用  
//在創(chuàng)建節(jié)點(diǎn)對(duì)象的時(shí)候就傳入節(jié)點(diǎn)的數(shù)據(jù)對(duì)象  
public LinkNode(Object obj){  
    this.obj = obj ;  
}  
public Object getObj(){  
    return obj ;  
}  
public void setObj(Object obj){  
    this.obj = obj ;  

}  
public LinkNode getNext(){  
    return next ;  
}  
public void setNext(LinkNode next){  
    this.next =next ;  
}  
}  

然后寫個(gè)隊(duì)列的實(shí)現(xiàn)方法類

復(fù)制代碼代碼如下:

 
public class LinkList {  

    public static LinkNode root ;//第一個(gè)節(jié)點(diǎn)  
    public LinkNode last = null ;//最后的一個(gè)節(jié)點(diǎn)  
    public static void main(String ara[]){  
        LinkList df = new LinkList() ;  
        df.add(1);  
        df.add(2);  
        df.add(3);  
        df.printLinkList(root);  
        df.move(root,2) ;  
        df.move(root,2) ;  
        df.printLinkList(root);  

    }  
    /* 
     * 插入節(jié)點(diǎn) 
     */  
    public void add(Object obj){  
        //創(chuàng)建一個(gè)新的節(jié)點(diǎn)  
        LinkNode t = new LinkNode(obj);  
        if(root ==null){  
            root = t ;  
            last = root ;  
        }else{  
            last.setNext(t);  
            last = t ;  
        }  

    }  
    /* 
     * 輸出操作 
     */  
    public void printLinkList(LinkNode root){  
        if(null != root){  
            Object data = root.getObj();  
            System.out.println(data);  
            LinkNode temp = root.getNext();  
            printLinkList(temp) ;  
        }  
    }  
    /* 
     * 刪除操作 
     */  
    public LinkNode move(LinkNode root,int index){  
        if(this.getLength()<index || index <0){  
            throw new RuntimeException("下標(biāo)越界："+index +  
                ",size:" +this.getLength()) ;  
        }else{  
        int count = 1 ;LinkNode sd = root ;  
         while(count!=index-1){  
             sd = sd.getNext();  

         }  

          
         sd.setNext(sd.getNext().getNext());  
        return root ;  
    }}  

   /* 
    * 得到鏈表的長(zhǎng)度 
    */  
      public int  getLength(){  
        int count = 0 ;  
        if(root==null){  
            return count ;  
        }  
        LinkNode node =root.getNext();  
        while(null != node){  
            count ++ ;  
            node=node.getNext();  

        }  
        //System.out.println((count+1));  
        return count+1 ;  
      }  
}  