但行好事  莫问前程

自己实现集合框架(十三):顺序队列的实现

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

一. 什么是顺序队列?

一样,队列也有顺序队列链式队列,链式队列在后面讲。顺序队列指采用顺序储存结构存储数据元素的队列,例如使用数组存储元素。

对队列的操作我们在实现上需要进行一些约定,操作过程描述如下所示:

1. 当队列为空时,设置对头,队尾的下标front=rear=-1,如下图所示:

2. 第一个元素入队,需要同时改变frontrear的下标,均置为0,即front=rear=0,元素10入队后如下图所示:

3. 元素2030入队后如下图所示:

4. 元素1020出队后如下图所示:

5. 元素4050入队之后如下图所示:

6. 当入队的元素个数(包括已出队元素)超过数组容量时,rear下标越界,数据溢出。例如此时元素60入队,而此时元素个数已经达到数组容量,队尾已经没有容量可用,这时候数组需要扩容,但是由于之前已有若干元素出队,数组的前部已经空出了很多的存储单元,所以,这种溢出并不是因为存储空间不够而产生的,因此称之为假溢出。元素60欲入栈如下图所示:

所以,从上面可以看出,顺序队列会出现假溢出问题。原因是由于顺序队列的存储单元没有重复使用机制,已经出队的元素占用的储存空间没办法重复利用。解决方案是将顺序队列设计成循环结构,顺序循环队列的实现在后面文章讲解。

二. 顺序队列实现

1. 定义顺序队列

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

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

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

/**
 * 顺序队列
 * 
 * @author longjiazuo
 * @param <E>
 */
public class SeqQueue<E> implements QQueue<E> {

    private Object[] value;// 存储队列数据元素的数组
    private int front;// 对头下标
    private int rear;// 队尾下标

    public SeqQueue(int capacity) {// 构造指定容量的空队列
        value = new Object[Math.abs(capacity)];
        this.front = -1;
        this.rear = -1;
    }

    public SeqQueue() {// 构造默认空队列
        this(16);
    }
}

代码解释:

定义了两个构造函数,一个无参的构造函数,队列的容量默认是16,另外一个有参的构造函数,可以指定队列的容量。

Math.abs(capacity)取队列容量的绝对值,做容错处理,防止传入负数的情况。

初始化frontrear的下标为-1

2. 判断队列是否为空

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

代码解释:

队列为空时,队头,队尾的下标front=rear=-1

3. 入队

      /**
     * 元素入队,操作成功返回true
     * 
     * @param element
     * @return
     */
    @Override
    public boolean enqueue(E element) {
        if (element == null) {// 空元素不允许入队
            return false;
        }
        if (isEmpty()) {// 空队列
            this.value[0] = element;
            this.front++;
            this.rear++;
        } else {// 非空队列,入队更改队尾结点指向
            if (this.rear == this.value.length - 1) {// 队列满则扩容
                Object[] temp = this.value;
                this.value = new Object[this.value.length * 2];// 扩容为当前队列的两倍
                for (int i = 0; i < temp.length; i++) {
                    this.value[i] = temp[i];
                }
            }
            this.value[++this.rear] = element;//
        }
        return true;
    }

代码解释:

如果队列为空,则第一个元素入队,需要同时改变frontrear的下标,均置为0,即front=rear=0

如果队列已满则需要扩容,数组扩容为原来队列的两倍。

入队需要修改队尾下标。

4.出队

/**
     * 出队,返回当前对头元素,若队列为空则返回null
     * 
     * @return
     */
    @Override
    public E dequeue() {
        if (isEmpty()) {// 如果队列为空返回null
            return null;
        }
        @SuppressWarnings("unchecked")
        E temp = (E) this.value[this.front];
        this.front++;
        return temp;
    }

代码解释:

出队需要修改队头的下标

5.重写toString()方法

       /**
     * 返回栈中各元素的字符串表示
     */
    @Override
    public String toString() {
        String str = "(";
        if (!isEmpty()) {// 判断是否非空
            for (int i = this.front; i <= this.rear; i++) {// 从对头 到队尾
                if (i == this.rear) {
                    str += this.value[i];
                } else {
                    str += this.value[i] + ",";
                }
            }
        }
        return str + ")";
    }

三. 测试

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

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

public class Test {
    public static void main(String[] args) {
        QQueue<String> queue = new SeqQueue<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),当需要扩充容量时,入队操作enqueue()的时间复杂度为O(n)

五.源代码示例

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

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

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

分享到:更多 ()

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

联系我关于我