队列的顺序表方式实现：
实现之前的问题？
/* * 沿用顺序表的实现方法的问题： * 1、rear=0时，因为队头元素就在数组高端，deQueue()的时间代价O(1)，而enQueue()的代价O(n) * 2、rear=n-1时，因为队头元素又在数组低端，需要移动其余n-1个元素，deQueue()的时间代价O(n)，而enQueue()的代价O(1) * 如何保证队列的连续性同时允许队列的首尾在数组中自由移动，并且可以防止”假溢出“ ->逻辑上形成循环队列 * 判断队列满和空的两种办法： * 1、用变量记录队列的元素个数，deQueue()和enQueue()时设置这些变量 * 2、牺牲一个元素空间来简化操作提高运行效率，把存储n个元素的数组length设置为n+1 * front = rear ->队列为空 * (rear+1)%size == front ->队列已满 * */
/** * @author Administrator * * @param <T> 队列存储类型 */ public class MyArrQueue<T> { private int size; //存放队列的数组大小 private int front; //队列头 private int rear; //队列尾 private T[] items; //存放T类型的数组 /** 初始化队列 * @param size */ @SuppressWarnings("unchecked") public MyArrQueue(int size){ this.size = size + 1; items = (T[])new Object[this.size]; front = rear = 0; } /** * 清空队列 */ public void clear(){ front = rear; items = null; } /** * 入队操作 * @param item * @return */ public boolean enQueue(final T item){ if((rear+1)%size == front){ System.out.println("队列已满！"); return false; } items[rear] = item; rear = (rear+1)%size; //循环后移 return true; } /** * 返回队头元素，并删除 * @return */ public T deOueue(){ if(front == rear){ throw new java.util.NoSuchElementException(); } T item = items[front]; front = (front+1)%size;//队头向后移 return item; } /** * 返回队头但不删除 * @return */ public T getFront(){ if(front == rear){ throw new java.util.NoSuchElementException(); } T item = items[front]; return item; } public static void main(String[] args) { MyArrQueue<Integer> queue = new MyArrQueue<Integer>(2); queue.enQueue(2); queue.enQueue(3); System.out.println(queue.getFront()); System.out.println(queue.deOueue()); System.out.println(queue.deOueue()); System.out.println(queue.deOueue()); } }队列的链式实现：
/** * 链式队列 * @author Administrator * * @param <T> */ public class MyLinkedQueue<T> { private int size; private Node<T> front; private Node<T> rear; private static class Node<T> { public Node(T item,Node<T> next) { data = item; this.next = next; } public T data; public Node<T> next; } public MyLinkedQueue() { size = 0; front = rear = null; } /** * 入队 * @param item * @return */ public boolean enQueue(final T item) { if (rear == null) { //队列为空 front = rear = new Node<T>(item, null); } else { //添加新元素 rear.next = new Node<T>(item, null); rear = rear.next; } size++; return true; } /** * 返回队头元素 * @return */ public T deQueue() { Node<T> tmp = front; final T val = front.data; if(size == 0) { System.out.println("队列为空"); return null; } front = front.next; tmp.data = null; tmp.next = null; if(front == null) { //只有一个元素且删除的情况 rear = null; } size--; return val; } /** * 返回队头元素，不删除 * @return */ public T getFront() { if(size == 0) { System.out.println("队列为空"); return null; } final T val =front.data; return val; } /** * 清空队列 */ public void clear(){ /* while(front!=null) { rear = front; front = front.next; rear.data = null; rear = null; }*/ for(Node<T> tmp = front; tmp != null;) { Node<T> next = tmp.next; tmp.data = null; //help GC tmp.next = null; tmp = next; } front = rear = null; size = 0; } public static void main(String[] args) { MyLinkedQueue<Integer> queue = new MyLinkedQueue<Integer>(); queue.enQueue(2); queue.enQueue(3); System.out.println(queue.getFront()); System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); } }
