婚礼策划婚礼定制,云南网站建设及优化,上海做网站的公司哪个好,企业网站备案号密码忘记队列 Queue
队列也是一种线性结构相比数组#xff0c;队列对应的操作是数组的子集只能从一端#xff08;队尾#xff09;添加元素#xff0c;只能从另一端#xff08;队首#xff09;取出元素队列是一种先进先出的数据结构
队列的实现及复杂度分析
QueueE
voi…队列 Queue
队列也是一种线性结构相比数组队列对应的操作是数组的子集只能从一端队尾添加元素只能从另一端队首取出元素队列是一种先进先出的数据结构
队列的实现及复杂度分析
QueueE
void enqueu(E)E dequeue()E getFront()int getSize()boolean isEmpty()
数组队列的复杂度分析
ArrayQueueE
void enqueue(E) O(1) 均摊E dequeue() O(n) E getFront() O(1)int getSize() O(1)boolean isEmpty() O(1)
代码实现
public class ArrayQueueE implements QueueE {private ArrayE data;public ArrayQueue(int Capacity){data new Array(Capacity);}public ArrayQueue(){this(10);}Overridepublic int getSize(){return data.getSize();}public int getCapacity(){return data.getCapacity();}Overridepublic boolean isEmpty(){return data.isEmpty();}Overridepublic void enqueue(E e){data.addLast(e);}Overridepublic E dequeue(){return data.removeFirst();}Overridepublic E getFront(){return data.getFirst();}Overridepublic String toString(){StringBuilder res new StringBuilder();res.append(Queue : front [);for (int i 0; i data.getSize(); i) {res.append(data.get(i));if (i ! data.getSize() - 1)res.append(, );}res.append(] tail);return res.toString();}public static void main(String[] args){ArrayQueueInteger queue new ArrayQueue();for(int i 0 ; i 10 ; i ){queue.enqueue(i);System.out.println(queue);if(i % 3 2){queue.dequeue();System.out.println(queue);}}}
}
循环队列的复杂度分析
LoopQueueE
void enqueue(E) O(1) 均摊E dequeue() O(1) 均摊 E getFront() O(1)int getSize() O(1)boolean isEmpty() O(1)front tail 队列为空 (tail 1) % c front 队列已满 tail不用于存储元素capacity中浪费一个空间 代码实现 public class LoopQueueE implements QueueE {private E[] data;private int front, tail;private int size;public LoopQueue(int capacity){data (E[])new Object[capacity 1];front 0;tail 0;size 0;}public LoopQueue(){this(10);}Overridepublic boolean isEmpty(){return size 0;}public boolean isFull(){return front (tail 1) % data.length;}public int getCapacity(){return data.length - 1;}Overridepublic int getSize(){return size;}Overridepublic void enqueue(E e){if (isFull())resize(getCapacity() * 2 1);data[tail] e;tail (tail 1) % data.length;size;}Overridepublic E dequeue(){if (isEmpty())throw new IllegalArgumentException(Dequeue Failed.Queue is empty.);E ret data[front];data[front] null;front (front 1) % data.length;size--;if (size getCapacity() / 4 getCapacity() / 2 ! 0)resize(getCapacity() / 2 1);return ret;}Overridepublic E getFront(){if (isEmpty())throw new IllegalArgumentException(Queue is empty.);return data[front];}public void resize(int newCapacity){if (newCapacity 0)throw new IllegalArgumentException(newCapacity is Illegal.);E[] newData (E[])new Object[newCapacity];for (int i 0; i size; i)newData[i] data[(i front) % data.length];data newData;front 0;tail size;}Overridepublic String toString(){StringBuilder res new StringBuilder();res.append(String.format(LoopQueue Capacity %d, Size %d\n, getCapacity(), getSize()));res.append(front [);for (int i front; i ! tail; i (i 1) % data.length){res.append(data[i]);if ((i 1) % data.length ! tail)res.append(, );}res.append(] tail);return res.toString();}public static void main(String[] args) {LoopQueueInteger queue new LoopQueue();for (int i 0; i 10; i) {queue.enqueue(i);System.out.println(queue);if (i % 3 2) {queue.dequeue();System.out.println(queue);}}}
}
性能比较
测试函数
// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间单位秒private static double testQueue(QueueInteger q, int opCount){long startTime System.nanoTime();for (int i 0; i opCount; i)q.enqueue(i);for (int i 0; i opCount; i)q.dequeue();long endTime System.nanoTime();return (endTime - startTime) / 1000000000.0;}
测试 public static void main(String[] args){int opCount 100000;ArrayQueueInteger arrayQueue new ArrayQueue();double timeArray testQueue(arrayQueue, opCount);System.out.println(ArrayQueue time : timeArray s);LoopQueueInteger loopQueue new LoopQueue();double timeQueue testQueue(loopQueue, opCount);System.out.println(LoopQueue time : timeQueue s);}
运行结果 在10^5数量级上我的这台电脑上所展现性能差异还是很明显的由于数组队列的出队操作是 O(n) 级别消耗了大量的时间。
