首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构06 队列

数据结构06 队列

作者头像
nnngu
发布2018-03-15 15:55:49
4960
发布2018-03-15 15:55:49
举报
文章被收录于专栏:nnngunnngu

上一篇讲了,这一篇要讲的是我们常用的队列,我会从以下几个方面进行总结。

1、什么是队列  2、队列的存储结构 3、队列的常用操作及实现代码

1、什么是队列 

(1)首先,队列也是一种特殊的线性表,它是一种操作受限的线性表。只允许在表的一端进行元素插入,而在另一端进行元素删除。允许插入的一端称为队尾,允许删除的一端称为队头。

(2)队列与现实生活中的排队类似(如下图),新加入的成员总是在队尾,而排在队列最前面的总是最先离开队列,即先进先出 First In First Out (FIFO),因此队列就是先进先出线性表。

 (3)线性表分为顺序表和链表,所以队列也分为顺序队列链式队列,为了方便演示,下文所使用的队列都是顺序队列

2、队列的存储结构

用java语言自己封装一个顺序队列:

SeqQueue.java

/**
 * 封装一个顺序队列
 */
public class SeqQueue {
    // 保存数据
    public Object[] data;

    // 头指针
    public int head;

    // 尾指针
    public int rear;

    // 队列的最大容量
    public int maxSize;

    public SeqQueue(int maxSize) {
        this.maxSize = maxSize;
        data = new Object[maxSize];
    }
}

3、队列的常用操作及实现代码

3-1、初始化队列

思路:构造一个空队列,并将头指针head和尾指针rear都设置为0。

代码:SeqQueueOperate.java

/**
 * 封装队列的常见操作
 */
public class SeqQueueOperate {
    /**
     * 初始化
     *
     * @param maxSize
     * @return
     */
    public SeqQueue init(int maxSize) {
        SeqQueue queue = new SeqQueue(maxSize);
        queue.head = 0;
        queue.rear = 0;
        return queue;
    }
}

3-2、入队

思路:若队列没有满,则将数据插入到尾指针rear指向的位置,然后再将rear加1。

代码:在 SeqQueueOperate.java 中添加方法

    /**
     * 入队
     */
    public void enter(SeqQueue queue, Object obj) {
        // 判断队列是否已经满了
        if (queue.rear >= queue.maxSize) {
            return;
        }
        queue.data[queue.rear] = obj;
        queue.rear++;
    }

3-3、出队

思路:若队列不为空,则将头指针指向的元素删除,然后将头指针加1。

代码:在 SeqQueueOperate.java 中添加方法

    /**
     * 出队
     */
    public Object dequeue(SeqQueue queue) {
        // 判断队列是否为空
        if (queue.head == queue.rear) {
            return null;
        }
        Object obj = queue.data[queue.head];
        queue.data[queue.head] = null;
        queue.head++;
        return obj;
    }

3-4、取队头

思路:若队列不为空,则返回队头元素。

代码:在 SeqQueueOperate.java 中添加方法

    /**
     * 取队头
     */
    public Object getHead(SeqQueue queue) {
        // 判断队列是否为空
        if (queue.head == queue.rear) {
            return null;
        }
        Object obj = queue.data[queue.head];
        return obj;
    }

3-5、取队长

思路:即尾指针 - 头指针的值。

代码:在 SeqQueueOperate.java 中添加方法

    /**
     * 取队长
     */
    public int getLength(SeqQueue queue) {
        return queue.rear - queue.head;
    }

3-6、判队空

思路:只需要判断头指针和尾指针是否相等即可

代码:在 SeqQueueOperate.java 中添加方法

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty(SeqQueue queue) {
        return queue.head == queue.rear;
    }

3-7、判队满

思路:只需判断尾指针与maxSize是否相等即可

代码:在 SeqQueueOperate.java 中添加方法

    /**
     * 判断队列是否已经满了
     */
    public boolean isFull(SeqQueue queue) {
        return queue.rear >= queue.maxSize;
    }

4、测试

添加一个用来测试的类

QueueTest.java

/**
 * 用来测试
 */
public class QueueTest {
    public static void main(String[] args) {
        SeqQueueOperate seqQueueOperate = new SeqQueueOperate();
        // 最大容量设置为5
        int maxSize = 5;
        SeqQueue queue = seqQueueOperate.init(maxSize);
        System.out.println("队列的最大容量是:" + maxSize);

        // 当前队列的长度
        System.out.println("当前队列的长度是:" + seqQueueOperate.getLength(queue));
        System.out.println("");

        System.out.println("===========入队start ===========");
        System.out.println("插入6个元素试试");
        seqQueueOperate.enter(queue, 1);
        seqQueueOperate.enter(queue, 2);
        seqQueueOperate.enter(queue, 3);
        seqQueueOperate.enter(queue, 4);
        seqQueueOperate.enter(queue, 5);
        seqQueueOperate.enter(queue, 6);
        System.out.println("===========入队end =============");
        // 当前队列的长度
        System.out.println("当前队列的长度是:" + seqQueueOperate.getLength(queue));
        System.out.println("");

        // 出队
        System.out.println("===========出队start ===========");
        Object obj = seqQueueOperate.dequeue(queue);
        System.out.println("出队的元素是:" + obj);
        System.out.println("===========出队end =============");
        // 当前队列的长度
        System.out.println("当前队列的长度是:" + seqQueueOperate.getLength(queue));
        System.out.println("");

        System.out.println("------------------------------------");
        System.out.println("队头元素是:" + queue.data[queue.head]);
        System.out.println("队尾元素是:" + queue.data[queue.rear-1]);
    }
}

测试结果:

 注意:在一个非空的队列中,头指针始终指向队头元素,而尾指针始终指向队尾元素的下一个位置

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1、什么是队列 
  • 2、队列的存储结构
  • 3、队列的常用操作及实现代码
    • 3-1、初始化队列
      • 3-2、入队
        • 3-3、出队
          • 3-4、取队头
            • 3-5、取队长
              • 3-6、判队空
                • 3-7、判队满
                • 4、测试
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档