数据结构-队列

栏目: 数据库 · 发布时间: 5年前

内容简介:数据结构-队列队列(queue)在计算机科学中,是一种先进先出的线性表。它只允许在表的前端进行删除操作,而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

数据结构-队列

定义

队列(queue)在计算机科学中,是一种先进先出的线性表。

它只允许在表的前端进行删除操作,而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

基于自定义数组实现的队列

新建queue接口,用来规范所有queue子类

package com.datastructure.queue;

import java.awt.*;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 16:44
 **/
public class LoopQueue<E> implements Queue<E> {

    private E[] data;

    //指向队列的第一个元素,初始指向0
    private int front;

    //指向队列的最后一个元素的后一个位置,初始指向0
    private int tail;

    private int size;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity+1];
        front=0;
        tail=0;
        size=0;
    }

    public LoopQueue(){
        this(10);
    }

    /**
     * 因为容量放的时候多了个1,所以get容量的时候,需要减1
     * @return
     */
    public int getCapacity(){
        return data.length-1;
    }


    /**
     * 1.if((tail + 1) % data.length == front) 如果tail + 1 超过了data.length的大小,
     *   代表当前tail指向已经超出了容量的大小,因为是循环式,所以需要tail去循环头元素中查看值是否有被占用,
     *   如果 == front 代表循环头没有,就需要扩容了。
     * 2.举例: 元素容量为8,tail目前指向7 front 指向2
     *          if((7 + 1) % 8 == 2 )  if(0 == 2) 这里是false,因为front指向了2,所以代表 第0,1位是没有值的
     *          所以这个值需要在在第0位放(空间利用)
     * 3.data[tail] = param  tail当前指向的地方需要赋值,然后tail自增 循环体 的1,size+1
     * @param param
     */
    @Override
    public void enqueue(E param) {
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = param ;
        tail = (tail + 1) % data.length;
        size ++ ;
    }

    /**
     * 扩充队列的容量
     * 1.front代表了当前元素初始位置的指向
     * 2.newData的第i位元素,应该等于 i + front % data.length 的值
     * 3.举例:元素容量20,i 等于 0 ,front 等于 2,结果: newData[0] = data[(0 + 2) %  20]
     *         = data[2]   意思就是,newData的第一位元素,应该等于data有值的第一位元素
     *         % data.length 的原因主要是为了防止数组越界错误
     * 4.新数组赋值完成需要将 front 重新指向0,因为新数组的front指针是从0开始的。
     *   tail最后要指向等于size大小的值,
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i++){
            newData[i] = data[(i + front ) % data.length];
        }
        data=newData;
        front = 0 ;
        tail = size;
    }

    /**
     * 1.如果队列为空抛出异常
     * 2.用ret变量来接受当前队列头的值
     * 3.接收成功之后将,队列头元素置空
     * 4.front指针指向下一个元素
     * 5.size大小-1
     * 6.如果size大小占据了容量的1/4和size为容量的1/2且不等于0的时候,对容量进行缩减,缩减为原来容量的1/2
     * 7.返回ret变量
     * @return
     */
    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("dequeue is fail ,because queue is empty");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size -- ;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0 ){
            resize(getCapacity() / 2 );
        }
        return ret;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 当front和tail的值相等时,队列为空,初始两个指向的是同一个值(只有初始的时候,指向的是同一个地方)
     * @return
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 1.元素从 front位置开始循环遍历,i的值不能等于tail,
     *   也就是到tail的前一位,i = i + 1 且%data.length,
     *   因为i有可能从循环头重新开始
     * 2.( i + 1 ) % data.length != tail  如果当前i + 1 % data.length
     *   不等于tail表示不到最后一个元素,就拼接,
     * @return
     */
    @Override
    public String toString(){
        StringBuffer sb = new StringBuffer();
        sb.append(String.format("Array: size = %d , capacity = %d\n", size, getCapacity()));
        sb.append("front [");
        for (int i = front; i != tail ; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if (( i + 1 ) % data.length != tail) {
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }
}

新建ArrayQueue实现类

package com.datastructure.queue;

import com.datastructure.array.Array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 18:19
 **/
public class ArrayQueue<E> implements Queue<E>{

    Array<E> array;


    public ArrayQueue(int capacity){
        array=new Array<E>(capacity);
    }



    public ArrayQueue(){
        array=new Array<E>();
    }


    @Override
    public void enqueue(E param) {
        array.addLast(param);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public String toString(){
        StringBuffer sb = new StringBuffer();
        sb.append("front: ");
        sb.append("[");
        for(int i=0;i<array.getSize();i++){
            sb.append(array.get(i));
            if(i!=array.getSize()-1){
                sb.append(", ");
            }
        }
        sb.append("]  tail");
        return sb.toString();
    }
}

测试类

package com.datastructure.queue;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 18:26
 **/
public class QueueTest {

    public static void main(String[] args) {
        ArrayQueue<Integer> integerArrayQueue = new ArrayQueue<>();
        for (int i = 0; i < 10; i++) {
            integerArrayQueue.enqueue(i);
            System.out.println(integerArrayQueue);


            if(i % 3 == 2){
                integerArrayQueue.dequeue();
                System.out.println(integerArrayQueue);
            }
        }
    }

}

测试结果

front: [0]  tail
front: [0, 1]  tail
front: [0, 1, 2]  tail
front: [1, 2]  tail
front: [1, 2, 3]  tail
front: [1, 2, 3, 4]  tail
front: [1, 2, 3, 4, 5]  tail
front: [2, 3, 4, 5]  tail
front: [2, 3, 4, 5, 6]  tail
front: [2, 3, 4, 5, 6, 7]  tail
front: [2, 3, 4, 5, 6, 7, 8]  tail
front: [3, 4, 5, 6, 7, 8]  tail
front: [3, 4, 5, 6, 7, 8, 9]  tail

可以看到测试结果是正确的,也符合队列结构的数据存取,但是因为是基于自定义数组来实现的,所以会调用数组方法的removeFirst方法,删除第一个元素的同时,会重新将后面所有元素前移,索引前移,均摊时间复杂度为O(n)。

循环队列

循环队列中有两个新词,两个指针

  • front 指向队列的第一个元素,初始指向0
  • tail 指向队列的最后一个元素的后一个位置,初始指向0

数据结构-队列

建立一个loopqueue实现queue接口

package com.datastructure.queue;

import java.awt.*;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 16:44
 **/
public class LoopQueue<E> implements Queue<E> {

    private E[] data;

    //指向队列的第一个元素,初始指向0
    private int front;

    //指向队列的最后一个元素的后一个位置,初始指向0
    private int tail;

    private int size;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity+1];
        front=0;
        tail=0;
        size=0;
    }

    public LoopQueue(){
        this(10);
    }

    /**
     * 因为容量放的时候多了个1,所以get容量的时候,需要减1
     * @return
     */
    public int getCapacity(){
        return data.length-1;
    }


    /**
     * 1.if((tail + 1) % data.length == front) 如果tail + 1 超过了data.length的大小,
     *   代表当前tail指向已经超出了容量的大小,因为是循环式,所以需要tail去循环头元素中查看值是否有被占用,
     *   如果 == front 代表循环头没有,就需要扩容了。
     * 2.举例: 元素容量为8,tail目前指向7 front 指向2
     *          if((7 + 1) % 8 == 2 )  if(0 == 2) 这里是false,因为front指向了2,所以代表 第0,1位是没有值的
     *          所以这个值需要在在第0位放(空间利用)
     * 3.data[tail] = param  tail当前指向的地方需要赋值,然后tail自增 循环体 的1,size+1
     * @param param
     */
    @Override
    public void enqueue(E param) {
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = param ;
        tail = (tail + 1) % data.length;
        size ++ ;
    }

    /**
     * 扩充队列的容量
     * 1.front代表了当前元素初始位置的指向
     * 2.newData的第i位元素,应该等于 i + front % data.length 的值
     * 3.举例:元素容量20,i 等于 0 ,front 等于 2,结果: newData[0] = data[(0 + 2) %  20]
     *         = data[2]   意思就是,newData的第一位元素,应该等于data有值的第一位元素
     *         % data.length 的原因主要是为了防止数组越界错误
     * 4.新数组赋值完成需要将 front 重新指向0,因为新数组的front指针是从0开始的。
     *   tail最后要指向等于size大小的值,
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i++){
            newData[i] = data[(i + front ) % data.length];
        }
        data=newData;
        front = 0 ;
        tail = size;
    }

    /**
     * 1.如果队列为空抛出异常
     * 2.用ret变量来接受当前队列头的值
     * 3.接收成功之后将,队列头元素置空
     * 4.front指针指向下一个元素
     * 5.size大小-1
     * 6.如果size大小占据了容量的1/4和size为容量的1/2且不等于0的时候,对容量进行缩减,缩减为原来容量的1/2
     * 7.返回ret变量
     * @return
     */
    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("dequeue is fail ,because queue is empty");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size -- ;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0 ){
            resize(getCapacity() / 2 );
        }
        return ret;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 当front和tail的值相等时,队列为空,初始两个指向的是同一个值(只有初始的时候,指向的是同一个地方)
     * @return
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 1.元素从 front位置开始循环遍历,i的值不能等于tail,
     *   也就是到tail的前一位,i = i + 1 且%data.length,
     *   因为i有可能从循环头重新开始
     * 2.( i + 1 ) % data.length != tail  如果当前i + 1 % data.length
     *   不等于tail表示不到最后一个元素,就拼接,
     * @return
     */
    @Override
    public String toString(){
        StringBuffer sb = new StringBuffer();
        sb.append(String.format("Array: size = %d , capacity = %d\n", size, getCapacity()));
        sb.append("front [");
        for (int i = front; i != tail ; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if (( i + 1 ) % data.length != tail) {
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }
}

测试代码

package com.datastructure.queue;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 18:26
 **/
public class QueueTest {



    public static void main(String[] args) {
        LoopQueue<Integer> integerArrayQueue = new LoopQueue<>();
        for (int i = 0; i < 10; i++) {
            integerArrayQueue.enqueue(i);
            System.out.println(integerArrayQueue);


            if(i % 3 == 2){
                integerArrayQueue.dequeue();
                System.out.println(integerArrayQueue);
            }
        }
    }
}

测试结果

Array: size = 1 , capacity = 10
front [0] tail
Array: size = 2 , capacity = 10
front [0, 1] tail
Array: size = 3 , capacity = 10
front [0, 1, 2] tail
Array: size = 2 , capacity = 5
front [1, 2] tail
Array: size = 3 , capacity = 5
front [1, 2, 3] tail
Array: size = 4 , capacity = 5
front [1, 2, 3, 4] tail
Array: size = 5 , capacity = 5
front [1, 2, 3, 4, 5] tail
Array: size = 4 , capacity = 5
front [2, 3, 4, 5] tail
Array: size = 5 , capacity = 5
front [2, 3, 4, 5, 6] tail
Array: size = 6 , capacity = 10
front [2, 3, 4, 5, 6, 7] tail
Array: size = 7 , capacity = 10
front [2, 3, 4, 5, 6, 7, 8] tail
Array: size = 6 , capacity = 10
front [3, 4, 5, 6, 7, 8] tail
Array: size = 7 , capacity = 10
front [3, 4, 5, 6, 7, 8, 9] tail

打印结果跟自定义数组的结果是一样的,但是因为引用了指针这个概念,删除的时候索引不会重排,均摊时间复杂度为O(1)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Oricle8i Web开发指南

Oricle8i Web开发指南

(美)Bradley D.Brown / 机械工业出版社 / 2001-6 / 78.00元

本书用实际通用的策略,阐明了怎样一起来看看 《Oricle8i Web开发指南》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具