数据结构(二) - 队列

顺序队列

简介

队列是一个特殊的线性表.只允许在表的一端插入元素.而在另一端取元素.允许取操作的一端称为队头(front),插入操作的一端称为队尾(rear).

特点 :

1 : 有序列表,可用数组或链表进行实现.

2 : 先进先出.

图形

Demo

package com.xbb.demo;

/**
 * 队列
 */
public class ArrayQueueDemo {

    /**
     * 队列的最大容量
     */
    private int maxSize;
    /**
     * 队列头位置
     */
    private int head = -1;
    /**
     * 队列尾位置
     */
    private int tail = -1;

    /**
     * 队列
     */
    private int[] arrQueue;

    /**
     * 创建一个队列
     * @param length : 队列长度
     */
    public ArrayQueueDemo(int length){
        maxSize = length;
        arrQueue = new int[length];
    }

    /**
     * 向队列中添加数据
     */
    public void put(int data){
        if (isFull()){
            System.out.println("队列已满");
            return;
        }
        arrQueue[++head] = data;
    }

    /**
     * 从队列中取出数据
     */
    public int get(){
        if (isEmpty()){
            System.out.println("队列为空");
            return -1;
        }
        return arrQueue[++tail];
    }

    /**
     * 判断队列是否满
     * @return
     */
    public boolean isFull(){
        return arrQueue.length == head+1;
    }

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

    public static void main(String[] args) {
        ArrayQueueDemo arrayQueueDemo = new ArrayQueueDemo(5);
        arrayQueueDemo.put(1);
        arrayQueueDemo.put(2);
        arrayQueueDemo.put(3);
        arrayQueueDemo.put(4);
        arrayQueueDemo.put(5);
        arrayQueueDemo.put(6);
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        arrayQueueDemo.put(6);
        System.out.println(arrayQueueDemo.get());
    }
}

环形队列:

问题 : 上面的Demo中.队列用完一次就不可以再用了.只是一个一次性的队列.现实中.这种是不可取的.我们需要让队列可以循环使用.有进有出.空出来的位置可以再填补新的值进去.

解决方法 : 通过算法把队列修改成一个环形队列(通过取模的方法)

图解:

通过以下程式可以完美的解决一次性使用的问题.
算法 : 判空和与非空操作

package com.xbb.demo;

/**
 * 队列
 */
public class ArrayQueueUpDemo {

    /**
     * 队列的最大容量
     */
    private int maxSize;
    /**
     * 队列头位置
     */
    private int head;
    /**
     * 队列尾位置
     */
    private int tail;

    /**
     * 队列
     */
    private int[] arrQueue;

    /**
     * 创建一个队列
     * @param length : 队列长度
     */
    public ArrayQueueUpDemo(int length){
        maxSize = length;
        arrQueue = new int[length];
    }

    /**
     * 向队列中添加数据
     */
    public void put(int data){
        if (isFull()){
            System.out.println("队列已满");
            return;
        }
        arrQueue[tail] = data;
        tail = (tail + 1) % maxSize;
    }

    /**
     * 从队列中取出数据
     */
    public int get(){
        if (isEmpty()){
            System.out.println("队列为空");
            return -1 ;
        }
        int value = arrQueue[head];
        head = (head + 1) % maxSize;
        return value;

    }

    /**
     * 判断队列是否满
     * @return
     */
    public boolean isFull(){
        return (tail+1) % maxSize == head;
    }

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

    /**
     * 获取数组长度
     */
    public int count(){
        return maxSize-1;
    }

    public static void main(String[] args) {
        ArrayQueueUpDemo arrayQueueDemo = new ArrayQueueUpDemo(3);
        arrayQueueDemo.put(1);
        arrayQueueDemo.put(2);
        arrayQueueDemo.put(3);
        arrayQueueDemo.put(4);
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        arrayQueueDemo.put(6);
        arrayQueueDemo.put(7);
        arrayQueueDemo.put(8);
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
        System.out.println(arrayQueueDemo.get());
    }
}