define
A queue is a linear table with limited operation, allowing only insertion at one end and deletion at the other. The inserted end is called the end of the queue, and the deleted end is called the head of the queue. Because of this limitation, the queue has the first-in, first-out characteristic, so the queue is also a first-in, first-out linear table.
Sequential storage
The sequential storage structure of the queue, in addition to storing the array, also needs a pointer to rear and a pointer to front. When the queue is initialized, rear and front both point to the same index 0, so shi is null.
- When an element joins the queue, the tail pointer is +1
- When an element goes out of the queue, the queue head pointer +1
- In a non-empty queue, the head pointer always points to the head element, and the tail pointer always points to the next position of the tail element
In this case, false overflows occur because both the head and tail Pointers are increased and not decreased during enqueue and dequeue operations, causing the deleted element space to never be reused. That is, although the number of elements in the queue is much smaller than the size of the array, the tail pointer has exceeded the upper bound of the array, so that the queue operation cannot be performed. This phenomenon is called false overflow.
The array size is 4. During queue operation, the change process of the head and tail Pointers is shown in the following figure
Circular queue
What can be improved to overcome false overflow? The natural idea is to put the new element in the free space, back at index 0, so that it looks like a ring ending to end. This queue is called a loop queue.
We’re still adding one to the head and tail of the loop queue, but when the head and tail reach the upper bound of the array, we’re adding one back to the lower bound of 0.
// I stands for head, tail pointer
if i+1 == maxSize {
i = 0
} else {
i++
}
Copy the codeThe above operation can be simplified by using the modulo operation, I = (I +1) % maxSize, which makes full use of all the space on the array and does not overflow unless the array space is full. Let’s take a look at the loop queue and see how the head and tail Pointers change.
We analyze this problem with the maximum queue capacity of 4:
- First, the state of the queue is judged by the relative positions of front and rear, so there are four situations: 0,1,2,3
- In fact, there are five states in the queue: 0 (empty queue), 1 element, 2 elements, 3 elements, and 4 elements (full queue)
- So, to use 4 cases to distinguish 5 cases, obviously, is not practical
How do you solve it? Generally, there are two schemes:
1, Use the extra tag bit, set the tag to 1 when entering the team and 0 when leaving the team, so that when front==rear, you can use the tag value to determine whether the team is empty or full
(rear+1) %maxSize == front, (rear+1) %maxSize == front, (rear+1) %maxSize == front, (rear+1) %maxSize == front, (rear+1) %maxSize == front, (rear+1) %maxSize == front (The example code below, implemented in this scenario) is shown below
Of course, you can also use chained storage to build the queue. If chained storage is used, there is no capacity problem, so there is no need to judge the queue is full.
The main operating
Structure describing
type data interface{}
type Queue struct {
list []data
front int / / the head pointer
rear int / / the tail pointer
maxSize int // Maximum capacity
}
func New(maxSize int) *Queue {
q := &Queue{
list: make([]data, maxSize+1),
front: 0,
rear: 0,
maxSize: maxSize + 1.// A spare capacity is not used
}
return q
}
Copy the codeTo the full
func (q *Queue) IsFull(a) bool {
return (q.rear + 1) % q.maxSize == q.front
}
Copy the codeSentenced to empty
func (q *Queue) IsEmpty(a) bool {
return q.front == q.rear
}
Copy the codeThe team
Judge if the team is full, report an error if it is full, otherwise join the team
func (q *Queue) Enqueue(value data) (bool, error) {
if q.IsFull() {
return false, errors.New("The line is full")
}
q.list[q.rear] = value
q.rear = (q.rear + 1) % q.maxSize
return true.nil
}
Copy the codeOut of the team
If the team is empty, an error will be reported, otherwise the team will be out
func (q *Queue) Dequeue(a) (data, error) {
if q.IsEmpty() {
return nil, errors.New("Line is empty.")
}
value := q.list[q.front]
q.list[q.front] = nil
q.front = (q.front + 1) % q.maxSize
return value, nil
}
Copy the codeGets the value of the queue header
func (q *Queue) GetHead(a) (data, error) {
if q.IsEmpty() {
return nil, errors.New("Line is empty.")}return q.list[q.front], nil
}
Copy the codeApplication: Output Yang Hui triangle
Yang Hui triangle is a geometric arrangement of binomial coefficients in triangles, as shown in the figure below
- The values at the end of each line are 1
- Each number is equal to the sum of the left and right digits on the previous row. This property can be used to write the entire Yang Hui triangle, that is, the i-th number of row n+1 is equal to the sum of the i-th and i-th numbers of row n, that is, C(n+1, I)=C(n, I)+C(n,i-1).
Based on these properties, one idea when using a program to input Yang Hui’s triangle is to take two arrays, and as you output the current row, compute the value of the next row, put it in another array, and alternate between the two arrays.
In the second scenario, we can use the queue to output, which can reduce the space of an array. When using the Yang Hui triangle of queue output, there is a small trick, which is to add two zeros at both ends of each row, which is the following form
0 1 0
0 1 1 0
0 1 2 1 0
Copy the codeOn this premise, the algorithm idea (n represents the number of lines) :
1. Initialize a queue and queue the first column 0, 1, 0 in sequence;
2. The number of elements in each line is N + 2, and each element in the line is output in turn, 0 is output but no output;
3, at the same time of the element out of the queue, calculate the value of the corresponding position of the next line, that is, out of the queue element + the new queue head element, and add the calculated value to the queue;
4. When each element in the line is output, the next element in the queue is calculated, and then 0 is added to the queue. This 0 is the 0 at the end of this line and the 0 at the beginning of the next line.
5. Repeat 2,3,4 until n ends.
Let’s take n = 4 as an example to see what happens to the elements in the queue:
const maxSize = 1000
func printYangHui(n int) {
q := Queue.New(maxSize)
q.Enqueue(0)
q.Enqueue(1)
q.Enqueue(0)
for i := 1; i <= n; i++ {
formatPrint(n-i) // Format output
for j := 1; j < i+2; j++ {
// Line I has I + 2 digits in the queue, including the first and last two zeros,
/ / 1 0 0
// 0 1 1 0
// 0 1 2 1 0
s, _ := q.Dequeue()
ifs ! =0 {
fmt.Printf(" %d", s)
}
t, _ := q.GetHead()
q.Enqueue(s.(int) + t.(int)) // The number in the next line is the sum of the left and right shoulders
}
q.Enqueue(0) // add 0 to each row
fmt.Println()
}
}
printYangHui(4) // The result is shown below
Copy the code
conclusion
The above application is only a small application of queue, theoretically the data flow conforms to the first-in, first-out rule, can consider using queue to solve the problem. For example, the printer’s printing schedule, the advanced content will be printed first, and so on.
Thanks!