This article has been included in my Github Algorithm Diagrams series: github.com/vipstone/al…
Earlier, we introduced the Stack. Queues and stacks are similar data structures. We can imagine that a lot of cars are passing through a one-way tunnel, and all cars cannot cut in line or turn around, and the cars coming in first go out first. We can call this data structure a queue.
Queue feature
The elements In a queue must be First In First Out (FIFO), which has two important methods: enqueue and dequeue. The entrance end of the queue is called rear, and the exit end is called front, as shown below:
Hand rolled queue
Now that we’ve learned the basics of queues, we’ll use code to implement a queue.
Let’s start by implementing a queue using an array. Its structure is shown in the following figure:
1. Customize queues – Arrays
public class MyQueue<E> {
private Object[] queue; // Storage container
private int head; // header pointer
private int tail; // end pointer
private int size; // The actual storage length of the queue
private int maxSize; // Maximum capacity
public MyQueue(a) {
// No argument constructor, set default arguments
this.maxSize = 10;
this.head = 0;
this.tail = -1;
this.size = 0;
this.queue = new Object[this.maxSize];
}
public MyQueue(int initSize) {
// Take the argument constructor to set the argument
this.maxSize = initSize;
this.head = 0;
this.tail = -1;
this.size = 0;
this.queue = new Object[this.maxSize];
}
/** * query the header element */
public E peek(a) throws Exception {
if (size == 0) {
throw new Exception("No data currently in queue.");
}
return (E) this.queue[this.head];
}
/** * enter */
public boolean offer(E e) throws Exception {
if (tail >= (maxSize - 1)) {
throw new Exception("Add failed, queue is full");
}
this.queue[++tail] = e;
size++;
return true;
}
/** ** out */
public E poll(a) throws Exception {
if (size == 0) {
throw new Exception("Deletion failed, queue empty");
}
size--;
return (E) this.queue[head++];
}
/** * code test */
public static void main(String[] args) throws Exception {
MyQueue queue = new MyQueue();
queue.offer("Hello");
queue.offer("Java"); System.out.println(queue.peek()); queue.poll(); System.out.println(queue.poll()); }}Copy the codeThe result of the above code is as follows:
Hello
Java
2. Custom queues – Linked lists
The data structure for implementing queues with linked lists is shown below:
The implementation code is as follows:
public class QueueByLinked {
/** * declare the linked list node */
static class Node<E> {
E item; // The current value
Node<E> next; // Next node
Node(E e) {
this.item = e; }}private Node firstNode; // Team head element
private Node lastNode; // Last element of the team
private int size; // The actual number of queues stored
private int maxSize; // Maximum queue capacity
public QueueByLinked(int maxSize) {
if (maxSize <= 0) throw new RuntimeException("Maximum queue capacity cannot be empty.");
// Default initialization function
firstNode = lastNode = new Node(null);
this.size = 0;
this.maxSize = maxSize;
}
/** * Check whether the queue is empty */
public boolean isEmpty(a) {
return size == 0;
}
/** * enter */
public void offer(Object e) {
// maximum effect
if (maxSize <= size) throw new RuntimeException("Queue full");
Node node = new Node(e);
lastNode = lastNode.next = node; // Set next for the last and penultimate node
size++; // Number of queues +1
}
/** ** out */
public Node poll(a) {
if (isEmpty()) throw new RuntimeException("Queue empty");
size--; // Number of queues -1
return firstNode = firstNode.next; // Set and return the header element (the first Node is null, the current element is Node.next)
}
/** * query the header element */
public Node peek(a) {
if (isEmpty()) throw new RuntimeException("Queue empty");
return firstNode.next; // Return the header element (the first Node is null, the current element is Node.next)
}
/** * code test */
public static void main(String[] args) {
QueueByLinked queue = new QueueByLinked(10);
queue.offer("Hello");
queue.offer("JDK");
queue.offer("Java"); System.out.println(queue.poll().item); System.out.println(queue.poll().item); System.out.println(queue.poll().item); }}Copy the codeThe result of the above code is as follows:
Hello
JDK
Java
3. Extension: Implement custom queues using lists
In addition to the above two methods, we can also use Java’s own data structure to implement queues, such as List, we provide an idea for implementation (but not recommended in the actual work), the implementation code is as follows:
import java.util.ArrayList;
import java.util.List;
/** * Custom queue (List mode) */
public class QueueByList<E> {
private List value; // Queue storage container
public QueueByList(a) {
/ / initialization
value = new ArrayList();
}
/** * Check whether the queue is empty */
public boolean isEmpty(a) {
return value.size() == 0;
}
/** * enter */
public void offer(Object e) {
value.add(e);
}
/** ** out */
public E poll(a) {
if (isEmpty()) throw new RuntimeException("Queue empty");
E item = (E) value.get(0);
value.remove(0);
return item;
}
/** * query the header element */
public E peek(a) {
if (isEmpty()) throw new RuntimeException("Queue empty");
return (E) value.get(0);
}
/** * code test */
public static void main(String[] args) {
QueueByList queue = new QueueByList();
queue.offer("Hello");
queue.offer("JDK");
queue.offer("Java"); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); }}Copy the codeThe result of the above code is as follows:
Hello
JDK
Java
Queue Usage Scenarios
Common usage scenarios for queues are:
- Store tasks waiting to be queued in multiple threads;
- Store threads waiting to execute tasks in multithreaded fair locks;
- Task queues of common messaging middleware.
conclusion
As can be seen from the above three Queue implementation methods, any container can be used to implement a Queue, as long as the elements of the Queue are guaranteed first-in-first-out (FIFO), and the implementation class needs to include the four core methods of the Queue: A custom queue can be implemented by enlisting, exiting, checking whether the queue is empty, returning the header element, etc.
Finally, I leave you with a question: What are the types of queues? Leave a comment in the comments section, and I’ll answer in my next post. Welcome to follow me and make progress with you every day
Bonus: search the public account “Java Chinese Community” and send “interview” to receive the latest interview materials.