[数据结构与算法]数据结构之队列

1 概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First
In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）

2 底层继承

如下图所示，Java中的Queue接口的底层是一个双向链表LinkedList。

3 结构定义

• 结构定义

class Node {
    private int val;
    private Node next;
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public Node(int val) {
        this.val = val;
    }
}

4 基本方法

• 入队

public void offer(int val) {
        //尾插法  需要判断是不是第一次插入
        Node node = new Node(val);
        if(this.first == null) {
            this.first = node;
            this.last = node;
        }else {
            this.last.setNext(node);//last.next = node;
            this.last = node;
        }
    }

• 出队

public int poll() {
        //1判断是否为空的
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空！");
        }
        //this.first = this.first.next;
        int ret = this.first.getVal();
        this.first = this.first.getNext();
        return ret;
    }

• 得到队头元素但是不删除

public int peek() {
        //不要移动first
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空！");
        }
        return this.first.getVal();
    }

• 判断队空

public boolean isEmpty() {
        return this.first == null;
    }