1. 前言
我们可以使用单向循环链表来实现队列.队列的特点是FIRST IN FIRST OUT.从队头删除节点，从队尾增加节点.
本文实现了从队头添加元素，从队尾删除元素.
2. 实现
自定义的Queue接口.
public interface Queue<E> { //向队伍插入值, 插入成功返回true, 否则返回false boolean offer(E value); //对队头获取值, 但不移除 E poll(); //从队头获取值, 并移除队头 E peek(); //判断队伍是否为空 boolean isEmpty(); }
实现部分 :
public class LInkedListQueue<E> implements Queue<E>, Iterable<E>{ private static class Node<E> { E value; Node<E> next; public Node(E value, Node next) { this.value = value; this.next = next; } } //head指针指向队头 Node<E> head; //tail指针指向队尾 Node<E> tail; //队伍的实际长度 int size; //队伍最大容量 int capacity = Integer.MAX_VALUE; Node<E> dummy; public LInkedListQueue() { //初始化哨兵节点, 其next指针指向自身 dummy = new Node(null, null); dummy.next = dummy; tail = dummy; head = dummy; } public LInkedListQueue(int capacity) { this(); this.capacity = capacity; } @Override public boolean offer(E value) { Node p = new Node(value, head); tail.next = p; size++; //移动尾指针, 使尾指针指向尾节点 tail = p; if(size > capacity) { return false; } return true; } @Override public E poll() { //如果队列为空, 则返回null if(isEmpty()) { return null; } E value = head.next.value; return value; } @Override public E peek() { //如果队列为空, 则返回null if(isEmpty()) { return null; } E value; //如果队列只有一个元素, if(head.next == tail) { value = head.next.value; head.next = null; tail = head; size--; } else { value = head.next.value; head.next = head.next.next; } return value; } @Override public boolean isEmpty() { //只有当head, tail指针都指向哨兵节点时, 此时队伍为空 return head == tail; } @Override public Iterator<E> iterator() { return new Iterator<E>() { Node<E> p = dummy.next; @Override public boolean hasNext() { return p != head; } @Override public E next() { E value = p.value; p = p.next; return value; } }; } }
单元测试 :
public class LInkedListQueueTest { @Test public void test() { LInkedListQueue<Integer> queue = new LInkedListQueue<>(); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); queue.offer(5); queue.offer(6); // for (Integer element : queue) { // System.out.println(element); // } System.out.println(queue.poll()); //1 System.out.println(queue.peek()); //1 System.out.println(queue.poll()); //2 } }
