A queue is also a linear data structure with restricted operations, much like a stack.
01Definitions
Stacks are restricted in that only element insertions are allowed at one end of the queue, and only deletions are allowed at the other end of the queue. This property can be summarized as First In First Out (FIFO). This means that the first element added to the queue will be the first to be removed.
join a team: The act of adding a new element to a queue is called queue entry;
go out of bounds: The act of removing an element from a queue is called queue-out;
team leader: The end of the queue where the element removal behavior is allowed is called the head of the queue;
back of the line: The end of the queue where the behavior of performing element additions is run is called the tail of the queue;
empty queue: When there are no elements in the queue it is called an empty queue.
full queue: When a queue is of finite capacity and the capacity is exhausted, it is called a full queue.
queue capacity: When the queue is of finite capacity, the queue capacity indicates the maximum number of elements that the queue can hold.
Queue size: Indicates the number of elements in the current queue.
02Classification
There are two ways to categorize queues based on how they are stored and their functional characteristics.
1、Classified according to the way of storage
Queues are logical structures, so they can be categorized into sequential and chained queues depending on how they are stored.
Sequential queue is all the queue elements are stored in a continuous address space, so you can implement sequential queue through the array, because the characteristics of the array also leads to sequential queue capacity is fixed, not easy to expand, which also leads to easy to waste space, but also pay attention to the elements of the overflow and other issues.
Chained queues, as the name suggests, are stored in a chained fashion, which can be realized through a linked table, so chained queues can be infinitely expandable, greatly improving memory utilization.
2、Classified according to functional characteristics
There are many proprietary queues that can be categorized according to their functional characteristics, and we list a few below for a brief introduction.
blocking queue: It blocks outgoing operations when the queue is empty and incoming operations when the queue is full.
priority queue: Each element in a queue has a priority level attribute, and the queuing operation of an element depends on this priority level attribute, i.e., a high priority level gives priority to queuing.
Delay Queue: Each element in the queue is marked with a time record, and the element will trigger an out-of-queue operation only after the specified delay time.
recurring queue: When using arrays to realize the queue, you can connect the head of the queue and the tail of the queue, that is, when the tail of the queue to reach the end of the array can be "circled back" to the beginning of the array, through this clever design to improve the utilization of the array space.
double-ended queue: It is a data structure that allows queue-in and queue-out operations at both ends.
Depending on these queue characteristics, they can have unexpected effects in different scenarios.
Below we will explain the implementation of sequential queues and chained queues in detail.
03, implementation (sequential queue)
Below we implement sequential queuing with the help of arrays, the core idea is to take the starting position of the array as the queue head and the direction of the end of the array as the queue tail. When the out-of-queue behavior occurs, you need to move all the remaining data to the head of the queue direction one, why do this step?
First of all, the sequential queue inside the array, assuming that the array can store 7 elements, at this time, the array has been full, so you can not add new elements into the queue operation, and then we head of the array elements out of the queue operation, at this time, the array because of out of the queue will leave an empty space, the following chart.
So is it possible to perform a queue entry operation at this point? We are told that we should be able to, because there is already space at the head of the array. However, we have agreed that the queue can only be queued from the end of the array, and at this point there is no empty space at the end of the array for the newly queued element, so it is not actually possible to perform a queuing operation.
How to deal with it? The simplest way is that when an out-of-queue operation occurs, all the elements behind it move one place toward the head of the queue, leaving the end of the queue empty by one place, and this can be entered into one element for every element that is out of the queue.
Of course, this is not the only solution, or through the circular queue to solve this problem, interested can study.
1. Definition of ADT
Let's first define the ADT for sequential queues.
ADT Queue{
Data object: D is a non-empty collection of elements, D = {a1, a2, ... , an}, where ai denotes the ith element in the queue and n is the length of the queue.
Data Relationships: The elements in D are organized by their indexes (positions), which are integers from 0 to n-1 and follow the principle of first-in-first-out of elements.
Basic operations: [
Init(n) : Initialize an empty queue of specified capacity.
Capacity: return the capacity of the queue.
Length: returns the length of the queue.
Head: return the head element of the queue, when the queue is empty, then report an exception.
Tail: return to the end of the queue, when the queue is empty, then report an exception.
IsEmpty(): return whether the queue is empty.
IsFull(): return whether the queue is full.
Enqueue(): add elements to the queue, when the queue is full, then report an exception.
Dequeue(): out of the queue that is, return to the head of the queue and remove it from the queue, when the queue is empty, then report an exception.
]
}
With the queue ADT defined, we can now start our own implementation of the queue.
2、Initialization Init
First define 3 variables to hold the array of queue elements, the capacity of the queue, and the end-of-queue index, and do not define the header index because the header index is always equal to zero.
Initializing a structure does a few things.
-
Initializes the capacity of the queue;
-
Initialize the array holding the queue elements;
-
Initialize the end-of-queue index;
The specific implementation code is as follows:
//store the queue elements
private T[] _array;
//capacity of the queue
private int _capacity;
//The index of the tail of the queue, -1 means an empty queue
private int _tail; //Initialize the queue to the specified capacity.
//Initialize the queue to the specified capacity
public MyselfQueueArray<T> Init(int capacity)
{
//Initialize the queue to capacity.
_capacity = capacity;
// Initialize an array of the specified length to hold the queue elements.
_array = new T[_capacity]; //initialize array of specified length to hold the queue elements
_tail = -1; // Return to the queue.
// Return the queue
return this; //Initialize an array of the specified length to hold the queue elements.
}
3、Get queue capacity Capacity
It's easier to just return the queue capacity private field.
//queue capacity
public int Capacity
{
get
{
return _capacity;
}
}
4. Get the length of the queue Length
We do not define the queue length of the private field, because the end of the queue index that is the last element of the array index, which can represent the length of the queue, so just use the end of the queue index plus 1 to get the length of the queue, at the same time you need to pay attention to determine whether the queue is empty, if it is empty, then the error.
//queue length
public int Length
{
get
if (IsEmpty())
if (IsEmpty())
if (IsEmpty())
return 0; }
}
// The length of the queue is equal to the tail index plus 1.
return _tail + 1; }
}
}
5、Get the head element Head
Based on our convention above, the queue head element always corresponds to the first element of the array, so you can directly fetch the array element with index 0. An empty queue will report an error. The specific code is as follows:
//Get the head element of the queue
public T Head
{
get
{
if (IsEmpty())
{
// Empty queue, do not fetch header elements.
throw new InvalidOperationException("Empty Queue");
}
return _array[0];
}
}
6, get the end of the queue element Tail
Because we defined the end-of-queue index private variable, we can get it directly through the end-of-queue index. The specific code is as follows:
//Get the last element of the queue
public T Tail
{
get
If (IsEmpty())
if (IsEmpty())
{
// Empty queue, do not fetch header elements.
throw new InvalidOperationException("Empty Queue");
}
return _array[_tail];
}
}
7, get whether the empty queue IsEmpty
Whether or not the queue is empty is simply a matter of determining whether or not the index at the end of the queue is less than 0.
//whether empty queue
public bool IsEmpty()
{
//Tail index less than 0 means empty queue
return _tail < 0; }
}
8, get whether the full queue IsFull
Whether the queue is full only to determine whether the index of the end of the queue is equal to the queue capacity minus 1, the code is as follows:
//Is the queue full
public bool IsFull()
{
//The head of the queue index is equal to the size of the capacity minus 1 indicates that the full queue
return _tail == _capacity - 1;
}
9. Enqueue
Into the queue only to add a new element to the end of the array inside the queue can be, so first of all, the end of the queue index has to move a successive one, and then assign the new element to the end of the queue elements, but also need to check whether the queue is full, if it is a full queue is reported as an error, the specific implementation of the code is as follows:
//Enqueue
public void Enqueue(T value)
{
if (IsFull())
{
//The queue is full, no queue entry operation is allowed.
throw new InvalidOperationException("Full Queue");
}
//The index of the tail of the queue is shifted back by 1 bit
_tail++.
//Assign a new value to the tail element of the queue.
_array[_tail] = value.
}
10. Dequeue
Getting out of the team is then roughly divided into the following steps:
-
Determines if the queue is empty, and reports an error if it is empty;
-
Removes the queue header element for temporary storage and resets the queue header element to its default value;
-
Moves all elements behind the head of the queue one place toward the head of the queue;
-
Resets the end-of-queue element to its default value;
-
The end-of-queue index is moved one place toward the head of the queue, i.e., the end-of-queue index is decremented by one;
-
Returns the temporary header element of the queue;
The specific implementation code is as follows:
//out of the queue
public T Dequeue()
{
if (IsEmpty())
{
//Empty queue, no out-of-queue operation is allowed
throw new InvalidOperationException("Empty queue");
}
// Remove the head element of the queue
var value = _array[0]; //Reset the head element to _array[0].
// Reset the header element to its default value
_array[0] = default;
//All elements after the head element are moved one place to the head of the queue
for (int i = 0; i < _tail; i++)
{
_array[i] = _array[i + 1];
}
// the tail element of the queue is reset to its default value
_array[_tail] = default;
//The tail index is moved one place toward the head of the queue
_tail--;
//Return the head element
return value; }
}
04, implementation (chained queues)
We implement a chained queue with the help of a linked table, the core idea of which is to use the tail node of the linked table as the tail of the queue and the first element node of the linked table as the head of the queue.
1. Definition of ADT
Compared to the ADT with sequential queue, the ADT with chained queue has two less methods i.e. getting the queue capacity and whether the queue is full or not, which is a benefit of the chained table feature.
2、Initialization Init
First you need to define the chain list node class, containing two attribute data fields and a pointer field.
Then 3 variables need to be defined for storing the queue head node, the queue tail node, and the queue length.
And the initialization structure mainly initializes the initial values of 3 variables, which are implemented as follows:
public class MyselfQueueNode<T>
{
//Data field
public T Data.
// pointer field, i.e. the next node
public MyselfQueueNode<T> Next; { // data field, i.e. next node
public MyselfQueueNode(T data)
{
Next = null; public MyselfQueueNode(T) { Data = data.
Next = null;
}
}
public class MyselfQueueLinkedList<T>
{
//Team head node i.e. primitive node
private MyselfQueueNode<T> _head;
//The end node of the queue i.e. the tail node
private MyselfQueueNode<T> _tail;
//The length of the queue
private int _length;
//Initialize the queue
public MyselfQueueLinkedList<T> Init()
{
//Initialize the queue head node to null
_head = null;
//Initialize the tail node to null
_tail = null;
//initialize queue length to 0
_length = 0;
// Return the queue
return this; //Initialize queue length to 0; //Return queue.
}
}
3. Get the length of the queue Length
It's easier to just return the queue length as a private field.
//Queue length
public int Length
{
get
{
return _length;
}
}
4、Get the head element Head
Get queue head elements can be returned directly through the queue head node data field, but pay attention to determine whether the queue is an empty queue, if it is an empty queue will report an exception. Specific code is as follows:
//Get the head element of the queue
public T Head
{
get
{
if (IsEmpty())
{
// Empty queue, do not fetch header elements.
throw new InvalidOperationException("Empty Queue");
}
// Return the data field of the queue head node
return _head.Data; }
}
}
5、Get the last element of the queue Tail
Get the end of the queue elements can be returned directly through the end of the queue node data field, but pay attention to the empty stack is reported as an exception. The specific code is as follows:
//Get the last element of the queue
public T Tail
{
get
If (IsEmpty())
if (IsEmpty())
{
// Empty queue, do not fetch the end of the queue.
throw new InvalidOperationException("Empty Queue");
}
// Return the data field of the tail node
return _tail.Data; }
}
}
6, get whether the empty queue IsEmpty
Whether the queue is empty is simply a matter of determining whether both the head node and the tail node are empty.
//whether the empty queue
public bool IsEmpty()
{
//The head node is null and the tail node are empty means empty queue
return _head == null && _tail == null;
}
7. Enqueue
Joining the team is roughly divided into the following steps:
-
A new node needs to be created first;
-
If the original end-of-queue node is not empty, point the original end-of-queue node pointer field to the new node;
-
Update the original end-of-queue node to a new node;
-
If the head node is empty, it means that this is the first element, so both the head and tail are the same node, so assign the tail node to the head node;
-
The queue length is added to 1;
The specific implementation code is as follows:
//Enqueue
public void Enqueue(T value)
{
// Create a new node at the end of the queue
var node = new MyselfQueueNode<T>(value);
// If the tail node is not empty, attach the new tail node after the tail node
if (_tail ! = null)
{
_tail.Next = node;
}
//Tail node changed to new tail node
_tail = node;
//If the head node is null, assign it as the tail node
if (_head == null)
{
_head = _tail;
}
// add 1 to the length of the queue
_length++; }
}
8, out of the team Dequeue
Getting out of the team is then roughly divided into the following steps:
-
Determines if the queue is empty, and reports an error if it is empty;
-
Get queue head node data field staging;
-
Update the head node to be the next node corresponding to the original team head node;
-
If the head node is empty, it means it is an empty queue, and the tail node should also be empty;
-
The queue length is reduced by 1;
-
Returns the temporarily stored queue head node data;
The specific implementation code is as follows:
//out of the queue
public T Dequeue()
{
if (IsEmpty())
{
//Empty queue, no out-of-queue operation is allowed
throw new InvalidOperationException("Empty Queue");
}
// Get the data of the head node of the queue
var data = _head.Data;
// Change the head node to the next node corresponding to the original head node
_head = _head.Next; //change the queue head node to the next node corresponding to the original queue head node
//If the queue is empty, indicate that it is empty and update the end of the queue to be null
if (_head == null)
{
_tail = null;
}
// Reduce the length of the queue by 1
_length--; // Return the queue head node data.
// Return the data of the head node of the queue
return data; }
}
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner