队列的介绍

Queue是一种先进先出的数据结构，和Stack一样，他也有链表和数组两种实现，理解了Stack的实现后，Queue的实现就比较简单了。

Queue

名称	描述
Stack<T>()	创建一个空的队列
void Enqueue(T s)	往队列中添加一个新的元素
T Dequeue()	移除队列中最早添加的元素
boolean IsEmpty()	队列是否为空
int Size()	队列中元素的个数

队列的操作

Queue示意

队列主要有两种操作：从队尾添加元素，从对头删除元素。添加元素称为入队，删除元素称为出队。如图：

Queue Operations

队列的创建

队列的创建有两种形式：基于数组结构实现（顺序队列）、基于链表结构实现（链式队列）。

代码实现：

入栈时，和在普通的链表中添加结点的操作是一样的；出队时，出的永远都是head结点。

package com.pingkeke.rdf.sample;

/**
 * 通过链表的形式来创建队列，这样的话，队列在扩充时会比较方便。队列在出队时，从头结点head开始.
 */
public class Queue01 {

    class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public Node head;
    public Node curent;

    /**
     * 链表中添加结点
     * @param data
     */
    public void add(int data) {
        if (head == null) {
            head = new Node(data);
            curent = head;
        } else {
            curent.next = new Node(data);
            curent = curent.next;
        }
    }

    /**
     * 出队操作
     * @return
     * @throws Exception
     */
    public int pop() throws Exception {
        if (head == null) {
            throw new Exception("队列为空");
        }

        Node node = head;  // node结点就是我们要出队的结点
        head = head.next;  // 出队之后，head指针向下移

        return node.data;
    }

    public static void main(String[] args) throws Exception {

        Queue01 queue = new Queue01();
        // 入队操作
        for (int i = 0; i < 5; i++) {
            queue.add(i);
        }

        //出队操作
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());

        /**
         * 运行结果:
         * 0
         1
         2
         */

    }

}

使用数组实现队列

package com.pingkeke.rdf.sample;

/**
 * 使用数组实现队列.
 */
public class Queue03 {

    public static void main(String[] args) throws Exception {

        ArrayQueue queue = new ArrayQueue(3);

        System.out.println(queue.isEmpty());

        for (int i = 0; i < 3; i++) {
            queue.insert(i);
        }
        System.out.println(queue.isFull());

        while (!queue.isEmpty()) {
            System.out.println(queue.remove());
        }

        /**
         * 运行结果:
         * false
         true
         0
         1
         2
         *
         */
    }
}


class ArrayQueue {

    private int[] arrInt;   // 内置数组
    private int front;      // 头指针
    private int rear;       // 尾指针

    public ArrayQueue(int size) {
        this.arrInt = new int[size];
        front = 0;
        rear = -1;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return front == arrInt.length;
    }


    /**
     * 判断队列是否已满
     * @return
     */
    public boolean isFull() {
        return arrInt.length - 1 == rear;
    }


    /**
     * 向队列的队尾插入一个元素
     * @param item
     */
    public void insert(int item) {
        if (isFull()) {
            throw new RuntimeException("队列已满");
        }
        arrInt[++rear] = item;
    }


    /**
     * 获得队头元素
     * @return
     */
    public int peekFront() {
        return arrInt[front];
    }


    /**
     * 获得队尾元素
     * @return
     */
    public int peekRear() {
        return arrInt[rear];
    }

    /**
     * 从队列的对头移除一个元素
     * @return
     */
    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arrInt[front++];
    }
}

两个栈实现一个队列

思路：栈1用于存储元素，栈2用于弹出元素，负负得正。
说的通俗一点，现在把数据1、2、3分别入栈一，然后从栈一中出来（3、2、1），放到栈二中，那么，从栈二中出来的数据（1、2、3）就符合队列的规律了，即负负得正。

完整版代码实现：

package com.pingkeke.rdf.sample;

import java.util.Stack;

/**
 * 两个栈实现一个队列.
 */
public class Queue02 {

    private Stack<Integer> stack1 = new Stack<>();  // 执行入队操作的栈
    private Stack<Integer> stack2 = new Stack<>();  // 执行出队操作的栈

    /**
     * 给队列增加一个入队的操作
     * @param data
     */
    public void push(int data) {
        stack1.push(data);
    }


    /**
     * 给队列增加一个出队的操作
     * @return
     * @throws Exception
     */
    public int pop() throws Exception {
        /**
         * stack1中的数据放到stack2之前，先要保证stack2里面是空的
         * （要么一开始就是空的，要么是stack2中的数据出完了），
         * 不然出队的顺序会乱的，这一点很容易忘
         */

        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop()); // 把stack1中的数据出栈，放到stack2中
            }
        }


        /**
         * stack2为空时，有两种可能：
         * 1、一开始，两个栈的数据都是空的；
         * 2、stack2中的数据出完了
         */
        if (stack2.empty()) {
            throw new Exception("队列为空");
        }

        return stack2.pop();
    }


    public static void main(String[] args) throws Exception {

        Queue02 queue = new Queue02();
        queue.push(1);
        queue.push(2);
        queue.push(3);

        System.out.println(queue.pop());

        queue.push(4);

        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());

        /**
         * 运行结果:
         * 1
         2
         3
         4
         */

    }


}