Basic Data Structure - Queue

Posted on Edited on In Waline:

Queue is an essential data structure when we are programming. It can be implemented with an array or a linked list. However, in fact, there are also some small places in the queue that will be forgotten because they will not be used for a long time. This time, I will recall it a little.

What is a queue

The concept of a queue is very easy to understand. You can think of it as a queue to buy tickets, the first to come buys first, and the later person can only stand at the end and is not allowed to jump in line. First in first out, this is a typical “queue”.

We know that the stack only supports two basic operations: push () and pop (). Queues are very similar to stacks and support very limited operations. The most basic operations are also two: enqueue (), which puts a piece of data at the end of the queue; dequeue (), which takes an element from the head of the queue.

Two implementations

Sequential queue

A queue implemented as an array is a sequential queue. The following example uses a simple version implemented in the JavaScript language

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class myQueue {
    constructor(capacity) {
        this.items = new Array(capacity);
        this.n = capacity;
        this.head = 0;
        this.tail = 0;
    }

    enqueue(item) {
        if (this.tail = this.n) {
            return false;
        }
        this.items[this.tail++] = item;
        return true;
    }

    dequeue() {
        if (this.head = this.tail) {
            return null;
        }
        let res = this.items[this.head++];
        return res;
    }
}

This code actually has a very serious problem, that is, with the continuous entry and exit, the head and tail are constantly moving backwards until the tail points to the end, even if there is space in front of the head at this time, the data cannot be inserted.

So how do we solve this problem? In fact, there are many solutions, but it boils down to’data migration '. We say one of them here is to transform our team joining function. When joining the team, we find that the tail has reached the position of the tail of the team, and move all the data to start from the head., and then insert.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enqueue(item) {
    if (this.tail = this.n) {
        if (this.head = 0) {
            return false;
        }
        for (let i = this.head; i < this.tail; i++) {
            this.items[i - this.head] = this.items[i];
        }
        this.tail -= this.head;
        this.head = 0;
    }
    this.items[this.tail++] = item;
    return true;
}

Cyclic queue

The above code can actually achieve the basic operation of a queue, but if tail points to the tail of the queue, it will involve a data move, which is time-consuming. Can we find a way to omit this step?

This involves a design that impressed me the most when I just learned the algorithm class in college. We bent the queue and made it a first-contact ring, so that when the tail points to the end of the queue, then insert the data. The tail pointer can re-point to the head of the queue, as long as the head pointer is not in the head.

Before implementing the code, we first need to think about why this is possible and what should we pay attention to?

The first question, we can come back and think about the following, what is the role of head and tail in fact? These two values actually mark the position within the [head, tail) interval with data, and the position outside the interval has no data. We can think of this item as a piece of rail, [head, tail) is the train on the rail, if this section of rail is a line segment, then the train can only move from head to tail, once moved to the tail, it can only move the train back to the head, but if this section of rail is a circle, then the process of moving the train back to the head can be omitted.

The second question, we also said above that there is data in the [head.tail) interval. This interval is a front-closed and back-open space, that is to say, the node pointed by head has data, and the node pointed by tail is to be inserted. If it points to the same, that is, the initial situation, it is considered no data. Then if we make this queue circular, there will be a question, when head = tail, is it the initial state or tail is back? And tail indicates that it can be inserted here next, but in fact head has already been inserted into the data here. So on the other hand, we can’t let the tail go back to the place where the head points after another circle, so we need to introduce a sentry-like position in front of the head, and when the tail points here, the queue is full.

After understanding these two questions, you can know that the condition for team empty is head = tail, and the condition for team full is (tail + 1) % n = head

The code at this time should look like this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class myQueue {
    constructor(capacity) {
        this.items = new Array(capacity);
        this.n = capacity;
        this.head = 0;
        this.tail = 0;
    }

    enqueue(item) {
        if ((this.tail + 1) % this.n = this.head) {
            return false;
        }
        this.items[this.tail] = item;
        this.tail = (this.tail + 1) % this.n;
        return true;
    }

    dequeue() {
        if (this.head = this.tail) {
            return null;
        }
        let res = this.items[this.head];
        this.head = (this.head + 1) % this.n;
        return res;
    }
}

Chain queue

No matter how optimized the sequential queue mentioned above is, there is actually a relatively large limitation.

This limitation is brought about by the data structure of ** array, that is, the length of the queue must be defined in advance, because the array requires a contiguous piece of memory to ensure O (1) random access based on subscripts.

Some people may ask, the length of the array in Javascript is variable ah, in fact, this is to look at the internal Javascript for the array is how to achieve, a solution is when we do not give the length, will help us apply for a period of memory use, when found that the length is not enough, will help us apply for a larger memory (usually 1.5 times), and then help us copy the data in the past.

So if we use a linked list to implement queues, will there be this problem? The answer is no, because the memory of the linked list is discontinuous, so there is no need to apply in advance, and because of the particularity of the queue, we do not need to randomly access according to the subscript, so it seems that it is better to use a linked list to implement a queue, then let’s try it first.

Before trying, we still need to understand two questions:

  • What are the conditions for the team to be empty?
  • What are the conditions for the team to be full?

For these two questions. The answer to the first question is that head points to null, and the second question is that theoretically there is still memory, so there can be no queue full situation.

It will be easier to write code again at this time, just pay attention to some issues that all linked lists should pay attention to, such as how to move this pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class myQueue2 {
    constructor() {
        this.head = this.tail = null;
    }

    enqueue(item) {
        if (this.tail = null) {
            this.head = this.tail = new Node(item);
        } else {
            let newNode = new Node(item);
            this.tail.next = newNode;
            this.tail = this.tail.next;
        }
        return item;
    }

    dequeue() {
        if (this.head = null) {
            return null
        }
        let res = this.head.val;
        this.head = this.head.next;
        return res;
    }
}

This code can already work normally, but there are still a few issues we need to think about:

  • Will there be a memory leak? For example, when dequeue reaches the last head with null, tail actually still holds a reference to the last node
  • Is the sentry node useful here?

Two usage scenarios

Blocking queue

Blocking queue is actually a blocking operation added to the queue. Simply put, when the queue is empty, fetching data from the head of the queue will be blocked. Because there is no data available at this time, it cannot be returned until there is data in the queue; if the queue is full, the operation of inserting data will be blocked until there is a free position in the queue, and then return.

Concurrent queue

Thread-safe queues are called concurrent queues. The simplest and most direct implementation method is to directly lock the enqueue () and dequeue () methods, but the concurrency will be relatively low if the lock granularity is large, and only one save or fetch operation is allowed at the same time. In fact, array-based circular queues, using CAS atomic operations, can achieve very efficient concurrent queues. This is also the reason why circular queues are more widely used than chained queues.

The so-called CAS atomic operation, that is, Compare and Set is to compare the data at the end of the queue with their last acquisition is not the same, if the same description queue has not been updated by other threads, you can set the value in, if not the same, indicating that the queue has been updated.

Is this design idea a bit like区块链？