学步园

用链表表示的队列在插入和删除方面效率更高。

/** Node class used by linked structures.<br /> * This class and its data members are<br /> * visible only within the package dataStructures. */</p> <p>package dataStructures;</p> <p>class ChainNode<br /> {<br /> // package visible data members<br /> Object element;<br /> ChainNode next;</p> <p> // package visible constructors<br /> ChainNode() {}</p> <p> ChainNode(Object element)<br /> {this.element = element;}</p> <p> ChainNode(Object element, ChainNode next)<br /> {this.element = element;<br /> this.next = next;}<br /> }<br />

/** a linked queue class */</p> <p>package dataStructures;</p> <p>public class LinkedQueue implements Queue<br /> {<br /> // data members<br /> protected ChainNode front;<br /> protected ChainNode rear;</p> <p> // constructors<br /> /** create an empty queue */<br /> public LinkedQueue(int initialCapacity)<br /> {<br /> // the default initial value of front is null<br /> }</p> <p> public LinkedQueue()<br /> {this(0);}</p> <p> // methods<br /> /** @return true iff queue is empty */<br /> public boolean isEmpty()<br /> {return front == null;}</p> <p> /** @return the element at the front of the queue<br /> * @return null if the queue is empty */<br /> public Object getFrontElement()<br /> {<br /> if (isEmpty())<br /> return null;<br /> else<br /> return front.element;<br /> }</p> <p> /** @return the element at the rear of the queue<br /> * @return null if the queue is empty */<br /> public Object getRearElement()<br /> {<br /> if (isEmpty())<br /> return null;<br /> else<br /> return rear.element;<br /> }</p> <p> /** insert theElement at the rear of the queue */<br /> public void put(Object theElement)<br /> {<br /> // create a node for theElement<br /> ChainNode p = new ChainNode(theElement, null);</p> <p> // append p to the chain<br /> if (front == null)<br /> front = p; // empty queue<br /> else<br /> rear.next = p; // nonempty queue<br /> rear = p;<br /> }</p> <p> /** remove an element from the front of the queue<br /> * @return removed element<br /> * @return null if the queue is empty */<br /> public Object remove()<br /> {<br /> if (isEmpty())<br /> return null;<br /> Object frontElement = front.element;<br /> front = front.next;<br /> if (isEmpty())<br /> rear = null; // enable garbage collection<br /> return frontElement;<br /> }</p> <p> /** test program */<br /> public static void main(String [] args)<br /> {<br /> int x;<br /> LinkedQueue q = new LinkedQueue(3);<br /> // add a few elements<br /> q.put(new Integer(1));<br /> q.put(new Integer(2));<br /> q.put(new Integer(3));<br /> q.put(new Integer(4));</p> <p> // delete all elements<br /> while (!q.isEmpty())<br /> {<br /> System.out.println("Rear element is " + q.getRearElement());<br /> System.out.println("Front element is " + q.getFrontElement());<br /> System.out.println("Removed the element " + q.remove());<br /> }<br /> }<br /> }<br />