自定义队列

队列：像排队吃饭一样，先到的先点菜，后来的后点菜。
以下代码展示使用单向列表实现的队列。

//链表是以节点为单位的，对于单向链表，每个节点中包含一个值和指向下一个对象的引用
public class Node {
    Object value;
    Node next;

    public Node(Object value) {
        this.value = value;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

public class MyQuene {
    int size = 0;

    public int getSize() {
        return size;
    }

    //维护一个head节点和foot节点
    Node head;
    Node foot;

    //加入队列尾部
    public void enQuene(Object value) {
        //如果是第一个节点，那么此节点既是根节点也是尾节点
        Node newNode = new Node(value);
        if (head == null) {
            head = foot = newNode;
        } else {
            //如果不是根节点，那么就将节点放入尾部，步骤，1，关联到尾部节点，2，foot指向此节点
            foot.setNext(newNode);
            foot = newNode;
        }
        size++;
    }

    //离队,即是把头节点指向下一个节点
    public Object deQuene() {
        Object value = head.getValue();
        head = head.getNext();
        size--;
        return value;
    }

    //显示队列头部元素
    public Object peek() {
        return head.getValue();
    }
}
//测试
public class QueneTest {
    public static void main(String[] args) {
        MyQuene myQuene = new MyQuene();
        myQuene.enQuene(1);
        myQuene.enQuene(2);
        myQuene.enQuene(3);
        myQuene.enQuene(4);

        while (myQuene.getSize() > 0) {
            System.out.println(myQuene.deQuene());
        }
    }
}
//结果：取出的顺序和进入的顺序一致。
1
2
3
4

在实现上，相比栈结构，取出数据的做法都是将头节点的指向变为下一个。
不同的是放入的顺序。栈是把新节点放在了头部，所以栈的顺序是后进先出，而队列则是把新节点放到了尾部，先被取出的则是先放进队列的，所以队列的特点是先进先出。

转载于:https://www.jianshu.com/p/7404961e37f3