JAVA实现数组队列,循环数组队列,链式队列
/** * 文件名:QueueText.java * 时间:2014年10月22日下午9:05:13 * 作者:修维康 */ package chapter3; /** * 类名:ArrayQueue * 说明:队列的数组实现 */ class ArrayQueue<AnyType>{ private static final int DEFAULT_CAPACITY = 10; private int front;//队头 private int rear;//队尾 private int theSize; private AnyType[] theItems; public ArrayQueue(){ clear(); } public void clear(){ front = 0; rear = 0; theSize = 0; ensureCapacity(DEFAULT_CAPACITY); } public boolean isEmpty(){ return theSize == 0;//or front == rear; } public void enqueue(AnyType x){ theItems[rear++] = x; theSize++; } public AnyType dequeue(){ if(theSize == 0) return null; theSize--; return theItems[front++]; } //返回队列前面的元素 public AnyType element(){ if(isEmpty()) return null; return theItems[front]; } /** * 方法名:ensureCapacity * 说明:确保容量 */ public void ensureCapacity(int newCapacity){ if(newCapacity < theSize) return; AnyType[] old = theItems; theItems = (AnyType[]) new Object[newCapacity]; for(int i = 0;i < theSize;i++) theItems[i] = old[i]; } } /** * 类名:CirArrQueue * 说明:循环队列 (因为用数组实现的队列在删除的时候指针会后移 这样导致了前面的浪费, * 循环数组可以解决这个问题,但是循环队列可能使得运行时间加倍) */ class CirArrQueue<AnyType>{ private static final int DEFAULT_CAPACITY = 3; private int front;//队头 private int rear;//队尾 private int theSize; private AnyType[] theItems; public CirArrQueue(){ clear(); } public void clear(){ theItems = (AnyType[]) new Object[DEFAULT_CAPACITY]; front = 0; rear = 0; theSize = 0; } public boolean isEmpty(){ return theSize == 0;//or front == rear; } public boolean enqueue(AnyType x){ if(theSize == DEFAULT_CAPACITY) return false; theItems[rear++] = x; theSize++; if(rear == DEFAULT_CAPACITY)//如果到了尾部则回到0 rear = 0; return true; } public AnyType dequeue(){ if(theSize == 0) return null; theSize--; AnyType temp = theItems[front]; if(++front == DEFAULT_CAPACITY)//如果加1超过了数组 则返回到0; front = 0; return temp; } //返回队列前面的元素 public AnyType element(){ if(isEmpty()) return null; return theItems[front]; } } /** * 类名:LinkedQueue * 说明:链表实现队列 */ class LinkedQueue<AnyType>{ private static class Node<AnyType> { Node(AnyType data, Node<AnyType> next) { this.data = data; this.next = next; } private AnyType data; private Node<AnyType> next; } private Node<AnyType> front; private Node<AnyType> rear; public LinkedQueue(){ clear(); } public void clear(){ front = null; rear = null; } public boolean isEmpty(){ return front == null; } public void enqueue(AnyType x){ if(front == null&&rear == null){//最开始的时候 rear = new Node<AnyType>(x,null); front = rear; }else{ Node<AnyType> p = new Node<AnyType>(x,null); rear.next = p; rear = p;; } } public AnyType dequeue(){ if(!isEmpty()){ AnyType x = front.data; front = front.next; return x; } return null; } public AnyType element(){ if(!isEmpty()) return front.data; return null; } } /** * 类名:QueueText * 说明:队列的数组和链表实现及循环队列的数组实现 */ public class QueueText { /** * 方法名:main * 说明:测试 */ public static void main(String[] args) { // TODO Auto-generated method stub /****数组队列测试*****/ /*ArrayQueue<Integer> q = new ArrayQueue<Integer>(); q.enqueue(1); q.enqueue(2); q.enqueue(3); q.enqueue(4); System.out.println(q.element()); while(!q.isEmpty()) System.out.println(q.dequeue()); /*********链表队列测试**********/ /*LinkedQueue<Integer> q2 = new LinkedQueue<Integer>(); q2.enqueue(1); q2.enqueue(2); q2.enqueue(3); q2.enqueue(4); System.out.println(q2.element()); while(!q2.isEmpty()) System.out.println(q2.dequeue()); /***********循环队列测试************/ CirArrQueue<Integer> q3 = new CirArrQueue<Integer>(); q3.enqueue(1); q3.enqueue(2); q3.enqueue(3); q3.dequeue(); q3.enqueue(4);//设置默认容量为3,开始时3个,队列满了,后来删除第一个,队列数组里第一个空出来了,4进入了,但是还是满足先进先出的原则,加上 //size的控制,使其不会覆盖后面的 q3.enqueue(5);//没有进去 System.out.println(q3.element()); while(!q3.isEmpty()) System.out.println(q3.dequeue()); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。