数据结构06 队列 - nnngu - 博客园

数据结构06 队列

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

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

 

测试结果:

 

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

 

 

欢迎转载,但请保留文章原始出处

本文地址:http://www.gzlawfc.com/nnngu/p/8277506.html 

 

posted @ 2018-01-13 00:10 nnngu 阅读(...) 评论(...) 编辑 收藏