队列的思想
先进先出
应用场景
消息队列,系统任务
队列实现 Java
基本API:isEmpty,size,enQueue,deQueue
package struct;
import java.util.Iterator;
public class Queue<T> implements Iterable<T> {
private Node first;
private Node last;
private int N;
public int size() {
return N;
}
public boolean isEmpty() {
return first == null;
}
public void enQueue(T val) {
Node previous = last;
last = new Node();
last.val = val;
last.next = null;
if (isEmpty()) {
first = last;
} else {
previous.next = last;
}
N++;
}
public T deQueue() {
T val = first.val;
first = first.next; // 最后一个时,first = first.next = null
// 判断条件是first == null,其实也可以用 N == 0,不过这就要把N--写在前面
if (isEmpty()) {
last = null; // first为null时,last也要为null才合理
}
N--;
return val;
}
@Override
public Iterator<T> iterator() {
return new QueueIterator();
}
// 内部类-----------------------------
private class Node {
T val;
Node next;
}
private class QueueIterator implements Iterator<T> {
Node curr = first;
@Override
public boolean hasNext() {
return curr != null;
}
@Override
public T next() {
T val = curr.val;
curr = curr.next;
return val;
}
}
// 测试类--------------------------------
//测试类---------------------------------------
public static class Test {
public static void main(String[] args) {
Queue<Integer> queue = new Queue<>();
queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
queue.enQueue(5);
Iterator iterator = queue.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
int size = queue.size();
for (int i = 0; i < size; i++) {
System.out.println(queue.deQueue());
}
}
}
}