Java实现队列 && 链式存储结构

原创
2014/09/17 13:51
阅读数 2K

队列的链式存储结构

示例代码如下,

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());
    }
}

====EN====

展开阅读全文
打赏
0
8 收藏
分享
加载中
更多评论
打赏
0 评论
8 收藏
0
分享
返回顶部
顶部