Definition of queues

** queues are linear tables that allow only inserts at one end and deletes at the other. ** queues are linear First In First Out tables, or FIFO for short. The end that allows insertion is called the tail, and the end that allows deletion is called the head.

Queue structure

A linear table has sequential storage and chain storage, and a stack is a linear table, so there are two types of storage. Similarly, queue, as a special linear table, also has these two storage modes.

Circular queue

Insufficient queue sequential storage

Append elements at the end of the queue, without moving any elements, O(1) time

The queue element exits at the head of the queue, at subscript 0, which means that everything in the queue has to move forward so that the head of the queue, at subscript 0, is not empty, and the time is zero (n).

Circular queue

A sequential storage structure that puts the heads of queues end to end is called a circular queue.

Condition of queue full

(Rear + 1) %QueueSize = front

On the left, when the queue is empty, the condition is front = rear, and when the queue is full, we modify the condition to keep one element space.

The picture on the right. When the queue is empty, front equals tear, and now when the queue is full, front equals rear.

To distinguish empty queues from full queues, we use the scheme shown on the left.

Queue length calculation formula

(rear-front + QueueSize) %QueueSize

structure

static class SqQueue {    
    int rear;    
    int front;    
    int[] data;
}
Copy the code

The team

If the queue is full, insert element elementData as the new end-of-queue element

static void EnQueue(SqQueue queue, Throws Exception {if((queue.rear + 1) % MAXSIZE == queue.front) {throw new Exception(" queue is full "); } queue.data[queue.rear] = elementData; Queue. Rear = (queue. Rear + 1) % MAXSIZE; // rear moves to the array header}Copy the code

Out of the team

If the queue is not empty, the head element of the queue is deleted and its value is returned

Static Integer DeQueue(SqQueue queue) throws Exception {if(queue.rear == queue.front) {throw new Exception(" queue is empty "); static Integer DeQueue(SqQueue queue) throws Exception {if(queue.rear == queue.front) {throw new Exception(" queue is empty "); } int result = queue.data[queue.front]; Result queue. Front = (queue. Front + 1) % MAXSIZE; Return result; return result; }Copy the code

insufficient

If only sequential storage is not a circular queue, the time performance of the algorithm is not high, but the circular queue also faces the problem that the array may overflow, so we need to study the chain storage structure without worrying about the queue length.

Chain queue

The chained storage structure of a queue is really just a single linked list of linear lists, except it can onlyThe tail into the headWe just call it a chain queue for short. The queue head pointer points to the head node of the chain queue, and the queue tail pointer points to the end node.When the queue is empty, front and rear point to the head node.

structure

static class Node{    
    int data;    
    Node next;    
    public Node() {    }
}
static class LinkQueue {    
    Node front;    
    Node rear;    
    public LinkQueue() {    }
}
Copy the code

The team

Queue operation is to insert nodes at the end of the list

static void EnQueue(LinkQueue queue, int elementData) { Node newNode = new Node(); newNode.data = elementData; queue.rear.next = newNode; Queue. Rear = newNode; // Queue. Rear = newNode; // set the new node to the end of the team. Above 2.}Copy the code

Out of the team

When queuing, the successor of the head node is queuing, and the successor of the head node is changed to the node after it, ifWhen there’s only one element left in the list except the head node, you point rear to the head node.

Static Integer DeQueue(LinkQueue queue) throws Exception {if(queue.rear == queue. Front) {throw new Exception(" Queue is empty "); static Integer DeQueue(LinkQueue queue) throws Exception {if(queue.rear == queue.  } Node p = queue.front.next; P 1 int result = p.data; queue.front.next = p.next; Queue. Rear == p) {queue. Rear == p; queue. Rear = queue. } return result; }Copy the code

conclusion

Comparison of circular and chain queues

In terms of time, in fact, their basic operation is constant time, namely 0(1), but the circular queue is to apply for space in advance, do not release during use, and for the chain queue, each application and release of nodes will also have some time overhead, if the queue is frequent, there is a slight difference between the two.

In space, the circular queue must have a fixed length, so there is the problem of storing the number of elements and wasting space. The chain queue does not have this problem, and although it requires a pointer field and incurs some space overhead, it is acceptable. So in space, chain queues are more flexible.

Circular queues are recommended when maximum queue length can be determined, and chain queues are recommended if you cannot predict queue length.