A queue of linear tables

structure

First come first comeThis is a typical “queue”.A queue, like a stack, is a linear table data structure with limited operation.

implementation

The order queue

// Queue with arrays
public class ArrayQueue {
  // Array: items, array size: n
  private String[] items;
  private int n = 0;
  // head indicates the team header index, and tail indicates the team tail index
  private int head = 0;
  private int tail = 0;

  // Apply for an array of capacity
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  / / team
  public boolean enqueue(String item) {
    // If tail == n, the queue is full
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  / / out of the team
  public String dequeue(a) {
    // If head == tail, the queue is empty
    if (head == tail) return null;
    // To make it more explicit for students of other languages, put the -- operation on a separate line
    String ret = items[head];
    ++head;
    returnret; }}Copy the code

The head and tail continue to move backwards as the queue enters and exits. When tail moves to the far right, you can no longer add data to the queue even if there is free space in the array. We can exit the team without moving the data. If there is no free space, we just need to focus on triggering the data move operation once more when joining the team.

   // Add item to the end of the queue
  public boolean enqueue(String item) {
    // tail == n Indicates that there is no space at the end of the queue
    if (tail == n) {
      // tail ==n && head==0, indicating that the queue is full
      if (head == 0) return false;
      // Data move
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // Update the head and tail after the move
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }
Copy the code

List the queue

Circular queue

When we implemented the queue with arrays, tail==n was used to move data, and enqueue performance was affected. Circular queues can be used to solve this problem.When a new element, A, joins the team, we place it at subscript 7. But at this point, instead of updating tail to 8, we move it back one bit in the loop to zero. When another element B enters the queue, we put b at zero, and then tail increments by 1 to update to 1. So, after a and B are queued, the elements in the loop queue look like this:

  • Implementation difficulties: confirm queue empty (head === tail) and full ((tail+1)%n=head) conditions.

When the queue is full, tail points to a position in the diagram where no data is actually stored. So, a loop queue wastes the storage space of an array.

public class CircularQueue {
  // Array: items, array size: n
  private String[] items;
  private int n = 0;
  // head indicates the team header index, and tail indicates the team tail index
  private int head = 0;
  private int tail = 0;

  // Apply for an array of capacity
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  / / team
  public boolean enqueue(String item) {
    // The queue is full
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  / / out of the team
  public String dequeue(a) {
    // If head == tail, the queue is empty
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    returnret; }}Copy the code

Queue application

Blocking queue

A blocking operation has been added to the queue. Simply put, fetching data from the queue head is blocked when the queue is empty. Because there is no data available at this point, it cannot be returned until there is data in the queue; If the queue is full, inserting data is blocked until there is a free place in the queue before inserting data, and then returning.The above definition is a “producer-consumer model”! Thus, blocking queues can be used to implement a producer-consumer model that effectively coordinates the rates of production and consumption: when producers produce data too quickly for consumers to consume, the queues that store data quickly fill up. At this point, the producer blocks and waits until the “consumer” consumes the data, and the “producer” is awakened to continue “producing.”

Concurrent queue

In the case of multi-threading, there will be multiple threads operating queue at the same time, this time there will be thread safety problem, then how to achieve a thread safe queue?

  • Thread-safe queues are called concurrent queues. The simplest and most direct way to implement this is to directly lock enqueue() and dequeue() methods, but the lock granularity is large and the concurrency is low. Only one save or fetch operation is allowed at a time. In fact, array-based circular queues, using CAS atomic operations, can achieve very efficient concurrent queues. This is why circular queues are more widely used than chain queues

source

Time.geekbang.org/column/arti…