`
mywebcode
  • 浏览: 988121 次
文章分类
社区版块
存档分类
最新评论

队列的顺序实现(循环数组)与链式实现

 
阅读更多

队列(queue)同栈一样,也是表。是插入在一端(队尾)进行而删除在另一端(队头)进行的表。通过enqueue向队列中输入,通过dequeue从队列中输出。

顺序实现如下:

public class ArrayQueue<AnyType> {

	private AnyType theArray[];
	private int front,back;      //定义队头队尾
	private int currentSize;     //队列中存放元素个数
	private int maxSize=5;       //队列中能存放元素的个数
   
	public int size(){
		return currentSize;
	}
	public ArrayQueue(){
		theArray=(AnyType []) new Object[maxSize];
		front=back=0;
		currentSize=0;
	}
	
	public boolean isEmpty(){
		return front==back&¤tSize==0;
	}
	
	public void enQueue(AnyType x){           //入队
		if(currentSize==maxSize){             //溢出
			System.out.println("队列已满");
		}
		theArray[back]=x;
		back++;
		if(back==maxSize)                      //构成循环队列
			back=0;
		 currentSize++;
		
	}
	
	public AnyType deQueue(){         //出队
		if(isEmpty())
			return null;
		AnyType a=theArray[front];
		front++;
		if(front==maxSize)
			front=0;
		currentSize--;
		return a;	
	}
	
	public AnyType getFront(){
		if(isEmpty())
			return null;
		return theArray[front];
	}
	public static void main(String[] args) {
		//验证部分
		ArrayQueue<Integer> aq=new ArrayQueue<Integer>();
		aq.enQueue(0);aq.enQueue(1);aq.enQueue(2);aq.enQueue(3);aq.enQueue(4);
		aq.deQueue();aq.deQueue();	
		aq.enQueue(0);
        int m=aq.size();
		for(int i=0;i<m;i++){
			System.out.println(aq.deQueue());
		}
	}

}


链式实现如下:

public class SingleLinkedQueue<AnyType> {
      private Node<AnyType> front,back;           //定义front,back结点
      private int currenSize;                    //链表中数据个数
	
      private static class Node<AnyType>{                 //定义结点类
    		public AnyType data;
    		public Node<AnyType> next;
    		
    		public Node(AnyType data,Node<AnyType> next){
    			this.data=data;
    			this.next=next;
    		}
    		public Node(AnyType data){
    			this.data=data;
    			this.next=null;
    		}
    		public Node(){
    			this.data=null;
    			this.next=null;
    		}
    	}
      
      public SingleLinkedQueue(){
    	  front=back=null;
    	  currenSize=0;
      }
      
      public boolean isEmpty(){
    	  return currenSize==0;
      }
      
      public int size(){
    	  return currenSize;
      }
	 
      public void enQueue(AnyType x){                    //入队
    	  Node<AnyType> p=new Node<AnyType>(x); 
    	  if(front==null){                             //
    		  front=back=p;
    	  }
    	  back.next=p;
    	  back=p;
    	  currenSize++;
      }
      
     
      public AnyType deQueue(){                    //出队
    	  if(front==null){
    		  return null;
    		  //若为void方法,System.out.println("此队列已无数据");
    	  }
    	  AnyType old=front.data;                       
    	  front=front.next;                      //令front1后移
    	  currenSize--;
    	  return old;
      }
       
      
	public static void main(String[] args) {
		//验证部分
		SingleLinkedQueue<String> slq=new SingleLinkedQueue<String>();
		slq.enQueue("aaa");slq.enQueue("bbb");slq.enQueue("ccc");slq.enQueue("ddd");slq.enQueue("eee");
		int m=slq.size();
		for(int i=0;i<m;i++){
			System.out.println("第"+(i+1)+"次输出的数据"+slq.deQueue());
		}

	}

}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics