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

This article mainly introduces how the Java language to achieve the queue, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, the following let the editor take you to understand.

Queue

Queue is a special linear table, which only allows delete operation at the front end of the table and insert operation at the back end of the table.

A queue is an ordered list that can be implemented as an array or a linked list.

Follow the first-in, first-out principle. That is, the data stored in the queue must be taken out first. If you deposit it later, take it out later.

It is equivalent to the queue in our daily life, first come, first serve, and then wait in line at the back.

Graphic illustration

Array analog queue

Through the understanding of the definition, we find that the queue is very similar to our array, so whether we can simulate the queue through the array, let's practice it.

First of all, let's analyze:

The queue itself is an ordered list. If the structure of the array is used to store the data of the queue, the declaration of the queue array is shown in the following figure, where maxSize is the maximum capacity of the queue.

Because the output and input of the queue are processed from the front and rear of the queue respectively, we need two variables, front and rear, to record the subscript of the front and rear of the queue respectively. Front will change with data output, while rear will change with data input.

When we put data in a queue, a process called addQueue,addQueue requires two steps: thought analysis.

When front = = rear [queue has no data], move the tail pointer back: rear + 1

If the tail pointer rear is less than the maximum subscript maxSize-1 of the queue, the data is stored in the array element referred to by rear, otherwise the data cannot be saved. Rear = = maxSize-1 [indicates that the queue is full] cannot store data.

Code

Package com.cz.Queuearray;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.concurrent.BlockingQueue / * @ ProjectName: Data_structure * @ Package: com.cz.Queuearray * @ ClassName: QueueArray * @ Author: Zhang Shengrui * @ Date: 18:42 * @ Version: 2022-2-21 * / public class QueueArray {public static void main (String [] args) {/ / TODO Auto-generated method stub QueueArray1 qArray1 = new QueueArray1 (3); Scanner scanner = new Scanner (System.in); char key ='' Boolean f = true; while (f) {System.out.println ("s (show): display queue"); System.out.println ("e (exit): exit the program"); System.out.println ("a (add): add data to the queue"); System.out.println ("g (get): pull data from the queue") System.out.println ("h (head): view data in the queue header"); key = scanner.next () .charAt (0); switch (key) {case's header: qArray1.getQueue (); break Case'asides: System.out.println ("Please output a number:"); int value = scanner.nextInt (); qArray1.addQueue (value); case'gems: try {int res = qArray1.exitQueue () System.out.printf ("output data is% d\ n", res);} catch (Exception e) {System.out.println (e.getMessage ());} case 'h': int res = qArray1.headQueue () System.out.printf ("header data is% d\ n", res); case'eforth: scanner.close (); fimble false; default:}} System.out.println ("exit the program!") ;}} / array simulation queue class QueueArray1 {private int maxSize;// maximum capacity, private int arr []; / declare array private int front;// queue header element private int rear;// queue tail / / constructor public QueueArray1 (int arrMaxSize) {maxSize = arrMaxSize; arr = new int [maxSize]; front =-1 / / point to the queue header and analyze that front is the previous position pointing to the queue header. Rear=-1 public boolean isEmety / pointing to the end of the queue, pointing to the data at the end of the queue (that is, the last data in the queue) / / judging that the team is empty () {return rear==front; / / judging that the team is full () {return rear== maxSize-1 / / public void addQueue (int n) {if (isFull ()) {System.out.println ("queue is full and cannot be inserted"); return / / without return / / Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3 / / at day1.QueueArray1.insert (QueueArray.java:89) / / at day1.QueueArray.main (QueueArray.java:32) arr [+ + rear] = n; / / outbound public int exitQueue () {if (isEmety ()) {throw new RuntimeException ("queue is empty, no elements") Return arr [+ + front]; / / output all elements public void getQueue () {System.out.println ("queue is empty, unable to output data ~"); for (int I = 0; I < arr.length; iSuppli +) {System.out.printf ("arr [% d] =% d\ n", ijinarr [I]) / / display the header data of the queue, instead of taking the data public int headQueue () {throw new RuntimeException ("data is empty, the header element cannot be removed ~"); return arr [front+1]; queue optimization-circular queue

In the above use, it is found that the array can not be used once, and the effect of reuse is not achieved. Can reuse be realized after all? Of course you can.

We use the algorithm to improve this array into a circular queue module:%

The optimization of the previous array simulation queue, make full use of the array. So think of the array as a ring. (it can be realized by taking the module)

A brief analysis:

When the next one of the tail index is the header index, the queue is full, that is, one of the queue capacity is vacated as a convention. When judging the queue full, you need to pay attention to (rear + 1)% maxSize = = front [queue full]

Rear = = front [queue is empty]

The ideas are as follows:

The meaning of the front variable is adjusted: front points to the first element of the queue, that is, arr [front] is the first element of the queue, and the initial value of front is 0.

The meaning of the rear variable is adjusted: rear points to the last location of the last element of the queue. Because you want to free up a space as a convention, the initial value of rear = 0

When the queue is full, the condition is (rear + 1)% maxSize = = front [full]

Rear = = front null for the condition that the queue is empty

When we analyze it this way, the number of valid data in the queue (rear-front + maxSize)% maxSize

We can modify the original queue to get a circular queue.

Code package com.cz.Queuearray;import java.util.Scanner;/** * @ ProjectName: Data_structure * @ Package: com.cz.Queuearray * @ ClassName: CircleQueueArray * @ Author: Zhang Shengrui * @ Date: 14:58 * @ Version: 2022-2-22 * / public class CircleQueueArray {public static void main (String [] args) {CircleQueueArray1 circlequeue = new CircleQueueArray1 (3); Scanner scanner = new Scanner (System.in) Char key =''; boolean f = true; while (f) {System.out.println ("s (show): display queue"); System.out.println ("e (exit): exit the program"); System.out.println ("a (add): add data to the queue") System.out.println ("g (get): fetch data from the queue"); System.out.println ("h (head): view the data in the header of the queue"); key = scanner.next (). CharAt (0); switch (key) {case's data: circlequeue.showQueue (); break Case'asides: System.out.println ("Please output a number:"); int value = scanner.nextInt (); circlequeue.addQueue (value); case'gems: try {int res = circlequeue.getQueue () System.out.printf ("output data is% d\ n", res);} catch (Exception e) {System.out.println (e.getMessage ());} case 'h': int res = circlequeue.headQueue () System.out.printf ("header data is% d\ n", res); case'eforth: scanner.close (); fimble false; default:}} System.out.println ("exit the program!") ;}} class CircleQueueArray1 {private int maxSize; / / indicates the maximum capacity of the array / / front variable meaning to make an adjustment: front points to the first element of the queue, that is, arr [front] is the meaning of the first element of the queue / / front initial value = 0 private int front; / / rear variable to make an adjustment: rear points to the last element of the queue. Because I want to free up a space as an agreement. / / initial value of rear = 0 private int rear; / / private int at the end of the queue [] arr; / / this data is used to store data, and the simulation queue public CircleQueueArray1 (int MaxSize) {maxSize = MaxSize; arr = new int [maxSize]; / / determines that the queue is full public boolean isFull () {return (rear + 1)% maxSize = = front / / determine that the queue is empty public boolean isEmpty () {return rear = = front; / / add data to the queue public void addQueue (int n) {if (isFull ()) {System.out.println ("queue full, cannot join data ~"); return / / insert the data directly into the array, and use the rear at the end of the queue to determine the position arr [rear] = n; / / move the rear back. Here you must consider taking rear = (rear + 1)% maxSize; / / to get the data of the queue and leaving the queue public int getQueue () {if (isEmpty ()) throw new RuntimeException ("queue is empty, data cannot be fetched"). / / here we need to analyze that front is the first element pointing to the queue, because it is cyclic, so we consider using a temporary variable to get the current queue header / / 1. First keep the corresponding value of front to a temporary variable / / 2. Move the front back and consider taking the module / / 3. Return the temporarily saved variable int value = front; front = (front + 1)% maxSize; return arr [value]; / / find the number of valid data in the current queue public int size () {return (rear-front + maxSize)% maxSize; / / display all data in the queue public void showQueue () {for (int I = front; I < front + size () ) {System.out.printf ("arr [% d] =% d\ n", I% maxSize, arr [I% maxSize]); / / display the header data of the queue, note that the data is not fetched public int headQueue () {/ / judge that the queue is empty if (isEmpty ()) {throw new RuntimeException ("queue empty, no data ~"); return arr [data] Use java internal queues

The LinkedList class implements the Queue interface, so we can use LinkedList as a Queue.

Code package com.cz.Queuearray;import java.util.LinkedList;import java.util.Queue / * @ ProjectName: Data_structure * @ Package: com.cz.Queuearray * @ ClassName: LinkedListDemo * @ Author: Zhang Shengrui * @ Date: 15:43 * @ Version: 2022-2-22 * / public class LinkedListDemo {public static void main (String [] args) {/ / add () and remove () methods throw exceptions when they fail (not recommended) Queue queue = new LinkedList () / / offer () adds the specified element to the end of this list (the last element). Queue.offer (1); queue.offer (2); queue.offer (3); queue.offer (4); queue.offer (5); for (Integer nums:queue) {System.out.println (nums);} / / poll () retrieve and delete the header (the first element) of this list. / / when the collection is empty, return null queue.poll (); / / queue.poll (); / / remove () to retrieve and delete the header of the list (the first element). / / an exception java.util.NoSuchElementException; queue.remove () occurs when the collection is empty; / / element () retrieves but does not delete the header of the list (the first element). / / when the queue is empty, java.util.NoSuchElementException / / System.out.println ("head of queue:" + queue.element ()); / / peek () retrieves but does not delete the header of this list (the first element). / / return null System.out.println ("queue header:" + queue.peek ());}} when the queue column is empty.

Poll,remove differences:

Both the remove () and poll () methods remove the first element from the queue. The behavior of remove () is similar to the version of the Collection interface, but the new poll () method does not throw an exception when called with an empty collection, it just returns null. Therefore, the new method is more suitable for situations prone to abnormal conditions.

Peek,element differences:

Element () and peek () are used to query elements at the head of the queue. Similar to the remove () method, element () throws an exception when the queue is empty, while peek () returns null.

So it is recommended to use peek () and poll ().

Thank you for reading this article carefully. I hope the article "how to realize the queue of Java language" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.