(2) Queue

definition

Similar to a stack, a queue is also a special linear table, and the difference from an array is also reflected in operations such as additions and deletions. The insertion operation of the queue can only be performed at the end of the queue, and the deletion operation of the queue can only be performed at the head of the queue. The queue is a first-in, first-out linear table. A queue implemented with an array is called a chained queue, and a queue implemented with a linked list is called a chained queue.

Basic operations of queues

Similar to the stack, for the queue, inserting data can only be done at the end of the queue, and deleting data can only be done at the head of the queue. When inserting data in the queue, we call it enqueue, and deleting data in the queue is called dequeue.

Similarly, we discuss their addition and deletion operations based on sequential queues and chained queues respectively.

chained queue

For a chained queue, it is also necessary to define two pointers during initialization, the front pointer and the rear pointer point to the tail of the queue. When the queue is empty, both the front pointer and the rear pointer point to the head of the empty linked list. When dequeuing, you only need to point the front pointer to the next node of the current node.

To join the chain queue, you only need to point the next pointer of the node pointed to by the rear pointer at the end of the queue to the new node to be inserted.

class Node():
    '''linked list structure Node node'''
    def __init__(self, val, next = None):
        '''Node Node initialization method.
        parameter:
            val:stored data
            next:Next Node Node's reference address
        '''
        self.val = val
        self.next = next

class LinkQueue():
    """chained queue"""
    def __init__(self):
        """Chained queue initialization"""
        self.head, self.tail = None, None

    def enqueue(self, num):
        """join the team
        parameter:
            num: enqueued value
        """
        node = Node(num)
        if self.tail:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        return True

    def dequeue(self):
        """out of the team
        return:
            Team leader value
        """
        if self.head:
            num = self.head.val
            self.head = self.head.next
            if not self.head:
                self.tail = None
            return num
        return None

    def PrintAll(self):
        """print queue
        return:
            the entire queue
        """
        if not self.head:
            return None
        res = []
        node = self.head
        while node:
            res.append(node.val)
            node = node.next
        return '->'.join('%s'%num for num in res)

sequential queue

For a sequential queue, you need to define two pointers and give the size of the queue when initializing, the front pointer points to the head of the queue, and the rear pointer points to the tail of the queue. When the queue is empty, both the front pointer and the rear pointer point to the position where the index of the array is 0. When dequeuing, you only need to move the front pointer one bit backward, so the dequeue time complexity of the sequential queue is O(1).

For the queue entry operation of the sequential queue, it is necessary to consider whether the queue is full. If the rear pointer has pointed to the last subscript position of the array, it is necessary to judge whether the front pointer has moved backward after the dequeue operation. If The front pointer does not point to the position where the subscript of the array is 0, then the data between the front and rear pointers are moved to the beginning of the array, and then the front pointer points to the position of the array subscript 0 again, and the rear pointer points to the rear-front position. If the front pointer points to the position where the index of the array is 0 and the rear pointer points to the last position of the array, then the queue is full, and the problem of expansion needs to be considered. If the queue is not full and the position pointed to by the rear pointer is not the end of the array, the time complexity of entering the queue is O(1); if the queue is not full and the rear pointer points to the end of the array, and the queue is full and needs to be expanded In these two cases, the time complexity is O(n) due to the data movement involved.

For the enqueue operation of the sequential queue, like the above false overflow situation where the rear pointer points to the end of the array but the front of the array is empty, there are usually two simple and crude solutions:

(1) The first is a solution like the above, which consumes O(n) time complexity for data movement

(2) The second is when initializing the queue, apply for a large enough memory space to ensure that the array does not exceed the bounds

class ArrayQueue():
    """sequential queue"""
    def __init__(self, capacity):
        """Initialization of a sequential queue
        parameter:
            capacity: the size of the sequence queue
        """
        self.queue = []
        self.capacity = capacity
        self.head, self.tail = 0, 0

    def enqueue(self, num):
        """enqueue 1
        parameter:
            num: enqueued value
        """
        if self.tail == self.capacity:
            return False
        self.queue.append(num)
        self.tail += 1
        return True

    def NewEnqueue(self, num):
        """Entry 2: If the leader of the team has extra space and the team is full, move the data before entering the team
        parameter:
            num: enqueued value
        """
        if self.tail == self.capacity:
            if self.head == 0:
                return False
            for i in range(self.head, self.tail):
                self.queue[i - self.head] = self.queue[i]
            self.tail -= self.head
            self.head = 0
        self.queue[self.tail] = num
        self.tail += 1
        return True

    def dequeue(self):
        """out of the team
        return:
            Team leader value
        """
        if not self.queue:
            return False
        num = self.queue[0]
        self.head += 1
        return num

    def PrintAll(self):
        """print queue
        return:
            the entire queue
        """
        if not self.queue:
            print(None)
            return False
        print(self.queue[self.head: self.tail])
        return True

For the first method, when rear==n-1, there will be data movement, which will affect the performance of the queue entry operation; for the second method, due to the continuous dequeuing, the front of the array will be dequeued. A lot of unused memory space is vacated, and these spaces are not released, which will cause a lot of wasted memory space.

So is there any good solution to the out-of-bounds problem of the array? The circular queue to be mentioned next is a solution to this problem.

circular queue

We connect the end of the sequence queue to form a ring. As shown in the figure below, we can see that the size of the queue is 8, front=4, rear=7. When we insert elements into the queue, the data is inserted into the position pointed by rear And rear moves one bit back. It should be noted here that the rear pointer has already pointed to the position with the subscript 7, so when we insert an element at the rear, the rear pointer will point to the position with the subscript 6 next.

The above is the situation when the queue is not full. If the queue is full, suppose the situation of the queue is as shown in the following figure.

We can see that the position pointed to by the rear pointer is empty, which means that our circular queue will waste a storage space when it is used.

So how do you judge whether the team is full or empty? The first is to judge whether the queue is empty, which is the same as the ordinary queue. When front==rear, the queue is empty; the condition for judging the queue full is different from other queues. We can use two methods to judge whether the circular queue is full.

The first one: When we initialize the circular queue, we set a flag bit and a count value count. At first, rear=front and flag=count=0. When we insert a data, we judge whether the count is equal to the queue size n-1 , if it is, then the team is full and cannot insert data and set flag=1, otherwise we insert the data into the current position of rear and move rear to the next bit, count++; also when deleting data, head points to his next position and count—.

The second: According to the summary of the predecessors, the condition for the team to be full is (rear + 1) % n == front, and this condition is directly used to judge whether the team is full.

class CircularQueue():
    """Circular queue implemented with arrays"""
    def __init__(self, capacity):
        """Initialization of a sequential queue
                parameter:
                    capacity: the size of the sequence queue
                """
        self.queue = []
        self.capacity = capacity + 1
        self.head, self.tail = 0, 0

    def enqueue(self, num):
        """enqueue 1
        parameter:
            num: enqueued value
        """
        if (self.tail + 1) % self.capacity == self.head:
            return False
        self.queue.append(num)
        self.tail = (self.tail + 1) % self.capacity
        return True

    def dequeue(self):
        """out of the team
        return:
            Team leader value
        """
        if self.head != self.tail:
            num = self.queue[self.head]
            self.head = (self.head + 1) % self.capacity
            return num

    def PrintAll(self):
        """print queue
        return:
            the entire queue
        """
        if self.tail >= self.head:
            return self.queue[self.head : self.tail]
        res = self.queue[self.head :] + self.queue[:self.tail - 1]
        return res

application

1. Joseph's Problem

2. Thread concurrency problem