Shulou(Shulou.com)06/03 Report--

What are the queue writing methods, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Preface

Stack and queue are a pair of good brothers. We introduced an article on stack (stack, not last-in-first-out). The mechanism of stack is relatively simple, last-in-first-out, just like entering a narrow cave, where there is only one entrance and only last-in-first-out (it is a bit unlucky for those who get stuck on the inside to get in first). The queue is like a tunnel, the people behind follow the front, and the people in front go out first (first in, first out). The daily queue is a description of the operation of the queue!

The stack is a kind of data structure that likes the new and hates the old. When the new comes, it will deal with the new and stagnate the old first (we hate this kind of people most when we find people and make appointments). Queue is a kind of selfless data structure, which is queuing, first-come, first-served and pay attention to sequence. so this kind of data structure is widely used in program design, middleware and so on. For example, message queuing, FIFO disk scheduling, binary tree sequence traversal, BFS width first search, and so on.

The core idea of the queue is: first in, first out! This very basic and important data structure must be mastered and handwritten! Although the queue is the core rule of FIFO, handwriting still needs to consider a lot of details!

The concept of queue: queue is a special linear table, which is special in that it only allows deletion at the front end of the table (front) and insert operation at the back end of the table (rear). Like the stack, a queue is a linear table with limited operations. The end of the insert operation is called the end of the queue, and the end of the delete operation is called the head of the line.

At the same time, reading this article, it is best to understand the basic operation of the sequence table and the data structure of the stack! The learning effect is better!

Queue introduction

When we design the queue, we can choose a standard, here we take the force buckle 622 design cycle queue as the queue design standard.

Line header front: delete one end of the data.

Rear at the end of the queue: insert one end of the data.

For arrays, it is easier to insert from the back of the array, but it is more difficult to insert in front of the array, so the queue header implemented by the array is generally in front of the array and the end of the queue is behind the array, while for linked lists, insert deletion is the most convenient choice to delete the head (front) and tail insertion at both ends.

Implementation method:

MyCircularQueue (k): constructor that sets the queue length to k.

Front: get the element from the head of the team. If the queue is empty, return-1.

Rear: gets the end-of-line element. If the queue is empty, return-1.

EnQueue (value): inserts an element into the circular queue. Returns true if the insert is successful.

DeQueue (): removes an element from the circular queue. Returns true if deleted successfully.

IsEmpty (): checks whether the loop queue is empty.

IsFull (): check whether the circular queue is full.

Ordinary queue

According to the above introduction, it is easy to know how the array is implemented. Use array simulation to represent queues. Consider initialization, insertion, and problems.

Some operations that need to be paid attention to in this normal queue are:

Initialization: both the front and rear of the array point to 0. (if the front and rear subscript are equal, the queue is empty.)

Join the team: the team is dissatisfied, the array does not cross the line, pass the value at the end of the line first, and then the subscript at the end of the line is + 1 (rear at the end of the line is actually one bit ahead, in order to distinguish the situation of empty queue)

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

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)

In view of the above problems. There is a better solution! Is to reuse the memory that has been applied for. This is what we call a circular queue. One of the benefits of a circular queue is that we can take advantage of the previously used space of the queue. In a normal queue, once a queue is full, we cannot insert the next element, even if there is still room in front of the queue. But with circular queues, we can use these spaces to store new values.

The circular queue implemented by the array is logically modified. Because we only need front and rear pointers in the queue. Rear is logically behind, front is logically in front, but in fact they are not necessarily who is in front of them. When calculating the distance, you need to add the array length minus front to rear, and then ask for the remainder.

Initialization: both the front and rear of the array point to 0. It should be noted here that when front and rear are in the same location, it proves that the queue is empty. Also, when I implement it here, I will make the array application larger by one location to prevent the queue from being full and causing front and rear to be in the same location.

Join the team: if the team is dissatisfied, pass the value at the end of the line first, and then rear= (rear+1)% maxsize

Out of the team: the team is not empty, take the head position element first, front= (front+1)% maxsize

Here, if you need to go to the head position at the end of the queuing index, you can directly + 1 to find the position (which is more concise than judging whether it is at the end), where maxsize is the actual size of the array.

Whether it is empty: return rear = = front

Size: return (rear+maxsize-front)% maxsize; is easy to understand here, it can be explained clearly by a picture, no matter the front can actually meet the requirements before and after.

There are a few things we need to pay attention to, that is, the addition of indicators if you finally need to turn to the head. You can determine whether the position at the end of the array is reached. You can also directly + 1 to make a surplus. Where maxsize is the actual size of the array.

Specific implementation:

Public class MyCircularQueue {private int data []; / Array container private int front;// header private int rear;// tail private int maxsize;// maximum length public MyCircularQueue (int k) {data = new int [knot 1]; front = 0; rear = 0; maxsize = knot 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;}} cyclic queue (linked list implementation)

For queues implemented by linked lists, the position of the head and tail should be considered according to the first-in-first-out rule.

We know that the queue is first-in, first-out, for linked lists, we can use single linked lists as far as possible, convenient as far as possible, but also take into account the efficiency. There are probably two implementations for using linked lists:

In option 1, if the queue head is set at the end of the chain table, and the queue tail is set at the chain table header.

In option 2, if the queue head is set at the head of the chain list and the tail of the queue is set at the end of the chain list, then the insertion at the end of the queue can be inserted at the end of the list (you can point directly to the next with the tail pointer). It is easy to implement, and if the head of the queue is deleted at the head of the linked list, it is also easy to delete nodes.

So what we finally adopt is the lead node of option 2, the single linked list with tail pointer!

The main actions are:

Initialization: set up a header node that both front and rear point to first.

Join the queue: rear.next=va;rear=va; (va is the inserted node)

、

Queuing: the queue is not empty, front.next=front.next.next; Classic takes the lead in deleting the node, but if only one node is deleted, you need to add an extra rear=front, otherwise rear will be lost.

Whether it is empty: return rear = = front; or custom maintenance len to determine return len==0

Size: the number of node front traverses to the rear, or the custom maintenance len returns directly (not implemented here).

Implementation code:

Public class MyCircularQueue {class node {int data;// node result node next;// next connected node public node () {} public node (int data) {this.data = data;}} node front;// is equivalent to head lead node node rear;// is 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 () {if (isEmpty ()) return false; else {front.next=front.next.next; len--; / / Note: point the rear to front if (len==0) rear=front if it is deleted. } 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;}} two-way queue (extra meal)

Design and implementation of double-ended queue, in fact, you often use ArrayDeque is a classic two-way queue, which is based on array implementation, very efficient. The bi-directional queue template we implement here is based on Likou 641 to design a circular double-ended queue.

Your implementation needs to support the following operations:

MyCircularDeque (k): constructor, the size of the double-ended queue is k.

InsertFront (): adds an element to the header of the double-ended queue. Returns true if the operation is successful.

InsertLast (): adds an element to the end of the double-ended queue. Returns true if the operation is successful.

DeleteFront (): removes an element from the header of the double-ended queue. Returns true if the operation is successful.

DeleteLast (): removes an element from the end of the double-ended queue. Returns true if the operation is successful.

GetFront (): gets an element from the header of the double-ended queue. If the double-ended queue is empty, return-1.

GetRear (): gets the last element of the double-ended queue. If the double-ended queue is empty, return-1.

IsEmpty (): checks whether the double-ended queue is empty.

IsFull (): check whether the double-ended queue is full.

In fact, with the above foundation, it is very easy to implement a double-ended queue. Many operations are the same as the single-ended circular queue. Only one more operation is inserted at the head of the queue and deleted at the end of the queue. The two operations are simply analyzed:

Team head insertion: teammate front subscript position itself is valuable, so front should be pushed back one bit and then assigned, but consider whether it is full or the array is out of bounds.

Delete at the end of the line: you only need to subtract 1 from the rear position, and also consider whether it is empty and out of bounds.

Specific implementation code:

Public class MyCircularDeque {private int data []; / Array container private int front;// header private int rear;// tail private int maxsize;// maximum length / * initialization maximum size is k * / public MyCircularDeque (int k) {data = new int [kend1]; front = 0; rear = 0; maxsize = kud1 } / * * header insert * / public boolean insertFront (int value) {if (isFull ()) return false; else {front= (front+maxsize-1)% maxsize; data [front] = value;} return true } / * * tail insert * / public boolean insertLast (int value) {if (isFull ()) return false; else {data [rear] = value; rear= (rear+1)% maxsize;} return true } / * * normal header deletion * / public boolean deleteFront () {if (isEmpty ()) return false; else {front= (front+1)% maxsize;} return true;} / * * tail deletion * / 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;}} Summary

For queues, the data structure is more complex than the stack, but it is not very difficult to understand first-in, first-out and then implement it with an array or linked list.

For arrays, the position pointed to by the tail at the end of the line is empty, while the front of the linked list (like head) is empty, so the method of achieving the same effect in different structures needs to be noted.

The circular queue implemented by the array can make use of the array space to a great extent, while the two-way queue is an efficient data structure which can be used as both a queue and a stack.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.