1. Sequential queue (loop)
Array-based loop queues are simple, resetting the queue entry and queue exit positions to the head of the array when the array is full.
public class CircleQueue<E> {
// Object saves E because E cannot be E[] --> (E)obj
private Object[] items;
private int putIdx; // The actual team position
private int takeIdx; // The actual queue position
private int count; The size of the queue does not change after the array is initialized
// Specify capacity initialization
public CircleQueue(int size) {
this.items = new Object[size];
this.count = 0;
this.putIdx = 0;
this.takeIdx = 0;
}
public boolean enqueue(E e) {
// Return when it is full
if (count == items.length) return false;
/ / in the
items[putIdx] = e;
PutIdx (++)
// If putIdx reaches the last element of the array, it returns to 0
if (++putIdx == items.length) putIdx = 0;
count++;
return true;
}
public E dequeue(a) {
// Return null if the queue is empty
if (count == 0) return null;
E res = (E) items[takeIdx];
TakeIdx (++); takeIdx (++);
// If takeIdx reaches the last element of the array, it returns to 0
if (++takeIdx == items.length) takeIdx = 0;
count--;
return res;
}
public E peek(a) {
// Be careful not to make null judgments
return count == 0 ? null: (E)items[takeIdx]; }}Copy the code
2. Chain queue
Before looking at the code, note a few non-null judgments:
- An empty queue can be determined if:
- head = null
- tail = null
- head = tail = null
- Non-empty judgment required when entering/leaving the team:
- Enqueue: tail = head = node if empty
- Dequeue
- Empty before queue exit: return null
- Tail = head = null
public class LinkedQueue<E> {
class Node<E> {
E item;
Node<E> next;
public Node(E e) {
this.item = e; }}private Node head; / / team first
private Node tail; / / of the
public LinkedQueue(a) {
// Head = tail = null when queue is empty
head = tail = null;
}
public void enqueue(E e) {
Node node = new Node(e);
// The queue is empty
if(tail == null) {
head = tail = node;
}else{ tail.next = node; tail = node; }}public E dequeue(a) {
// The queue is empty
if (head == null) {
return null;
}
E item = (E)head.item;
// The queue is empty
if (head.next == null) {
head = tail = null;
}
return item;
}
public E peek(a) {
return this.head == null ? null : (E)this.head.item; }}Copy the code
LinkedList is also an implementation of Queue. For more details, please refer to LinkedList source code analysis.