preface
Stacks and queues are a pair of good brothers, before we introduce an article on the stack (stack, not last in, first out), the mechanism of stack is relatively simple, after the first out, is like entering a narrow cave, cave is only one entrance, only lifo (starting out in the outside, plugging in advanced to is a bit of luck). 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.
In the meantime, it is best to understand the basic operation of the sequence table and the data structure of the stack first! Better learning results!
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’s easy to spotThe problem, each space domain can only be used once, resulting in extreme waste of space, very easy to cross boundaries!
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.
Return rear == front;
Return (rear+maxsize-front)%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[];// Array container
private int front;/ / head
private int rear;/ / the end
private int maxsize;// Maximum length
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(a) {
if (isEmpty())
return false;
else {
front=(front+1)%maxsize;
}
return true;
}
public int Front(a) {
if(isEmpty())
return -1;
return data[front];
}
public int Rear(a) {
if(isEmpty())
return -1;
return data[(rear-1+maxsize)%maxsize];
}
public boolean isEmpty(a) {
return rear == front;
}
public boolean isFull(a) {
return (rear + 1) % maxsize == front; }}Copy the codeCircular 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.
The team:rear.next=va; rear=va; (VA is inserted node)
Out of the teamThe line is not empty.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.
Return rear == front; Return len==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;// Result of the node
node next;// Next connected node
public node(a) {}
public node(int data) {
this.data = data;
}
}
node front;// equivalent to head of the leading node
node rear;// equivalent to tail/end
int maxsize;// Maximum length
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(a) {
if (isEmpty())
return false;
else {
front.next=front.next.next;
len--;
// Make sure to point rear to front if deleted
if(len==0)
rear=front;
}
return true;
}
public int Front(a) {
if(isEmpty())
return -1;
return front.next.data;
}
public int Rear(a) {
if(isEmpty())
return -1;
return rear.data;
}
public boolean isEmpty(a) {
return len==0;
//return rear == front;
}
public boolean isFull(a) {
returnlen==maxsize; }}Copy the codeTwo-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[];// Array container
private int front;/ / head
private int rear;/ / the end
private int maxsize;// Maximum length
/* The maximum initialization size is k */
public MyCircularDeque(int k) {
data = new int[k+1];
front = 0;
rear = 0;
maxsize = k+1;
}
/** insert */ into the header
public boolean insertFront(int value) {
if(isFull())
return false;
else {
front=(front+maxsize-1)%maxsize;
data[front]=value;
}
return true;
}
/** insert */ at the end
public boolean insertLast(int value) {
if(isFull())
return false;
else{
data[rear]=value;
rear=(rear+1)%maxsize;
}
return true;
}
/** Normal header deleted */
public boolean deleteFront(a) {
if (isEmpty())
return false;
else {
front=(front+1)%maxsize;
}
return true;
}
/** * delete */
public boolean deleteLast(a) {
if(isEmpty())
return false;
else {
rear=(rear+maxsize-1)%maxsize;
}
return true;
}
/** Get the front item */
public int getFront(a) {
if(isEmpty())
return -1;
return data[front];
}
/** Get the last item from the deque. */
public int getRear(a) {
if(isEmpty())
return -1;
return data[(rear-1+maxsize)%maxsize];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty(a) {
return front==rear;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull(a) {
return (rear+1)%maxsize==front; }}Copy the codeconclusion
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.
Finally, the author’s level is limited, if there are loopholes and deficiencies, please point out. Also, if you feel good, you can click like and follow!