dummyHead 和 dummyTail 就不需要做那么多判断了
来源:4-7 带有尾指针的链表:使用链表实现队列
menghuanbaolei
2020-10-09
使用 dummyHead 和 dummyTail,就不需要那么多判断了,直接如下就好了
@Override
public void enqueue(E e) {
dummyTail.next = new Node(e);
dummyTail = dummyTail.next;
size++;
}
@Override
public E dequeue() {
Node curr = dummyHead.next;
dummyHead.next = curr.next;
curr.next = null;
size--;
return curr.e;
}
话不多说,代码奉上
public class LinkedListQueue<E> implements Queue<E> {
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node dummyHead;
private Node dummyTail;
private int size;
public LinkedListQueue() {
dummyHead = dummyTail = new Node(null, null);
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E e) {
dummyTail.next = new Node(e);
dummyTail = dummyTail.next;
size++;
}
@Override
public E dequeue() {
Node curr = dummyHead.next;
dummyHead.next = curr.next;
curr.next = null;
size--;
return curr.e;
}
@Override
public E getFront() {
Node curr = dummyHead.next;
return curr.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node curr = dummyHead.next;
while (curr != null) {
res.append(curr + "->");
curr = curr.next;
}
res.append("NULL tail");
return res.toString();
}
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for(int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if (i % 3 == 2) {
queue.dequeue();
System.out.println(queue);
}
}
}
}
写回答
2回答
-
qq_慕神7027777
2021-01-08
我看代码好像貌似:虚拟头节点起作用了;虚拟尾节点就是指向链表的最后一个节点。
012021-07-25 -
liuyubobobo
2020-10-09
感谢分享。继续加油!:)
00
相似问题