队列 - Queue

基本概念

队列和栈类似，不同的是，先进队列的元素，最先从队列出去。

实现

• 通过链表实现队列

interface InterfaceQueue {
    void push(int val);
    int pop();
    int top();
}

class Node {
    public int val;
    public Node next, prev;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

public class MyQueue implements InterfaceQueue{
    public Node first, last;
    public MyQueue() {
        first = null;
        last = null;
    }
    @Override
    public void push(int val) {
        if (last == null) {
            last = new Node(val);
            first = last;
        } else {
            Node node = new Node(val);
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }
    @Override
    public int pop() {
        if (first == null) {
            return -1;
        } else {
            int res = first.val;
            first = first.next;
            if (first == null) {
                last = null;
            } else {
                first.prev = null;
            }
            return res;
        }
    }
    @Override
    public int top() {
        if (first == null) {
            return -1;
        } else {
            return first.val;
        }
    }
}

Java中，队列是一个接口，一般通过LinkedList实现。

Queue<Integer> q = new LinkedList<>();
q.offer(); // 入队
q.poll(); // 出队，并返回该元素
q.peek(); // 返回队列头元素，但不弹出

Lintcode 相关练习

Binary Tree Level Order Traversal
Implement Queue by Two Stacks
Animal Shelter