队列也是一种操作受限的线性表。只能在队尾进行插入，队首进行删除，实现先进先出（FIFO）。
链表队列
链表队列.png
在初始状态下（即空队列），首/尾指针同时指向头节点，此时队列长度为0。
空队列.png
在队列中插入节点，将节点接入原列表，移动尾指针指向新的表尾节点即可。
插入队列.png
从队列中删除节点，即取出首指针指向的节点 并将其从队列中取出，首指针指向其原来指向的节点的下一个节点；当新的队首节点为空时，需修改队尾指针指向队首，使得队列为空队列。
出队列.png
/**
* queue
* @param <T> element type
*/
public class Queue<T> {
//front pointer: always point to the head of queue
QueueNode<T> front;
//rear pointer: always point to the tail of queue
QueueNode<T> rear;
//queue head
QueueNode<T> head;
/**
* constructor.
*/
public Queue() {
// create empty queue. front and rear both point to head.
front = rear = head = new QueueNode<>();
}
/**
* if it is an empty queue.
* @return <code>true</code> if front and rear both point to head
*/
public boolean isEmpty() {
return front == head && rear == head;
}
/**
* put element into queue.
* @param data data needs to input into queue
*/
public void enQueue(T data) {
QueueNode<T> newNode = new QueueNode<>();
newNode.data = data;
rear.next = newNode;
rear = newNode;
}
/**
* pull out element from queue.
* @return element
*/
public QueueNode<T> deQueue() {
QueueNode result = null;
if (!this.isEmpty()) {
result = front.next;
QueueNode<T> newHead = result.next;
//if it is the last element in queue, after pull out, set the queue to be empty
if (newHead == null) {
rear = front;
}
front.next = newHead;
}
return result;
}
/**
* number of elements in queue.
* @return size of queue
*/
public int getQueueSize() {
int size = 0;
if (!this.isEmpty()) {
QueueNode<T> current = front;
while (current != rear) {
current = current.next;
size++;
}
}
return size;
}
/**
* clear queue.
*/
public void clear() {
//set queue at the status of initiation
front = rear = head;
head.next = null;
}
public static void main(String[] args) {
Queue<String> queue = new Queue<>();
queue.enQueue("a");
queue.enQueue("b");
System.out.println(queue.getQueueSize());
System.out.println(queue.deQueue().data);
System.out.println(queue.isEmpty());
System.out.println(queue.getQueueSize());
}
}
class QueueNode<T> {
T data;
QueueNode next;
}
循环队列
链表队列虽然用起来很方便，但是对于他的结构而言，除单纯存储数据以外，每个节点都还额外需要一个指针域来指明它的后继。 在内存限制要求较高的情况下，相对于链表队列，循环队列更节省空间。循环队列主要以顺序存储表结构来实现，省去指针域。
循环队列.png
此时我们引入一个哨兵占位用以 表示队列是否满，如不设置哨兵位，仅用front == rear判断是否位空/满时，难以分辨；在这种情况下rear + 1 mod capability == front 则说明队列存储空间满，rear == front时队列空
/**
* circular queue.
* @param <T> element type
*/
public class CircularQueue<T> {
T[] elements;
int front;
int rear;
// max size
private final int CAPABILITY = 7;
/**
* constructor.
* create an empty queue.
*/
public CircularQueue() {
elements = (T[]) new Object[CAPABILITY];
front = rear = 0;
}
/**
* identify if queue is full.
* @return <code>true</code> if full
*/
public boolean isFull() {
// +1 for placeholder
return (rear + 1) % CAPABILITY == front;
}
/**
* identify if queue is empty
* @return
*/
public boolean isEmpty() {
return rear == front;
}
/**
* put element into queue.
* @param data data
* @return <code>true</code> if success
*/
public boolean enQueue(T data) {
if (!this.isFull()) {
elements[rear] = data;
rear++;
return true;
}
return false;
}
/**
* pull element from queue
* @return data
*/
public T deQueue() {
if(!this.isEmpty()) {
T result = elements[front];
front++;
return result;
}
return null;
}
public int getSize() {
return (rear - front + CAPABILITY) % CAPABILITY;
}
public static void main(String[] args) {
CircularQueue<String> queue = new CircularQueue<>();
queue.enQueue("a");
queue.enQueue("b");
queue.enQueue("c");
queue.enQueue("d");
queue.enQueue("e");
queue.enQueue("f");
System.out.println(queue.enQueue("g"));
System.out.println(queue.deQueue());
System.out.println(queue.enQueue("g"));
System.out.println(queue.deQueue());
System.out.println(queue.getSize());
}
}
