Java實現隊列 - 隊列內部使用鏈式存儲結構

Java實現隊列——隊列內部使用鏈式存儲結構

鏈隊列

代碼：

package hash;

/**
 * Created with IntelliJ IDEA.
 * User: ASUS
 * Date: 14-9-17
 * Time: 上午11:58
 * To change this template use File | Settings | File Templates.
 */
public class CustomLinkQueue<E> {
    //定義一個內部類Node，Node實例代表鏈棧的節點。
    private class Node {
        //保存節點的數據
        private E data;
        //指向下個節點的引用
        private Node next;

        //無參數的構造器
        public Node() {
        }

        //初始化節點的數據域
        private Node(E data) {
            this.data = data;
        }

        //初始化全部屬性的構造器
        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node front;  //頭指針指向頭結點
    private Node rear;   //尾節點
    private int count; //該隊列元素的數量


    /**
     * 初始化隊列
     * 此時隊列為空
     */
    public CustomLinkQueue() {
        Node p = new Node();
        p.data = null;
        p.next = null;
        front = rear = p;
    }

    /**
     * 在隊列的后端插入節點
     *
     * @param item
     */
    public void enqueue(E item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = null; //入隊的節點沒有后繼節點
        this.rear.next = newNode; //讓原來的尾節點的后繼節點指向新節點
        this.rear = newNode;     //rear指向最后一個節點
        count++;
    }


    /**
     * 出隊
     * 在隊列的前端刪除節點
     *
     * @return
     */
    public E dequeue() throws Exception {
        if (isEmpty()) {
            throw new Exception("隊列為空");
        } else {
            E obj;
            Node p = this.front.next;  //指向隊頭的第一個節點
            obj = p.data;
            this.front.next = p.next;

            if (rear == p) {
                rear = front;
            }
            count--;
            return obj;
        }
    }


    /**
     * @return
     */
    public int size() {
        return count;
    }

    /**
     * 遍歷算法
     * 移動front指針，直到front指針追上rear指針
     */
    public void traverse() {
        for (Node current = front.next; current != null; current = current.next) {
            System.out.println(current.data);
        }
    }

    /**
     * 判斷隊列為空的條件是front == rear
     *
     * @return
     */
    public boolean isEmpty() {
        return front == rear;
    }


    public static void main(String args[]) throws Exception {
        CustomLinkQueue linkQueue = new CustomLinkQueue();

        for (int i = 0; i < 5; i++) {  //添加5個元素
            linkQueue.enqueue("lyx" + i);
        }

        System.out.println(linkQueue.size());
        System.out.println("===========traverse===========");
        linkQueue.traverse();
        System.out.println("==============================");
        linkQueue.dequeue();
        linkQueue.dequeue();
        System.out.println("===========traverse===========");
        linkQueue.traverse();
        System.out.println("==============================");
        System.out.println(linkQueue.size());
    }
}