“This is the 15th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.
A queue is a linear list that allows only inserts at one end and deletes at the other. This paper introduces the characteristics of queues in detail, and implements queues based on sequential structure and chain structure using Java language respectively.
1 Overview of queues
A queue is a linear list that allows only inserts at one end and deletes at the other. Queues work exactly like queues in real life. Suppose you are standing in line with your friend at a bus stop. If you are ahead of him in line, you will get on the bus first, and the person behind will line up behind your friend. Queues work in the same way.
A queue is a First In First Out linear table, or FIFO for short. The end that allows insertion is called the tail, and the end that allows deletion is called the head. Suppose the queue is q=(A1,a2,…… ,an), so A1 is the head element and an is the tail element. So we can always start at A1 when we delete, and last when we insert.
Because queues are linear tables, they can also be implemented using sequential and chained storage structures. Java already provides implementations of many thread queues, such as the various blocking and non-blocking queues in JUC. In a production environment, message queues such as Kafka use the most basic queuing features underneath. Queues are used more often than stacks.
For information on the data structure of the Java Stack, see this article: Data Structures – Stack principles and Java implementation and postfix expression operations.
2 queue sequential storage structure implementation
2.1 Overview of the sequential storage structure of queues
Unlike a stack, queues are enqueued and unqueued at different ends. If the queue head is at the maximum index of the array element, then the queuing is to add the element to the index after the maximum index, without moving the element, and the time complexity is O(1). But the exit queue is going to be at the head of the array, and it’s going to move all the elements in order n time. If the queue head is at the starting index of the array element, the time to queue is faster, but the time to queue is O(n) again.
Therefore, we need to be flexible in dealing with heads or tails. Instead of being fixed at the start or maximum index of the array, it should be variable. In this case, we need to add external Pointers to hold “head” and “tail”. When manipulating data, you only need to manipulate the head and tail of the queue, so that the time complexity of joining and leaving the queue is O(1).
According to the above practice, team head and team tail is not fixed, team and team operation is really very convenient. However, it may cause index overflow and memory waste, as shown below:
May appear on the graph, team head is moved to the center of the array, and because of the added elements, moved to an array of tail, if team again, at this time due to the overflow will throw ArrayIndexOutOfBoundsException array index, but the first half of the space did not use an array, This is a waste of space.
This type of overflow is called a “false overflow”. The way to fake overflow is when the back is full, you start all over again, which is head to tail. We call the sequential storage structure of the queue, head to tail, a circular queue.
Circular queue solves the problem of false overflow, and the queue entry and queue exit time are O(1) at the same time. The only thing to worry about is the limited size of the array.
2.2 Simple implementation of array loop queue
/** * array implementation loop queue, for convenience, here the underlying array design is not extensible */
public class MyArrayLoopQueue<E> {
/ * * * chain is realized by using an array of storage * /
private final Object[] elements;
/** * Capacity */
private final int capacity;
/** * queue header element index */
private int first;
/** * end of the queue element index */
private int end;
/** * Number of elements */
private int size;
/** * constructor initializes array **@param* / capacity capacity
public MyArrayLoopQueue(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
}
/** * join the team, element added at the end of the team **@paramElement The added element *@returnReturn true on success, false */ on failure
public boolean add(E element) {
// If the queue capacity is full. False is returned when adding fails
if (size == capacity) {
return false;
}
if (size == 0) {
/* If the element is placed for the first time, both the header and the tail point to the element at index 0 */
elements[end] = element;
} else if (end + 1 == capacity) {
/* If end + 1 = capacity, the end of the queue is used up, and the end index is set to 0
end = 0;
elements[end] = element;
} else {
/* Otherwise, the index at the end of the queue normally increments */
elements[++end] = element;
}
/ / the size on the 1
size++;
return true;
}
/** * delete the header element **@returnRemoved element, or NULL */
public E remove(a) {
// Whether the queue is empty
if (size == 0) {
/ / returns null
return null;
}
Object o = elements[first];
// Remove the header element
elements[first] = null;
// If the queue header index equals capacity after +1, reset the queue header index, loop
if (++first == capacity) {
first = 0;
}
// If the queue is empty, reset the index of the head and tail of the queue
if (--size == 0) {
first = 0;
end = 0;
}
return (E) o;
}
/** * returns the number of queue elements **@return* /
public int size(a) {
return size;
}
/** * Clear the queue */
public void clear(a) {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
first = 0;
end = 0;
}
/** * overrides toString method **@return* /
@Override
public String toString(a) {
StringBuilder stringBuilder = new StringBuilder();
if (size == 0) {
stringBuilder.append("[]");
return stringBuilder.toString();
}
stringBuilder.append("[");
if (first < end) {
for (int i = first; i <= end; i++) {
stringBuilder.append(elements[i]);
if(i ! = end) { stringBuilder.append(","); }}}else if (size == 1) {
stringBuilder.append(elements[first]);
} else {
for (int i = first; i < capacity; i++) {
stringBuilder.append(elements[i]);
stringBuilder.append(",");
}
for (int i = 0; i <= end; i++) {
stringBuilder.append(elements[i]);
if(i ! = end) { stringBuilder.append(",");
}
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}
/** * enhances toString to test **@return* /
public String toStringPlus(a) {
StringBuilder stringBuilder = new StringBuilder();
if (size == 0) {
stringBuilder.append("[]");
stringBuilder.append("; first:").append(first).append("; end:").append(end).append("; size:").append(size);
return stringBuilder.toString();
}
stringBuilder.append("[");
if (first < end) {
for (int i = first; i <= end; i++) {
stringBuilder.append(elements[i]);
if(i ! = end) { stringBuilder.append(","); }}}else if (size == 1) {
stringBuilder.append(elements[first]);
} else {
for (int i = first; i < capacity; i++) {
stringBuilder.append(elements[i]);
stringBuilder.append(",");
}
for (int i = 0; i <= end; i++) {
stringBuilder.append(elements[i]);
if(i ! = end) { stringBuilder.append(",");
}
}
}
stringBuilder.append("]");
stringBuilder.append("; first:").append(first).append("; end:").append(end).append("; size:").append(size);
returnstringBuilder.toString(); }}Copy the code2.2.1 test
MyArrayLoopQueue<Object> objectMyArrayLoopQueue = new
MyArrayLoopQueue<>(4);
System.out.println("Team = = = = = = = = >");
objectMyArrayLoopQueue.add(11);
objectMyArrayLoopQueue.add(22);
objectMyArrayLoopQueue.add(33);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("A team = = = = = = = = >");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("A team = = = = = = = = >");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("Team = = = = = = = = >");
objectMyArrayLoopQueue.add(44);
objectMyArrayLoopQueue.add(55);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("Team = = = = = = = = >");
objectMyArrayLoopQueue.add(null);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("Team failed ========>");
boolean add = objectMyArrayLoopQueue.add(77);
System.out.println(add);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
Copy the codeQueue chain storage structure and implementation
3.1 Overview of queue chain storage structure
The chain storage structure of queue is actually a single linked list of linear lists, but it can only go in and out at the end, we call it chain queue for short. For ease of operation, the queue head pointer points to the head node of the chain queue, and the queue tail pointer points to the end node.
As you can see, implementing a queue using a chain structure is much simpler than implementing a sequential structure.
3.2 Simple implementation of queue chain storage structure
/** * a simple singly linked list implementation of a queued storage structure */
public class MySingleLinkedQueue<E> {
/** * empty constructor, internal nodes are not initialized, will be initialized at the first time added. * /
public MySingleLinkedQueue(a) {}/** * Number of elements */
private int size;
/** * a reference to the team header */
private Node<E> first;
/** * a reference to the end of the queue */
private Node<E> end;
/** * nodes within a single list */
private static class Node<E> {
// Reference to the next node
Node<E> next;
// Node data
E data;
// Node constructor
public Node(E data, Node<E> next) {
this.data = data;
this.next = next; }}/** * join the queue, add the element to the end of the list **@paramE The element to add */
public void add(E e) {
// Create a node
Node<E> newNode = new Node<>(e, null);
if(end ! =null) {
/* If the end is not empty */
end.next = newNode;
// Change the queue end node reference
end = newNode;
} else {
end = newNode;
first = newNode;
}
++size;
}
/** * delete the header element **@returnThe deleted element */
public E remove(a) {
// If the header is null, an exception is thrown
if (first == null) {
throw new NoSuchElementException("Queue is empty");
}
E e = first.data;
// Change the header node reference
first = first.next;
// If the element is 0, the last-node reference is null
if (--size == 0) {
end = null;
}
return e;
}
/** * gets the number of elements */
public int size(a) {
return size;
}
@Override
public String toString(a) {
StringBuilder stringBuilder = new StringBuilder();
if (size > 0) {
Node<E> f = first;
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(f.data);
if(i ! = size -1) {
stringBuilder.append(",");
}
f = f.next;
}
stringBuilder.append("]");
return stringBuilder.toString();
}
return "[]"; }}Copy the code3.2.1 test
MySingleLinkedQueue<Object> objectMySingleLinkedQueue = new
MySingleLinkedQueue<>();
System.out.println("Team = = = = = = = = >");
objectMySingleLinkedQueue.add(11);
objectMySingleLinkedQueue.add(22);
objectMySingleLinkedQueue.add(33);
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("A team = = = = = = = = >");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("A team = = = = = = = = >");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("Team = = = = = = = = >");
objectMySingleLinkedQueue.add(44);
objectMySingleLinkedQueue.add(55);
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("Team = = = = = = = = >");
objectMySingleLinkedQueue.add(null);
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("A team = = = = = = = = >");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("Abnormal queue ========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
Copy the code4 summarizes
This article introduces the basic concept of queues and provides a simple implementation. Queues belong to a special kind of linear table. “Data first comes first” is a very common idea, so the application range of queue is very wide, in fact, we can directly contact with queue applications are higher than stack applications, such as various concurrent queues, message queues. In addition, breadth-first search algorithms usually select the earliest data from the search candidates as the next vertex. At this point, queues can be used for the management of alternate vertices.
In addition, for more information about the data structure of the Java Stack, see this article: Data Structure – Stack principle and Java implementation and postfix expression operations.
Related articles:
- Big Talk Data Structure
- Diagram of algorithms
- My First Algorithm Book
If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!