现在的位置: 首页 > 综合 > 正文

Queue实现

2013年12月05日 ⁄ 综合 ⁄ 共 3459字 ⁄ 字号 小 中 大 ⁄ 评论关闭

链表实现，插入节点放最后就行了。

代码：

[java]
view plaincopy
  1. package nuaa.ds;  
  2.   
  3. import java.util.NoSuchElementException;  
  4.   
  5. public class LinkedQueue<T> {  
  6.     private Node<T> head;  
  7.     private Node<T> tail;  
  8.     private int size;  
  9.       
  10.     public void enqueue(T t){  
  11.         if(null==t){  
  12.             throw new IllegalArgumentException();  
  13.         }  
  14.         if(size==0){  
  15.             head = new Node<T>(t);  
  16.             tail = head;  
  17.             size++;  
  18.             return;  
  19.         }  
  20.         Node<T> p = new Node<T>(t);  
  21.           
  22.         tail.next = p;  
  23.         tail = p;  
  24.         size++;  
  25.     }  
  26.       
  27.     public T dequeue(){  
  28.         if(size==0){  
  29.             throw new NoSuchElementException();  
  30.         }  
  31.         Node<T> p = head;  
  32.         head = head.next;  
  33.         return p.u;  
  34.     }  
  35.     public LinkedQueue(){  
  36.         this.size = 0;  
  37.     }  
  38.       
  39.     public boolean isEmpty(){  
  40.         return size==0 ? true : false;  
  41.     }  
  42.       
  43.     public T element(){  
  44.         return head.u;  
  45.     }  
  46.     public int  size(){  
  47.         return size;  
  48.     }  
  49.     class Node<U>{  
  50.         U u;  
  51.         Node<U> next;  
  52.           
  53.         public Node(U u) {  
  54.             super();  
  55.             this.u = u;  
  56.         }  
  57.           
  58.     }  
  59. }  

数组实现循环队列：

分离出满和空单独讨论，满就doble size，空了就把索引head tail都置为-1

代码：

[java]
view plaincopy
  1. package nuaa.ds;  
  2.   
  3. import java.util.NoSuchElementException;  
  4.   
  5. public class Queue<E> {  
  6.     private Object[] arrays = new Object[this.capacity];    //holds the objects  
  7.     private int size=0; //current size  
  8.     private int capacity = 2;   //default capacity  
  9.     private int head = -1;  //location of the head of queue  
  10.     private int tail = -1;  //location of the tail of queue  
  11.       
  12.     public void enqueue(E e) {  
  13.           
  14.         if(null==e){  
  15.             throw new IllegalArgumentException("e is null");  
  16.         }  
  17.         if(this.size()>=this.capacity||arrays.length==0){// arrays is full  
  18.             Object[] old = this.arrays;  
  19.             this.capacity = 2*this.capacity;  
  20.             this.arrays = new Object[this.capacity];  
  21.             this.head = 0;  
  22.             this.tail = old.length-1;  
  23.             for(int i=0;i<old.length;i++){//copy the elements  
  24.                 arrays[i] = old[i];  
  25.             }  
  26.               
  27.             //add the element  
  28.             this.tail++;      
  29.         }else{// not full  
  30.             if(head==-1&&tail==-1){//empty  
  31.                 this.head = 0;  
  32.                 this.tail = 0;  
  33.                   
  34.             }else if(head<tail){   
  35.                 if(tail==capacity-1){//tail is at the end of the arrays  
  36.                     this.tail = 0;  
  37.                 }else{  
  38.                     tail++;  
  39.                 }  
  40.             }else{//head>tail  
  41.                 tail++;  
  42.             }  
  43.         }  
  44.         this.size++;  
  45.         arrays[tail] = e;  
  46.     }  
  47.   
  48.       
  49.     public E dequeue() {  
  50.         if(size==0){//empty  
  51.             throw new NoSuchElementException();  
  52.         }  
  53.         if(size==1){//only 1 element  
  54.             this.head = -1;  
  55.             this.tail = -1;  
  56.             this.size--;  
  57.             return (E)this.arrays[tail];  
  58.         }  
  59.         if(head==capacity-1){  
  60.             this.head = 0;   
  61.             this.size--;  
  62.             return (E)arrays[capacity-1];  
  63.         }  
  64.         this.size--;  
  65.         this.head++;  
  66.         return (E)arrays[head-1];  
  67.     }  
  68.     public boolean isEmpty(){  
  69.         return size==0 ? true : false;   
  70.     }  
  71.       
  72.     public int size() {  
  73.         return this.size;  
  74.     }  
  75. } 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞