但行好事  莫问前程

自己实现集合框架(十五):链式队列的实现

这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和java集合有个大概的了解。当然实现没有java集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。

一. 链式队列的描述

链式队列指采用链式存储结构的队列,比如采用链表来储存数据元素。对于队列的概念请参考文章自己实现集合框架(十二):队列接口。下面采用不带头结点的单链表来实现链式队列,设frontrear分别指向队列的队头结点和队尾结点,入队操作将新结点链在队尾结点之后,并使rear指向新的队尾结点;出队操作是在队列不为空的情况下,取得队头结点值,删除该结点,并使front指向其后继结点。整个操作过程如下图示所示:

二. 链式队列实现

1. 定义链式队列

顺序队列类LinkedQueue实现队列接口QQueue,并实现队列接口中定义的方法,队列接口的定义参考前面文章自己实现集合框架(十四):队列接口,代码如下所示:

package org.light4j.dataStructure.linearList.queue.link;

import org.light4j.dataStructure.linearList.Node;
import org.light4j.dataStructure.linearList.queue.QQueue;

/**
 * 链式队列
 * 
 * @author longjiazuo
 * @param <E>
 */
public class LinkedQueue<E> implements QQueue<E> {
    private Node<E> front;// 队列头结点
    private Node<E> rear;// 队列尾结点

    public LinkedQueue() {// 构造空队列
        this.front = null;
        this.rear = null;
    }
}

代码解释

初始空队列的状态设置为front=null,rear=null

数据类型是单链接结点类,成员变量frontrear分别指向队头和队尾结点。

2. 判断队列是否为空

/**
     * 判断队列是否为空,若为空返回true
     * 
     * @return
     */
    @Override
    public boolean isEmpty() {
        return this.front == null && this.rear == null;
    }

代码解释:

队列为空的条件是this.front == null && this.rear == null

3. 入队

/**
     * 元素入队,操作成功返回true
     * 
     * @param element
     * @return
     */
    @Override
    public boolean enqueue(E element) {
        if (element == null) {// 空元素不能入队
            return false;
        }
        Node<E> q = new Node<E>(element);
        if (!isEmpty()) {// 队列不为空,新的结点作为新的队尾结点
            this.rear.next = q;
        } else {// 队列为空,新的结点作为头结点
            this.front = q;
        }
        this.rear = q;// 队尾结点指向新结点q
        return true;
    }

代码解释:

入队操作将新结点链在队尾结点之后,并使rear指向新的队尾结点;

4.出队

/**
     * 出队,返回当前对头元素,若队列为空则返回null
     * 
     * @return
     */
    @Override
    public E dequeue() {
        if (!isEmpty()) {
            E temp = this.front.data;// 取得对头元素
            this.front = this.front.next;// 删除对头结点
            if (this.front == null) {// 如果对头为空,则是空队列,队尾也置为空
                this.rear = null;
            }
            return temp;
        }
        return null;
    }

代码解释:

出队操作是在队列不为空的情况下,取得队头结点值,删除该结点,并使front指向其后继结点。

5.重写toString()方法

/**
     * 返回队列中各元素的字符串表示
     */
    @Override
    public String toString() {
        String str = "(";
        Node<E> p = this.front;
        while (p != null) {
            if (p == this.rear) {// 尾结点
                str += p.data;
            } else {
                str += p.data + ",";
            }
            p = p.next;
        }
        return str + ")";
    }

三. 测试

package org.light4j.dataStructure.linearList.queue.link;

import org.light4j.dataStructure.linearList.queue.QQueue;

public class Test {
    public static void main(String[] args) {
        QQueue<String> queue = new LinkedQueue<String>();
        queue.dequeue();//出栈
        System.out.println(queue.toString());
        queue.enqueue("A");// 元素在队尾入队
        queue.enqueue("B");
        queue.enqueue("C");
        queue.enqueue("D");
        System.out.println(queue.toString());
        queue.dequeue();// 对头出队
        System.out.println(queue.toString());
    }
}

运行结果如下图所示:

四.时间复杂度分析

链式队列的入队enqueue()和出队dequeue()操作的时间复杂度为O(1)

五.源代码示例

github地址:点击查看
码云地址:点击查看

打赏
欢迎关注人生设计师的微信公众账号
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(十五):链式队列的实现

分享到:更多 ()

人生设计师-接受不同的声音

联系我关于我