`

数组和链表实现的队列

阅读更多

 队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作

 我管你什么队列,我就是要打破这规则,什么先进先出,都是浮云。

(1)用数组实现的队列:

 

//先自己定义一个接口
public interface NetJavaList {
  public void add(Student t);    //继承该接口的类必须实现的方法
  public Student get(int index);//队列的加入,取出,队列的大小
  public int size();
	
}

   //定义一个学生类

 

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

 // 实现自定义接口

 

public class STList implements NetJavaList{
private Student[] str = new Student[0] ;
	//增加队列的元素
	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 ;
	}

	//得到队列中的某个元素
	public Student get(int index) {
		Student t = str[index];
		return t;
	}

	//返回队列的长度
	public int size() {
		
		return str.length;
	}

}

 //写个主函数类实现下队列

    

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) ;

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

 (2)

 链表实现的队列

  先定义一个节点类;

 

public class LinkNode {
private Object obj ; //节点内的数据对象
private LinkNode next ; //对下一个节点的引用
//在创建节点对象的时候就传入节点的数据对象
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 ;
}


}

 然后写个队列的实现方法类

public class LinkList {

	public static LinkNode root ;//第一个节点
	public LinkNode last = null ;//最后的一个节点
	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);
		
	}
	/*
	 * 插入节点
	 */
	public void add(Object obj){
		//创建一个新的节点
		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("下标越界:"+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 ;
	}}
  
   /*
    * 得到链表的长度
    */
      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 ;
      }
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics