数据结构–队列的实现(采用数组方式)

作者 : 开心源码 本文共3016个字,预计阅读时间需要8分钟 发布时间: 2022-05-13 共155人阅读

队列概述

队列是一种先进先出的线性表(first in first out,简称FIFO)。它只允许在队列的一段插入数据,另一端取出数据。允许插入数据的一端叫做队尾(rear),允许删除的一段则称为队头(front)。

队列无论在实际生活中还是在开发中都是非常常见的。比方我们去银行办理业务的排号系统就是队列。消息中间件也是队列的思想。

队列ADT

下面给出队列的笼统定义,在后文中我们将以此ADT开发队列的实现。

/** * @author jaune * @since 1.0.0 */public interface Queue<E> {    /**     * 查看队列中的第一个元素,仅仅查看元素,不从队列中取出。     * @return 队列中的第一个元素     * @throws NoSuchElementException 队列为空时抛出     */    E peek();    /**     * 向队列中增加元素,元素增加到队尾。     */    void push(E e);    /**     * 从队列中取出第一个元素。     * @return 队列中的第一个元素。     * @throws NoSuchElementException 队列为空时抛出     */    E pop();    /**     * 清空队列并     */    void clear();    /**     * 队列中元素的数量,假如队列为空,则返回0     *     * @return 队列中元素的数量     */    int size();    /**     * 判断队列能否为空     * @return true-空,false-非空     */    boolean isEmpty();    /**     * 判断队列是已满     * @return true-已满,false-未满     */    boolean isFull();}

使用数组实现的基本思想

定义两个指针,一个指向队头(front),一个指向队尾(rear)。

当从队列中取出元素时,front指针后移;当向队列中增加元素时rear指针后移。

当队头和队尾在同一个位置时,队列为空。

采用数组的方式实现队列的最大问题就是,当frontrear指针一律指向队列的尾部时,队列失效了。无法增加新的元素至队列中。当增加元素时由于指针指向队尾,所以出现队列已满的情况。在后面我将详情如何解决这种情况。在本文中对这种情况不做解决。

代码实现

package com.codestd.study.queue;import java.util.NoSuchElementException;/** * 数组队列的实现 * * @author jaune * @since 1.0.0 */public class ArrayQueue<T> implements Queue<T> {    final int maxSize;    final T[] queueArray;    private int front = -1;    private int rear = -1;    public ArrayQueue(int maxSize) {        this.maxSize = maxSize;        this.queueArray = (T[]) new Object[maxSize];    }    @Override    public T peek() {        if (this.isEmpty()) {            throw new NoSuchElementException("队列为空");        }        return this.queueArray[this.front + 1];    }    @Override    public void push(T t) {        if (this.isFull()) {            throw new RuntimeException("队列已满,无法增加新的元素。");        }        this.queueArray[++this.rear] = t;    }    @Override    public T pop() {        if (this.isEmpty()) {            throw new NoSuchElementException("队列为空");        }        T element = this.queueArray[++this.front];        this.queueArray[this.front] = null;        return element;    }    @Override    public int size() {        return this.rear - this.front;    }    /**     * 清空队列,并重置队头和队尾指针。     */    @Override    public void clear() {        for (int i = (this.front + 1); i <= this.rear; i++) {            this.queueArray[i] = null;        }        this.front = -1;        this.rear = -1;    }    @Override    public boolean isEmpty() {        return this.rear == this.front;    }    @Override    public boolean isFull() {        return this.rear + 1 == this.maxSize;    }}

测试代码

package com.codestd.study.queue;import org.junit.Test;import static org.assertj.core.api.Assertions.*;/** * Test for {@link ArrayQueue} */public class ArrayQueueTest {    @Test    public void test() {        Queue<Integer> queue = new ArrayQueue<>(3);        assertThat(queue.isEmpty()).isTrue();        assertThat(queue.isFull()).isFalse();        queue.push(1);        assertThat(queue.isEmpty()).isFalse();        assertThat(queue.peek()).isEqualTo(1);        assertThat(queue.size()).isEqualTo(1);        int el = queue.pop();        assertThat(queue.isEmpty()).isTrue();        assertThat(el).isEqualTo(1);        queue.push(2);        queue.push(3);        assertThat(queue.isEmpty()).isFalse();        assertThat(queue.isFull()).isTrue();        assertThat(queue.size()).isEqualTo(2);        el = queue.pop();        assertThat(el).isEqualTo(2);        el = queue.pop();        assertThat(el).isEqualTo(3);        assertThat(queue.isFull()).isTrue();        assertThat(queue.isEmpty()).isTrue();        queue.clear();        assertThat(queue.isEmpty()).isTrue();        assertThat(queue.isFull()).isFalse();        queue.push(1);        queue.clear();        assertThat(queue.isEmpty()).isTrue();        assertThat(queue.isFull()).isFalse();    }}

总结

前文中已经提到这种方式存在严重的问题,这是一个一次性的队列。在队列满了之后,就无法再往队列中插入数据了,哪怕数组中有空位置。要处理这个问题就需要用到环形数组。这部分的实现原理在下一篇文章中将。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 数据结构–队列的实现(采用数组方式)

发表回复