How to implement queues
This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021
The author recently studied “The Beauty of Data Structures and Algorithms”, just take this opportunity to practice while recording their knowledge points. Today we have a queue.
What is a queue
- Queues, like stacks, are linear table data structures with limited operations. Queues only allow data to be added at one end and removed at the other, creating a first-in, first-out feature. Think of a queue as a ticket check-in line, where you can’t jump the queue. Those first in line pass through first, and those coming from behind get to the end of the line.
- The basic operations of a queue are similar to those of a stack, with push() and pop() being added to the stack. Similar queues also have two basic operations, enQueue () and deQueue().
Common types of queues
Queues can be implemented in two ways, one using arrays called sequential queues and the other using linked lists called chained queues.
2.1 Sequential Queue
Array queue implementation, first need to record the head index of the queue and tail index of the queue. The head position in the array is removed while the head is moved back one bit. Enqueue operations are similar, adding data to the array tail position and moving tail back one bit.
If all positions in the queue are full, no more data can be added. In this case, the user is told that adding data fails.
Second, the head of the queue is still free. In this case, data needs to be moved to the head of the queue and then new data needs to be added.
/ * * *@author xuls
* @date2021/11/20 21:45 * Array implements sequential queue */
public class ArrayQueue <T>{
// Store arrays
private Object[] dataArray;
/ / capacity
private int capacity;
// queue header index
private int head;
// End index
private int tail;
public ArrayQueue(int capacity) {
dataArray = new Object[capacity];
head=0;
tail=0;
this.capacity = capacity;
}
/ / team
public boolean enQueue(T data){
// If the tail index exceeds the maximum array length
if (tail == capacity){
// tail-head = capacity
if (head ==0) {return false;
}
// Data move
int length = tail - head;
for (int i = 0; i < length; i++) {
dataArray[i] = dataArray[head+i];
}
head=0;
tail=length;
}
// When joining the queue, tail ++ moves back one bit
dataArray[tail++]=data;
return true;
}
/ / out of the team
public T deQueue(a){
if (isEmpty()){
throw new IndexOutOfBoundsException("queue is empty");
}
// Head ++ moves back one position as you exit the queue
return (T)dataArray[head++];
}
public boolean isEmpty(a){
return head == tail;
}
@Override
public String toString(a) {
StringBuilder builder = new StringBuilder();
for (int i = head; i < tail; i++) {
builder.append(dataArray[i]).append(",");
}
return "ArrayQueue={"+builder.toString()+"}"; }}Copy the code2.2 Chain queue
Queues are implemented using linked lists, again with a head reference to the head of the queue and a tail reference to the tail. Next points to the new node and sets the new node to tail. Out of the queue set head. Next to head.
Here is the concrete implementation code:
/ * * *@author xuls
* @date2021/11/20 23:35 * Chain queue */
public class LinkedListQueue<T> {
private Node<T> head;
private Node<T> tail;
public LinkedListQueue(a) {
head=tail=null;
}
/ / team
public void enQueue(T data){
Node<T> node = new Node<>(data,null);
if (head == null){
head = tail =node;
}else{ tail.next = node; tail = node; }}/ / out of the team
public T deQueue(a){
if (head==null) {throw new IndexOutOfBoundsException("queue is empty");
}
T data = head.data;
head = head.next;
// Set tail to null when the queue is empty
if (isEmpty()){
tail = null;
}
return data;
}
public boolean isEmpty(a){
return head == null;
}
private class Node<T>{
private T data;
private Node<T> next;
public Node(T data, Node<T> next) {
this.data = data;
this.next = next; }}@Override
public String toString(a) {
StringBuilder builder = new StringBuilder();
Node<T> tempNode = head;
while(tempNode ! =null){
builder.append(tempNode.data).append(",");
tempNode = tempNode.next;
}
return "LinkedListQueue{"+builder.toString()+"}"; }}Copy the code2.3 Circular Queue
When implementing sequential queues, data movement may be required when a new data is added after the data has been added to the last position in the array. The circular queue can avoid the operation of data moving. The circular queue connects the head and tail of the queue together. The realization idea of the circular queue is basically the same as that of the sequential queue. Here are some examples of situations that you can try to generalize from.
Here is the concrete implementation code:
/ * * *@author xuls
* @date* Loop queue */
public class CircleQueue<T> {
private Object[] dataArray;
private int capacity;
private int head;
private int tail;
public CircleQueue(int capacity) {
dataArray = new Object[capacity];
this.capacity = capacity;
head=tail=0;
}
public boolean enQueue(T data){
if ((tail+1)%capacity == head){
return false;
}
dataArray[tail]=data;
// select module % to avoid array access out of bounds
tail = (tail+1) % capacity;
return true;
}
public T deQueue(a){
if (isEmpty()){
throw new IndexOutOfBoundsException("queue is empty");
}
T t = (T) dataArray[head];
// select module % to avoid array access out of bounds
head = (head+1) % capacity;
return t;
}
public boolean isEmpty(a){
return tail == head;
}
@Override
public String toString(a) {
StringBuilder builder = new StringBuilder();
int temp = head;
while(temp ! = tail){ builder.append(dataArray[temp]).append(",");
temp = (temp+1) % capacity;
}
return "CircleQueue={"+builder.toString()+"}"; }}Copy the codeThird, summary
- Queues are characterized by first in, first out.
- The basic operations on queues are enQueue() and deQueue().
- Arrays are called sequential queues, and linked lists are called linked queues. The data moving problem of sequential queue can be solved by circular queue. The biggest difference between circular queue and sequential queue is the judgment condition of queue full. Circular queue will waste a storage space.