队列的性质
- 先进先出（FIFO - First In First Out）：最先加入队列的元素最先被移出
- 后进后出（后来的元素排在队尾）
- 只允许在队尾插入元素，在队首删除元素
- 具有先来先服务的特点
链表实现队列
和之前创建链表相同，我们需要设置一个哨兵头结点 此时它既是head也是tail
后面进行添加操作的之后将每次新加的节点设置为tail，并且指向head
我们接下来实现队列的基本操作
先来写队列类和它内部Node类
public class LinkedListQueue <E>implements Queue<E>, Iterable<E>{Node<E> head=new Node<>(null,null);//头指针一直指向哨兵节点Node<E> tail=head;int size=0;int capacity=Integer.MAX_VALUE;{tail.next=head;}private static class Node<E>{E value;Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}
}public LinkedListQueue(int capacity) {this.capacity = capacity;}public LinkedListQueue() {}我们在这个类中将每次构造的队列对象的tail节点都指向head节点
接下来我们实现各个功能操作
代码如下
public boolean offer(E value) {if(isFull()){return false;}Node<E> added=new Node<>(value,head);tail.next=added;tail=added;size++;return true;}@Overridepublic E poll() {if (isEmpty()){return null;}Node<E> first=head.next;head.next=first.next;size--;return first.value;}@Overridepublic E peek() {if(isEmpty()){return null;}return head.next.value;}@Overridepublic boolean isEmpty() {return head==tail;}@Overridepublic boolean isFull() {return size==capacity;}
}
