Java数据结构之队列

2016/12/7 posted in  Algorithm

什么是队列

  • 队列是一种受限的线性表,其限制是仅允许在队的一端进行插入,而在队的另一端进行删除.
  • 在队列中把插入数据元素的一端称为队尾(rear).
  • 删除数据元素的一端称为队首(front).
  • 向队尾插入元素称为进队或入队.新元素入队后成为新的队尾元素.
  • 从队列中删除元素称为离队或出队.元素出队后,其后续元素成为新的队首元素
  • 因此在队列中,先入队的元素,肯定是先出队.所以称队列为先进先出表(FIFO).

队列结构与日常生活中排队等候服务的模型是一致的,最早进入队列的人,最早得到服务从队首离开;最后到来的人只能排在队列的最后,最后得到服务并最后离开.

队列的常用方法

队列结构一般都满足以下几个方法:

方法 功能描述
getSize() 返回队列的大小,即队列中元素的个数
isEmpty() 判断队列是为空
enqueue(e) 将元素e入队
dequeue 删除队尾元素
peek() 获取队首元素,但不出队

接口代码如下:

/**
 * Created by HuShiwei on 2016/10/18 0018.
 * FIFO先进先出
 */
public interface Queue {
    public int getSize();//返回队列的大小

    public boolean isEmpty();//判断队列是否为空

    public void enqueue(Object e);//数据元素e入队

    public Object dequeue();//队首元素出队

    public Object peek();//取队首元素
}

队列的线性表实现

实现分析

队列的线性表实现:底层是用的数组存储队列元素.

queueArray

  • 如何判断队列是否满队列还是空队列
    • 设计了一个循环数组
    • 设计一个队首指针front,和一个队尾指针rear
    • front指向队列的首元素,rear指向队尾的最后一个元素+1的位置
  • 如何判断队列是空队列还是满队列?
    • 当是空队列的时候,front=rear,两个指针都指向同一个位置
    • 当是满队列的时候,因为是循环数组,所以front=rear.这样我们就没办法区分是空队列还是满队列了.
  • 如何解决这个问题呢?
    • 把数组的最后一个位置空出来,浪费最后的存储空间.
    • 这样,判断是满队列的时候,就可以根据(rear+1)%capacity=front
  • 注意点
    • 队尾指针rear指向队尾元素+1的位置.这样在队尾入队的时候就可以指针赋值了

代码实现

注意: 在实现队列的时候,一定要记住
+ 队列的结构特性,FIFO
+ 如何通过指针来操作
+ 理解了这些,自己就可以很轻松的实现队列了

/**
 * 队列的顺序存储实现
 */
public class QueueArray implements Queue {
    private static final int CAP = 7;//队列默认大小
    private Object[] elements;//数据元素数组
    private int capacity;//数组的大小
    private int front;//队首指针
    private int rear;//队尾指针

    public QueueArray() {
        this(CAP);
    }
//    初始化队列
    public QueueArray(int cap){
        capacity = cap + 1;
        elements = new Object[capacity];
        front = rear = 0;
    }
//    返回队列的大小
    @Override
    public int getSize() {
        return (rear-front+capacity)%capacity;
    }
//    判断队列是否为空
    @Override
    public boolean isEmpty() {
        return front==rear;
    }

//    数据元素e入队
    @Override
    public void enqueue(Object e) {
        if (getSize()==capacity-1) {
            expandSpace();
        }
        elements[rear] = e;
        rear = (rear + 1) % capacity;
    }

//    扩充队列大小
    private void expandSpace() {
        Object[] objects = new Object[elements.length * 2];
        int i=front;
        int j = 0;
        while (i != rear) {
            objects[j++] = elements[i];
            i = (i + 1) % capacity;
        }
        elements = objects;
        capacity = elements.length;
//        设置新的队首队尾指针
        front = 0;
        rear = j;

    }

//    队首元素出队
    @Override
    public Object dequeue() {
        if (isEmpty()) {
            try {
                throw new Exception("错误: 队列空了...");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        Object element = elements[front];
        elements[front] = null;
        front = (front + 1) % capacity;
        return element;
    }

//    取队首元素
    @Override
    public Object peek() {
        if (isEmpty()) {
            try {
                throw new Exception("错误: 队列空了...");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return elements[front];
    }
}

队列的链式存储实现

未完待续....