数据结构学习笔记之队列(java)

队列

概念

• 栈是后进先出的数据结构，而队列是先进先出的，即插入数据在表的一端进行，而删除数据在表的另一端进行，插入数据一端称为队尾 (rear)，删除数据的一端称为队首 (front)。

• 抽象数据类型描述

public interface MQueue{
    //判断是否空队列
    boolean isEmpty();
    //判断是否满队列
    boolean isFull();
    //取队首
    T getHead();
    //进队
    void add(T x);
    //出队
    T remove();
}

队列可以用两种方式存储，顺序存储和链式存储，顺序队列中一种特殊的存储方式是循环队列。

链式队列

习惯上将表头作为队首，表尾作为队尾，插入和删除的复杂度都是 O(1)。

继承方式实现链式队列

/**
 * Created by nvgtor on 2016/4/27.
 * 其中 add、remove、isEmpty方法在 MLinkList 中已经实现
 */
public class MLinkQue extends MLinkList {
    public MLinkQue(){
        super();
    }

    public boolean isFull(){
        return false;
    }

    public T getHead(){
        return get(0);
    }
}

聚合方式实现链式队列

public class MLinkQue2 {
    private MLinkList linkList;
    public MLinkQue2(){
        linkList = new MLinkList();
    }

    public T getHead(){
        return linkList.get(0);
    }

    public void add(T x){
        linkList.add(x);
    }

    public T remove(){
        return linkList.remove(0);
    }

    public boolean isEmpty(){
        return linkList.isEmpty();
    }

    public boolean isFull(){
        return false;
    }
}

顺序队列

顺序队列用一个顺序表（数组）作为队列的存储空间。存在假溢出问题。假设数组 seqQue[maxSize] 作为队列的存储空间,rear 指向队尾元素的下一个位置，初始 front = rear = 0;

1. 空队列： front == rear;
2. 入队： seqQue[rear] = x; rear++;
3. 出队： x = seqQue[front]; front++;
4. 队满条件： rear == maxSize;

循环队列

把数组的头指针和尾指针链接起来，形成一个圆环，即为循环队列。可以解决假溢出问题,但是浪费一个存储单元。用数组data[maxSize]存储。

1. 队空： front == rear;
2. 队满： (rear + 1) % maxSize == front;
3. 进队： data[rear] = x; rear = (rear + 1) % maxSize;
4. 出队： x = data[front]; front = (front + 1) % maxSize;

实现：

public class MSeqQue implements MQueue {

    private int front, rear, maxSize;
    Object[] data;

    public MSeqQue(int maxQueueSize){
        maxSize = maxQueueSize + 1;
        front = rear = 0;
        data = new Object[maxSize];
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    @Override
    public T getHead() {
        return (T) data[front];
    }

    @Override
    public void add(T x) {
        data[rear] = x;
        rear = (rear + 1) % maxSize;
    }

    @Override
    public T remove() {
        T x =  (T) data[front];
        front = (front + 1) % maxSize;
        return x;
    }
}