A queue is an abstract data structure with a first-in, first-out (FIFO) policy. That is, the data elements of the most advanced queue are also first out of the queue. The queue is the same as we queue to buy a ticket, the first to queue must buy a ticket, and then the queue to buy a ticket. The queue is shown below:
Queues have two important concepts, one called head and one called tail, where the head points to the first element and the tail points to the last element. Queues, like stacks, are restricted in access, so queues have only two main operations: enqueue and dequeue. The join operation adds an element to the end of the queue, and the exit operation takes an element from the head of the queue.
The bottom of the queue can be realized with an array and a linked list. The queue based on an array is called a sequential queue, and the queue based on a linked list is called a linked queue. Below, we respectively use an array and a linked list to simply realize these two queues.
Array-based queues
In this article, we use head to point to the head of the queue, and tail to point to the tail of the queue. This will be used by default in the following examples. I will explain the special points, but first let’s look at the queue entry and queue exit.
As can be seen in the figure, when entering the team, the tail of the team moves back, the head of the team remains unchanged, the head of the team is moved back, the tail of the team remains unchanged. The logic for joining and leaving the queue is fairly simple. If you are wondering why the queue head is moving backwards when exiting the queue, instead of pointing to the array with subscript 0 all the way through, you may be wondering why the queue head is moving backwards when exiting the queue. Why is that? If we keep the team head always point to the location of the array subscript is 0, that every time the team after the operation, the data behind the need to move forward one, in other words each time a team operation requires data migration, and data migration is larger, the price of each data migration time complexity is O (n), which can greatly affect the use of the queue performance. If we exit the queue by moving the head back one bit, we avoid migrating data every time we exit the queue. We only migrate data once when tail is equal to the size of the array and head is not equal to 0, and the space left by the queue is used for joining the queue. The following figure shows the data migration process:
During data migration, the data starting from the head position must be moved to the front of the head position, so that the space after leaving the queue can be used by subsequent queue operations.
Array-based queue implementation code:
Public class ArrayQueue {private String[] items; Private int size = 0; Private int head = 0; Private int tail = 0; Public ArrayQueue(int size){this.size = size; items = new String[size]; } /** * join the queue operation * @param data * @returnPublic int enQueue (String data){tail = size,head = 0, */ tail = size,head = 0, */if (tail == size && head == 0) return- 1; /** * if tail = size, but head! If = 0, data has been deleted, the queue is not full, and data migration is required */if(tail == size){// All data after the head need to migrate the head bit forwardfor(int i= head; i< size; i++){ items[i-head] = items[i]; } // move the last element head bit tail -=head; // head = 0; } // Add items[tail] = data; tail++;return1; } /** * queue operation * @return
*/
public String dequeue(){// The queue is empty when the first and last elements are equalif (head == tail) returnnull; String result = items[head]; // The first element is moved back one time. The advantage of this is that no data migration is required on exit.returnresult; }}Copy the codeChain queue
Chained queues are much easier to implement than sequential queues. Let’s take a look at the chained queue entry and exit operations:
tail
next
tail
head
head.next
Queue implementation code based on linked list
/** * list based queue */
public class LinkQueue {
// Point to the head of the queue
private Node head;
// point to the end of the queue
private Node tail;
/** * queue operation *@param data
* @return* /
public int enqueue(String data){
Node node = new Node(data,null);
// Determine if there are any elements in the queue
if (tail == null) {
tail = node;
head = node;
}else {
tail.next = node;
tail = node;
}
return 1;
}
/** * queue operation *@return* /
public String dequeue(a){
if (head==null) return null;
String data = head.data;
head = head.next;
// If there is no element in the queue, tail should also be null
if (head == null){
tail = null;
}
return data;
}
class Node{
private String data;
private Node next;
public Node(String data,Node node){
this.data = data; next = node; }}}Copy the codeCircular queue
Circular queue is a queue in order to improve, because the order queue inevitable data migration, data migration operation to cause a decline in the performance of the queue, in order to avoid this problem, will queue into a cycle, when the tail reach of the array subscript biggest refers to back in the location of the array subscript is 0, thus avoiding the data migration. Let’s take a look at the dequeueing and dequeueing operations of the circular queue:
tail
head
1
tail
head
1
tail
head
n
n-1
tail==head
Circular queue implementation code
/** * Ring queue, no data migration, improve performance */
public class CircularQueue {
// An array of data
private String[] items;
// Size of the container
private int size = 0;
// The first node
private int head = 0;
// The last node
private int tail = 0;
// constructor
public CircularQueue(int size){
this.size = size;
items = new String[size];
}
/** * queue operation *@param data
* @return* /
public int enqueue(String data){
/** * (tail+1) = head */
if ((tail+1)%size == head) return -1;
// Add elements to the queue
items[tail] = data;
// This is the remainder of the array length
tail= (tail+1)%size;
return 1;
}
/** * queue operation *@return* /
public String dequeue(a){
// The queue is empty when the first and last elements are equal
if (head == tail) return null;
String result = items[head];
// This is the remainder of the array length
head = (head+1)% size ;
returnresult; }}Copy the codedeque
Double-ended queue is a queue in which both the head and tail of the queue can be in and out of the queue. Double-ended queue uses a two-way linked list to achieve this. First, let’s take a look at the operations of double-ended queue in and out of the queue:
Can see from the dynamic figure, every end is a deque stack, conform to the characteristics of advanced stack out after, if we ban on deque team head team and the limitation of the next morning the team operation, deque and becomes a chain queue, deque is a kind of multi-functional data structure, we can use it to provide queue and stack two functions.
Double – ended queue implementation code
/** * double-ended queue, using bidirectional linked list implementation */
public class DoubleEndsQueue {
private static class Node {
String item;
Node next;
Node prev;
Node(Node prev, String element, Node next) {
this.item = element;
this.next = next;
this.prev = prev; }}// The first node
private Node first;
// The last node
private Node last;
/* * join the queue before the first node */
public void enqueueFirst(String e) {
final Node f = first;
final Node newNode = new Node(null, e, f);
// The first node points to the new node
first = newNode;
if (f == null)
// The last node also points to that node
last = newNode;
else
// The former node of the current node points to the new node
f.prev = newNode;
}
/** * join after the last element *@param e
*/
public void enqueueLast(String e) {
final Node l = last;
final Node newNode = new Node(l, e, null);
// The last node points to the new node
last = newNode;
if (l == null)
// The first node points to the new node
first = newNode;
else
// The next node of the current node points to the new node
l.next = newNode;
}
/** * exits from the first node *@return* /
public String dequeueFirst(a) {
if (first == null) return null;
final Node f = first;
String element = f.item;
Node next = f.next;
f.item = null;
f.next = null;
// The first node points to the next node of the leading node
first = next;
if (next == null)
// Indicates that the queue is empty
last = null;
else
next.prev = null;
return element;
}
/** * exit queue from last node *@return* /
public String dequeueLast(a) {
final Node l = last;
if (last == null) return null;
String element = l.item;
Node prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
return element;
}
// Outputs the entire contents of the queue
public void displayAll(a) {
while(first ! =null){
System.out.print(first.item+"");
first = first.next;
}
System.out.println("= = = = = = = = = = = = = = ="); }}Copy the codePriority queue
Priority queue is a kind of don’t have to follow the queue first in first out (FIFO) characteristics of a special queue, priority queue with the average queue as only one head and one of the team and also from the teams head out of the team, of the team, but in the priority queue, with each team, will be carried out in accordance with the team the key value of a data item order (from big to small, since the childhood, This ensures that the item with the smallest or largest keyword is always at the head of the queue, and the item with the highest priority is the first to go out of the queue. This is just like our hospital treatment, emergency patients are treated before ordinary patients. Let’s take a look at the priority queue dequeueing and joining operations:
In our example, we specify that a smaller value has a higher priority. Each time we perform the join operation, the smaller element moves closer to the leader, and when we leave the team, the smaller element moves first.
Priority queue code implementation
The main reason for implementing priority queues is to better understand the idea of priority queues. Priority queues are typically implemented using a heap because array implementations are expensive to sort data at insert time.
/** * Priority queue */
public class PriorityQueue {
// An array of data
private Integer[] items;
// Size of the container
private int size = 0;
// The first node
private int head = 0;
// constructor
public PriorityQueue(int size){
this.size = size;
items = new Integer[size];
}
/** * queue operation *@param data
* @return* /
public int enqueue(Integer data){
int j;
if (head == 0){
items[head++] = data;
}
else {
for (j=head-1; j>=0; j--){// Put the smaller number back
if (data > items[j]){
items[j+1] = items[j];
}else {
break;
}
}
items[j+1] = data;
head++;
}
return 1;
}
public Integer dequeue(a){
returnitems[--head]; }}Copy the codeconclusion
- A queue is a data structure that follows a first-in, first-out (FIFO)
- Queues can be implemented using arrays, called sequential queues, and linked lists, called linked queues
- Circular queue solves the problem of performance loss caused by sequential queue data migration
- A two-end queue is a queue in which both the head and tail of a queue can enter or leave the queue
- A priority queue is a queue that does not follow the first-in, first-out rule. When any element is added, the one with the highest priority is placed at the head of the queue
The last
Play a small advertisement, welcome to scan the code to pay attention to the wechat public number: “The technical blog of the flathead brother”, progress together.
