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

This article introduces you how to understand the queue and java implementation, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Guide reading

Stacks and queues are linear tables with operation restrictions.

Concept

A queue is a linear table that is inserted at one end and deleted at the other.

1. The insertion end of the queue is called the end of the queue, and the deletion end of the queue is called the head of the queue. (like a train entering a tunnel)

2. The insertion operation of the queue is called push, and the deletion operation is called pop.

Characteristics

The queue is like a train entering the tunnel, the tunnel is the queue, the train car is the element, entering the tunnel is inserting the element from this end of the tunnel (the end of the line), and getting out of the tunnel is deleting the element from the other end of the tunnel (the head of the line). Therefore, it is a "first-in, first-out" feature.

Storage structure

There are two kinds of similar stacks: sequence team and chain team.

Java implementation

We can implement the queue around the four elements of the stack:

Status: whether the team is empty; whether the team is full.

Operation: push; in the team, pop out of the team.

The realization of sequential team

The implementation of sequential queue can also be accomplished by array, just like the implementation of stack, except that the stack is pressed and loaded at the same end, while the queue does push at one end and pop operation at the other end.

You can take a look at the following diagram of queue operation:

When we implement the sequence stack, we use the head pointer "front" and the tail pointer "rear" to dequeue and enter the queue, respectively, but the ordinary queue, as shown in the figure above, will have a "false overflow" phenomenon, so we usually make the array into a ring, that is, the head of the queue is connected to the end of the queue, which forms a "circular queue" and solves the phenomenon of "false overflow". Circular queues are improved sequential queues.

As shown in the figure:

For ordinary queue push or pop, we only need to increment the tail pointer or head pointer, but we can't simply augment the queue, when front or rear=maxSize- 1, we can't do self-increment operation, such as an array datas [4] with a queue tail length of 4, then when front or rear need to cycle "push" between 0meme1and 2prime3, so as to achieve the effect of circular queue. So we can use the rear = (rear+1)% maxSize; front = (front+1)% maxSize; formula for pointer calculation.

It should be noted that the condition for team empty status is: front = rear. If the entire queue is full of data, the condition that the queue is full is also front = rear;, so the circular queue needs to lose a storage space, as shown below:

Once these problems are solved, we can easily implement circular queues:

1 package test; 2 3 public class SqQueue {4 private T [] datas;// use arrays as containers for queues 5 private int maxSize;// queue capacity 6 private int front;// head pointer 7 private int rear;// tail pointer 8 9 / / initialize queue 10 public SqQueue (int maxSize) {11 if (maxSize)

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.