Java Queue-数组队列和循环队列-学习记录
package queue; import array.Array; /** * @Title: ArrayQueue * @ProjectName Demo03 * @date 2018/9/1214:09 */ public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue() { array = new Array<>(); } public ArrayQueue(int capacity) { array = new Array<>(capacity); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public void enqueue(E e) { array.addLast(e); } @Override public E dequeue() { return array.removeFirst(); } @Override public E getFront() { return array.getFirst(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue:"); res.append("Front ["); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1) { res.append(","); } } res.append("] tail"); return res.toString(); } public static void main(String[] args) { ArrayQueue<String> arrayQueue = new ArrayQueue<>(); arrayQueue.enqueue("1"); arrayQueue.enqueue("2"); System.out.println(arrayQueue); System.out.println(arrayQueue.getFront()); arrayQueue.dequeue(); System.out.println(arrayQueue); } }
package queue; /** * @Title: LoopQueue * @ProjectName Demo03 * @date 2018/9/1214:17 */ public class LoopQueue<E> implements Queue<E> { 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); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return front == tail; } public int getCapacity() { return data.length - 1; } @Override public void enqueue(E e) { if ((tail + 1) % data.length == front) { // 队列已满 resize(getCapacity() * 2); } data[tail] = e; tail = (tail + 1) % data.length; size++; } @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("队列为空"); } E e = data[front]; front = (front + 1) % data.length; size--; if (size == getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / 2); } return e; } @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("队列为空"); } return data[front]; } private void resize(int capacity) { E[] newData = (E[]) new Object[capacity + 1]; for (int i = 0; i < size; i++) { newData[i] = data[(i + front) % data.length]; } data = newData; front = 0; tail = size; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("LoopQueue: size=%d , capacity=%d\n", size, getCapacity())); 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){ LoopQueue<Integer> queue = new LoopQueue<>(5); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println(queue); if(i % 3 == 2){ queue.dequeue(); System.out.println(queue); } } } }
- 上一篇 »PHP 算法
- 下一篇 »学习笔记-mysql_日志