0001 /* 0002 * 借助定长循环数组实现Queue接口 0003 */ 0004 0005 package dsa; 0006 0007 public class Queue_Array implements Queue { 0008 public static final int CAPACITY = 1000;//数组的默认容量 0009 protected int capacity;//数组的实际容量 0010 protected Object[] Q;//对象数组 0011 protected int f = 0;//队首元素的位置 0012 protected int r = 0; //队尾元素的位置 0013 0014 //构造方法(空队列) 0015 public Queue_Array() 0016 { this(CAPACITY); } 0017 0018 //按指定容量创建对象 0019 public Queue_Array(int cap) 0020 { capacity = cap; Q = new Object[capacity]; } 0021 0022 //查询当前队列的规模 0023 public int getSize() 0024 { return (capacity - f + r) % capacity; } 0025 0026 //判断队列是否为空 0027 public boolean isEmpty() 0028 { return (f == r); } 0029 0030 //入队 0031 public void enqueue(Object obj) throws ExceptionQueueFull { 0032 if (getSize() == capacity - 1) 0033 throw new ExceptionQueueFull("Queue overflow."); 0034 Q[r] = obj; 0035 r = (r + 1) % capacity; 0036 } 0037 0038 //出队 0039 public Object dequeue() { 0040 Object elem; 0041 if (isEmpty()) 0042 throw new ExceptionQueueEmpty("意外:队列空"); 0043 elem = Q[f]; 0044 Q[f] = null; 0045 f = (f + 1) % capacity; 0046 return elem; 0047 } 0048 0049 //取(并不删除)队首元素 0050 public Object front() throws ExceptionQueueEmpty { 0051 if (isEmpty()) 0052 throw new ExceptionQueueEmpty("意外:队列空"); 0053 return Q[f]; 0054 } 0055 0056 //遍历(不属于ADT) 0057 public void Traversal() { 0058 for (int i = f; i < r; i++) 0059 System.out.print(Q[i] + " "); 0060 System.out.println(); 0061 } 0062 }