队列是一种重要的数据结构,在排队论和算法设计中有很重要的应用,其实队列也是一种链表,它只允许在表的始端出表(dequeue),在表的末端入表(enqueue),下边是队列的java实现。
//队列是一种重要的数据结构,主要应用是资源的排队(例如打印机),需要注意的是要利用循环数据来存储数据 class Queue { private int front; private int back; private int size; private Object[] data; public Queue(){ data=new Object[10]; } public int getSize(){ return size; } public Object dequeue(){ Object o=null; if(size>0){ size--; o=data[front]; data[front]=null; front=(front>data.length-1)?0:front+1; } return o; } public void enqueue(Object o){ if(size>=data.length){ Object[] newData=new Object[data.length*2]; for(int i=0;i<data.length;++i){ newData[i]=data[i]; } data=newData; } data[back]=o; back++; size++; } public String toString(){ StringBuffer str=new StringBuffer(); for(int i=0;i<data.length;i++){ Object o=data[i]; if(o!=null){ str.append(o+" "); } } return str.toString(); } }
测试方法如下:
public static void main(String[] args){ Queue queue=new Queue(); for(int i=0;i<15;i++){ queue.enqueue("sunzhenxing"+i); } System.out.println(queue); System.out.println(queue.getSize()); System.out.println("----------------------"); for(int i=0;i<10;i++){ queue.dequeue(); } System.out.println(queue); System.out.println(queue.getSize()); System.out.println("----------------------"); for(int i=0;i<5;i++){ queue.enqueue("sunhailong"+i); } System.out.println(queue); System.out.println(queue.getSize()); }
输出是:
sunzhenxing0 sunzhenxing1 sunzhenxing2 sunzhenxing3 sunzhenxing4 sunzhenxing5 sunzhenxing6 sunzhenxing7 sunzhenxing8 sunzhenxing9 sunzhenxing10 sunzhenxing11 sunzhenxing12 sunzhenxing13 sunzhenxing14
15
----------------------
sunzhenxing10 sunzhenxing11 sunzhenxing12 sunzhenxing13 sunzhenxing14
5
----------------------
sunzhenxing10 sunzhenxing11 sunzhenxing12 sunzhenxing13 sunzhenxing14 sunhailong0 sunhailong1 sunhailong2 sunhailong3 sunhailong4
10