“This is my fourth day of the November Gwen Challenge.The final text challenge in 2021”

A queue is a linear table in which additions or deletions can only be made at the end of the queue, and elements can only be added from the end of the queue (enQueue) and removed from the head (deQueue). So the characteristics of the queue can be summarized as First In First Out (FIFO).

Interface design according to the definition of queue is as follows:

function paraphrase
int size() Number of elements
boolean isEmpty() Whether is empty
void clear() empty
void enQueue(E element) The team
E dequeue() Out of the team
E front() Gets the header element of the queue
  • E is a generic type

implementation

Queues can be implemented as dynamic arrays or linked lists. Since queues can only operate at the head and tail, they can be encapsulated in a dynamic array or linked list, exposing the interface APIS that operate on the head or tail. It is recommended to choose the bidirectional linked list in favor of the operation of the head or tail.

Create a Queue and create a private list to store the data:

public class Queue<E> {
  private List<E> list = new LinkList<>();
}
Copy the code

The number of elements in the queue can be accessed directly from the list’s size() method:

int size() {
  return list.size();
}
Copy the code

To determine whether the queue has elements, you can also access the isEmpty() method of the list directly:

boolean isEmpty() {
  return list.isEmpty();
}
Copy the code

The queue can also be cleared directly using the list clear() method:

void clear() {
  list.clear();
}
Copy the code

Next, start implementing the three important methods of queues.

The first is the joining method, because joining is adding elements to the list from the end of the queue:

void enQueue(E element) {
  list.add(element);
}
Copy the code

Select * from list where index 0 is 0;

E deQueue() {
  return list.remove(0);
}
Copy the code

Fetching the header element is also equivalent to fetching the element whose index is 0:

E front() {
  return list.get(0);
}
Copy the code

At this point, you have implemented all interfaces to the queue. Now the queue is only from the end of the queue, from the head of the queue. So no matter the team head or team tail, can operate the team and team? A two-endian queue solves this problem.

Double-ended queue (Deque)

A double-endian queue is a queue that can be queued and queued at both ends. Therefore, related interfaces are added

function paraphrase
void enQueueRear(E element) Join from the back of the line
E deQueueFront() Go from the head of the team
void enQueueFront(E element) Go from the head of the team
E deQueueRear() Cut out from the back of the line
E front() Gets the header element of the queue
E rear() Gets the last element of the queue

Looking at the methods in the table, the header elements for queue entry, queue exit, and queue fetch are implemented above. Now you just need to implement the remaining three methods. The implementation method is also very simple.

Add an element to the list at the position where the index is 0:

void enQueueFront(E element) {
  list.add(0, element);
}
Copy the code

The next step is to remove the element from the last position in the list:

E deQueueRear() {
  return list.remove(list.size() - 1);
}
Copy the code

Get the element at the end of the queue, which is the element at the end of the list:

E rear() {
  return list.get(list.size() -1);
}
Copy the code

By this point, we’ve all implemented queues and double-endian queues. It is easy to implement queues by encapsulating dynamic arrays or linked lists. For those interested in the structure of dynamic arrays or linked lists, see previous installments of the Data Structures and Algorithms-Basics series.

\