GitHub source code sharing
Project homepage: github.com/gozhuyinglo…
Source: github.com/gozhuyinglo…
1. Queue
A queue, like a stack, is a linear table with limited operations. The difference is that the insertion of the queue happens at one end, which we call rear; The deletion (extraction) takes place at the other end, which we call the front.
A queue is an ordered fiFI-first In First Out list with only two operations:
- Enqueue: Adds an element to the end of the queue
- Dequeue: Removes (retrieves) an element from the queue head
2. Array implementation of the queue
Just like stacks, each operation on a queue, linked list implementation or array implementation is given a fast running time. The list implementation of queues is simple and straightforward, and we will not cover it. Let’s discuss how to implement a queue using arrays.
To start with, we need to declare an array and maintain two Pointers:
- Head pointer: points to the position of the element to be listed
- Tail pointer: points to the storage location of the column to be added
As you can see, when you reach the end of the queue, you can’t add any new elements, and then the previous position is left empty.
We can join the array end to end to form a circular array, that is, when the pointer reaches the end of the array, it points back to the head of the array, as shown in the figure below.
A few things to note here:
- Empty queues can be determined by head == tail
- Head == tail + 1 To check whether the queue is full, head and tail cannot overlap. Head == (tail + 1) % capacity; head == (tail + 1) % capacity
- The actual size of the array should be: the specified size + 1
3. Code implementation
The following code is a queue using a ring array, so it is also called a ring queue. The capacity is as follows: The specified capacity is + 1. The initial value of head and T AIL is 0. Queue storage elements use generics, so you can manipulate any data type you want. Let’s look at the implementation:
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>(5);
System.out.printf("Header pointer: %s\t Tail pointer: %s\t Queue size: %s\t Capacity: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
System.out.println("Out of line: -->" + queue.get());
System.out.println("Team entry: 1 -->" + queue.add(1));
System.out.println("Enter team: 2 -->" + queue.add(2));
System.out.println("Enter team: 3 -->" + queue.add(3));
System.out.println("Enter team: 4 -->" + queue.add(4));
System.out.println("Enter team: 5 -->" + queue.add(5));
System.out.printf("Header pointer: %s\t Tail pointer: %s\t Queue size: %s\t Capacity: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
System.out.println("Out of line: -->" + queue.get());
System.out.println("Enter team: 6 -->" + queue.add(6));
System.out.printf("Header pointer: %s\t Tail pointer: %s\t Queue size: %s\t Capacity: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
System.out.println("Team entry: 7 -->" + queue.add(7));
System.out.println("Out of line: -->" + queue.get());
System.out.println("Out of line: -->" + queue.get());
System.out.printf("Header pointer: %s\t Tail pointer: %s\t Queue size: %s\t Capacity: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
System.out.println("Team entry: 8 -->" + queue.add(8));
System.out.println("Team entry: 9 -->" + queue.add(9));
System.out.printf("Header pointer: %s\t Tail pointer: %s\t Queue size: %s\t Capacity: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
System.out.println("Out of line: -->" + queue.get());
System.out.println("Out of line: -->" + queue.get());
System.out.println("Out of line: -->" + queue.get());
System.out.println("Out of line: -->" + queue.get());
System.out.println("Out of line: -->" + queue.get());
System.out.printf("Header pointer: %s\t Tail pointer: %s\t Queue size: %s\t Capacity: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
System.out.println("Enter team: 10 -->" + queue.add(10));
System.out.printf("Header pointer: %s\t Tail pointer: %s\t Queue size: %s\t Capacity: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
}
private static class ArrayQueue<T> {
private final T[] queue; // Store queue data elements
private final int capacity; / / capacity
private int head = 0; // a header pointer to the header element
private int tail = 0; // A tail pointer to the storage location of the next element to be queued
public ArrayQueue(int capacity) {
this.capacity = capacity + 1; // The ring queue needs to be empty so that head and tail do not overlap when the queue is full
this.queue = (T[]) new Object[this.capacity];
}
/** * adds an element ** to the queue@param data
* @return* /
public boolean add(T data) {
// Queue full, add failed
if (isFull()) {
return false;
}
// tail points to the location where the next element to be queued will be stored, so the pointer is incremented by 1
queue[tail] = data;
// Ring arrays require modulo operations
tail = (tail + 1) % capacity;
return true;
}
/** * retrieves an element ** from the queue@return* /
public T get(a) {
if (isEmpty()) {
return null;
}
// Head refers to the position of the header element, so it is fetched first and then incremented by 1
T data = queue[head];
// Ring arrays require modulo operations
head = (head + 1) % capacity;
return data;
}
/** * Current queue size **@return* /
public int size(a) {
int size = tail - head;
if (size < 0) {
size += capacity;
}
return size;
}
/** * queue empty: When tail and head point to the same position, the queue is empty **@return* /
public boolean isEmpty(a) {
return tail == head;
}
/** * if the queue is full: tail needs to be incresed by 1 because a slot is reserved; Circular queue requires modular operation * *@return* /
public boolean isFull(a) {
return head == (tail + 1) % capacity; }}}Copy the codeOutput result:
Header pointer: 0 Tail pointer: 0 Queue size: 0 Capacity: 6 Out: --> NULL Join in: 1 --> True Join in: 2 --> True Join in: 3 --> True Join in: 4 --> True Join in: 5 --> true Header pointer: 0 tail pointer: 5 Queue size: 5 Capacity: 6 Queue size: --> 1 Queue size: 6 --> true Head pointer: 1 Tail pointer: 0 Queue size: 5 Capacity: 6 Queue size: 7 --> false Queue size: --> 2 Queue size: --> 3 Head pointer: 3 Tail pointer: 0 Queue size: 3 Capacity: 6 Queue entry: 8 --> true Queue entry: 9 --> true Header pointer: 3 Tail pointer: 2 Queue size: 5 Capacity: 6 out: --> 4 out: --> 5 out: --> 6 out: --> 8 out: --> 9 Head pointer: 2 Tail pointer: 2 Queue size: 0 Capacity: 6 In: 10 --> true Head pointer: 2 Tail pointer: 3 Queue size: 1 Capacity: 6Copy the codeGet more content
Wechat search: code nong StayUp
Personal homepage: GoZhuyinglong.github. IO