数据结构之队列

定义

队列，是一种先进先出(FIFO, firt in first out)的线性表。队列的特性是只允许在一端进行插入操作，而在另一端进行删除操作。允许插入的一端称为队尾，允许删除的一端称为队头。类似于火车站排队买票的队列。

队列分为普通队列和循环队列，一般使用循环队列，因为循环队列有更高的时间和空间效率。

---

具体实现

/**
 * 循环队列实现
 */
public class MyQueue {

    private int[] mData; //队列存储内容
    private int mQueueCapacity;  //队列容量
    private int mQueueLength; //队列长度
    private int mFront;  //队头
    private int mRear;   //队尾

    public MyQueue(int capacity) {
        this.mQueueCapacity = capacity;
        mData = new int[capacity];
        mQueueLength = 0;
        mFront = 0;
        mRear = 0;
    }

    /**
     * 清空队列
     */
    public void clearQueue() {
        mQueueLength = 0;
        mFront = 0;
        mRear = 0;
    }

    /**
     * 获取队列长度
     * @return
     */
    public int getQueueLength() {
        return mQueueLength;
    }

    /**
     * 队列是否已满
     * @return
     */
    public boolean isQueueFull() {
        return mQueueLength == mQueueCapacity;
    }

    /**
     * 队列是否为空
     * @return
     */
    public boolean isQueueEmpty() {
        return mQueueLength == 0;
    }

    /**
     * 入队
     * @param element
     * @return
     */
    public boolean enQueue(int element) {
        if (isQueueFull()) {
            return false;
        }
        mData[mRear] = element;
        mRear = (mRear + 1) % mQueueCapacity;
        mQueueLength++;
        return true;
    }

    /**
     * 出队
     * @return
     */
    public boolean deQueue() {
        if (isQueueEmpty()) {
            return false;
        }
        mFront = (mFront + 1) % mQueueCapacity;
        mQueueLength--;
        return true;
    }

    /**
     * 遍历队列
     */
    public void queueTraverse() {
        for (int i = mFront; i < mFront + mQueueLength; i++) {
            int temp = mData[i % mQueueCapacity];
            System.out.println(temp);
        }
    }

    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        MyQueue q = new MyQueue(5);

        q.enQueue(1);
        q.enQueue(2);
        q.enQueue(33);

        q.deQueue();
        q.deQueue();

        q.queueTraverse();

        System.out.println("size = " + q.getQueueLength());

        q.enQueue(4);
        q.enQueue(5);
        q.enQueue(6);

        q.enQueue(7);
        q.enQueue(7);
        q.enQueue(7);

        q.queueTraverse();

        System.out.println("size = " + q.getQueueLength());

        q.clearQueue();
        q.enQueue(666);
        q.queueTraverse();

    }
}

视频课程：[慕课网]数据结构探险—队列篇