(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