Children’s Day for 8-year-olds, a little hardcore, let’s meet these little programmers and see how they create a different childhood.

Abstract: Data structure is more complicated than stack for queue, but it is not too difficult to understand fifO and then use array or linked list implementation.

This article is shared from huawei cloud community “handwritten all kinds of queues, one article done”, the original author: Bigsai.

preface

Stack and queue are a pair of good brothers, the mechanism of stack is relatively simple, last in first out, just like entering a narrow cave, the cave has only one entrance and exit, can only be last in first out (the outside of the first out, blocked in the inside of the first out is a little unlucky). A queue, on the other hand, is like a tunnel. The people behind follow the people in front, and the people in front exit first. The daily queue is a description of how queues work!

Stack is a discard the data structure to the new will deal with the old first stagnation in this (we have), some people hate such people, the queue is a data structure of selfless, line up first come, first serve, pay attention to order, so this kind of data structure in the program design, middleware, etc are very widely used, Examples include message queuing, FIFO disk scheduling, binary tree order traversal, BFS width first search, and so on.

The core idea of the queue is: first in, first out!

The concept of a queue: A queue is a special kind of linear table, special in that it allows only delete operations at the front of the table and insert operations at the back of the table. Like a stack, a queue is a linear table with limited operations. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue.

The queue is introduced

When we design the queue, we can choose a standard. Here we take the likou 622 design cycle queue as the standard of queue design.

Front: The end of the deleted data.

Rear: Inserts the end of the data.

For arrays, it’s easier to insert from the back of the array, but harder to insert from the front of the array, so arrays are usually implemented with the head in front of the array and the tail behind the array; For linked lists, insert and delete are carried out at both ends, so head (front) delete and tail insert is the most convenient option.

Implementation method:

  • MyCircularQueue(k): constructor that sets the queue length to K.
  • Front: Retrieves elements from the team leader. If the queue is empty, -1 is returned.
  • Rear: Gets the last element of the team. If the queue is empty, -1 is returned.
  • EnQueue (value): Inserts an element into the loop queue. Return true on successful insertion.
  • DeQueue (): Removes an element from the loop queue. Return true if deleted successfully.
  • IsEmpty (): checks if the loop queue isEmpty.
  • IsFull (): checks if the loop queue isFull.

The average queue

From the above introduction, it is easy to see how arrays are implemented. Represent queues with array emulation. You have to think about initialization, insertion.

Some operations to note in this normal queue are:

Initialization: Array front and rear both point to 0.

Join queue: if the queue is not satisfied, the array does not cross the boundary. Pass the value to the rear of the queue first, then the subscript +1(rear is actually one bit ahead, in order to distinguish empty queue).

Out of the team: the team is not empty, first take the team head position element, in the team head +1.

But it is easy to find the problem, each space domain can only be used once, resulting in extreme waste of space, very easy to cross the boundary!

Circular queue (array implementation)

For the above problems. There is a better solution! It is the reuse of allocated memory. This is what we call a circular queue. One of the nice things about a circular queue is that we can use the space that the queue has previously used. In a normal queue, once a queue is full, we cannot insert the next element, even though there is still space in front of the queue. But with circular queues, we can use that space to store new values.

The array implementation of the loop queue is a logical modification. Because we only need front and rear Pointers in the queue. Rear is logically behind, front is logically in front, but actually they don’t have to be in front or in front, so when you compute the distance, you fill in the length of the array to rear minus front, and then you compute the remainder.

Initialization: Both front and rear point to 0. If front and rear are in the same position, the queue is empty. And what I’m doing here is I’m making the array request bigger and leaving it empty so that the queue is full and front and rear are in the same place again.

Rear =(rear+ 1) % maxsize;

Front =(front+ 1)% maxsize;

If we need to go to the end of the queue, we can find the end by +1, where maxsize is the actual size of the array.

Empty: returnrear == front;

Size: return + maxsize – front (rear) % maxsize;

This is easy to understand, a picture can explain, whether the front is actually in front or in back.

There’s a couple of things that you need to be aware of here, and that’s when you add indices and you need to go to the end. We can tell if we’re at the end of the array. Or I could just add 1 to it. Maxsize is the actual size of the array.

Concrete implementation:

public class MyCircularQueue { private int data[]; Private int front; // private int rear; Private int maxSize; Public MyCircularQueue(int k) {data = new int[k+1]; front = 0; rear = 0; maxsize = k+1; } public boolean enQueue(int value) { if (isFull()) return false; else { data[rear] = value; rear=(rear + 1) % maxsize; } return true; } public boolean deQueue() { if (isEmpty()) return false; else { front=(front+1)%maxsize; } return true; } public int Front() { if(isEmpty()) return -1; return data[front]; } public int Rear() { if(isEmpty()) return -1; return data[(rear-1+maxsize)%maxsize]; } public boolean isEmpty() { return rear == front; } public boolean isFull() { return (rear + 1) % maxsize == front; }}Copy the code

Circular queue (linked list implementation)

For queues with linked list implementations, head and tail positions are considered based on first-in, first-out rules

We know that queues are first in, first out, so for linked lists, we can use single-linked lists and try to use single-linked lists as much as we can, as convenient as we can, but also be efficient. There are roughly two implementations of linked lists:

If the queue head is at the end of the list, the queue tail is at the head of the list. If the end pointer is not set, it will traverse to the end of the list, but if the end pointer is set to delete, it will need to put it in the bidirectional list, which is quite troublesome.

If the head of the queue is set at the head of the list and the tail of the queue is set at the end of the list, then the tail of the queue is inserted at the end of the list (the tail pointer can point directly to next), which is easy to implement. If the head of the queue is deleted at the head of the list, it is also easy to implement.

So we ended up with a single linked list with a leading node and a trailing pointer for scheme 2!

The main operations are:

Initialization: Set up a header to which both front and rear point first.

Team: rear. Next = va; rear=va; (VA is inserted node)

Front. Next =front. Next. Next; The classic lead node is deleted, but if only one node is deleted, you need to add a rear=front, otherwise the rear is lost.

Empty: returnrear == front; Or customize the maintenance len and check if returnLen ==0

Size: The number of front nodes traversed to rear, or custom maintenance len returned directly (not implemented here).

Implementation code:

public class MyCircularQueue{ class node { int data; // Node next; Public node() {} public node(int data) {this.data = data; } } node front; // equivalent to head node rear; // tail/end int maxsize; Int len=0; public MyCircularQueue(int k) { front=new node(0); rear=front; maxsize=k; len=0; } public boolean enQueue(int value) { if (isFull()) return false; else { node va=new node(value); rear.next=va; rear=va; len++; } return true; } public boolean deQueue() { if (isEmpty()) return false; else { front.next=front.next.next; len--; If (len==0) rear=front; } return true; } public int Front() { if(isEmpty()) return -1; return front.next.data; } public int Rear() { if(isEmpty()) return -1; return rear.data; } public boolean isEmpty() { return len==0; //return rear == front; } public boolean isFull() { return len==maxsize; }}Copy the code

Two-way queue (extra meal)

In fact, ArrayDeque, which you use a lot, is a classic two-way queue, which is based on arrays and is very efficient. The bidirectional queue template we implement here is based on likou 641 to design a circular two-end queue.

Your implementation needs to support the following:

  • MyCircularDeque(k) : constructor, double-ended queue size k.
  • InsertFront () : Adds an element to the head of a double-ended queue. Returns true on success.
  • InsertLast () : Adds an element to the end of a double-ended queue. Returns true on success.
  • DeleteFront () : Removes an element from the head of a double-ended queue. Returns true on success.
  • DeleteLast () : Removes an element from the end of a two-ended queue. Returns true on success.
  • GetFront () : Gets an element from the head of a two-ended queue. If the two-end queue is empty, -1 is returned.
  • GetRear () : Gets the last element of a two-ended queue. If the two-end queue is empty, -1 is returned.
  • IsEmpty () : checks whether the double-ended queue isEmpty.
  • IsFull () : checks whether the two-end queue isFull.

In fact, with the above foundation, it is very easy to implement a double-ended queue, there are many operations and single-ended loop queue is the same, only a queue head insert and queue tail delete operation, two operations respectively simple analysis:

Team header insertion: The front index position itself has a value, so we need to move front back one bit and then assign it, but consider whether it is full or the array is out of bounds.

Tail deletion: just subtract 1 from the rear position and consider whether it is empty and out of bounds.

Specific implementation code:

public class MyCircularDeque { private int data[]; Private int front; // private int rear; Private int maxSize; Public MyCircularDeque(int k) {data = new int[k+1]; front = 0; rear = 0; maxsize = k+1; } public Boolean insertFront(int value) {if(isFull()) return false; else { front=(front+maxsize-1)%maxsize; data[front]=value; } return true; } public Boolean insertLast(int value) {if(isFull()) return false; else{ data[rear]=value; rear=(rear+1)%maxsize; } return true; } public Boolean deleteFront() {if (isEmpty()) return false; else { front=(front+1)%maxsize; } return true; } public Boolean deleteLast() {if(isEmpty()) return false; else { rear=(rear+maxsize-1)%maxsize; } return true; } /** Get the front item */ public int getFront() { if(isEmpty()) return -1; return data[front]; } /** Get the last item from the deque. */ public int getRear() { if(isEmpty()) return -1; return data[(rear-1+maxsize)%maxsize]; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return front==rear; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return (rear+1)%maxsize==front; }}Copy the code

conclusion

Data structures are a little more complicated for queues than stacks, but it’s not too hard to figure out how to implement fifO with arrays or linked lists.

For arrays, tail points to an empty position, while front (like head) points to an empty head pointer, so be careful how you achieve the same effect in different structures.

Arrays implement circular queues that make great use of array space, while bidirectional queues are efficient data structures that can function as both queues and stacks.

Click to follow, the first time to learn about Huawei cloud fresh technology ~