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

This article mainly introduces java how to implement the queue queue data structure, the article is very detailed, has a certain reference value, interested friends must read it!

Concept

Queue is a non-primitive (special) linear table and a first-in-first-out (FIFO) data structure. It only allows delete operations at the front end of the table (front) and insert operations at the back end of the table (rear).

FIFO:first input first output, that is, the element added first, removed first, then added, and finally removed.

The way it works is similar to the situation of queuing up at shopping malls to check out:

Array analog queue diagram:

Two main operations in the queue

Insert value operation: insert-- "enqueue (queue)--" parameter is the data data to be inserted

Delete value operation: remove-- "dequeue (out of line)--" No parameter

The queue follows the following conditions:

If FRONT = 0, then the queue is empty.

If REAR = size of the queue, then the queue is full.

If FRONT = REAR, there is at least one element in the queue.

If you want to know the total number of elements in the queue, use this formula to calculate (REAR-FRONT) + 1.

Array implementation of queue

We can implement queues through arrays, stacks, and linked lists. Arrays are the easiest way to implement queues.

Create an array of size n. Initialize the value of FRONT and REAR to-1, which indicates that the array is currently empty.

Write an ArrayQueue class as follows:

Class ArrayQueue {maximum capacity of private int maxSize; / / array private int front; / / queue header private int rear; / / queue tail private int [] arr; / / stores data, simulates the queue / / creates a constructor, and initializes public ArrayQueue (int arrMaxSize) {maxSize = arrMaxSize Arr = new int [maxSize]; front =-1; / / front is the previous position pointing to the head of the queue rear =-1; / / rear is the data pointing to the end of the queue (the last data)} / / determine whether the queue is full () {return rear = = maxSize-1 } / / determine whether the queue is empty public boolean isEmpty () {return rear = = front;} / / add data public void addQueue (int n) {if (isFull ()) {System.out.println ("queue is full, no more data can be added!") ; return;} rear++; / / Let rear move back arr [rear] = n } / / get data public int getQueue () {if (isEmpty ()) {/ / by throwing an exception throw new RuntimeException ("queue is empty, no data is desirable!") ;} front++; / / front moves back to return arr [front];} / / displays all data in the queue public void showQueue () {if (isEmpty ()) {System.out.println ("queue empty, no data ~"); return } for (int I = 0; I < arr.length; iTunes +) {System.out.printf ("arr [% d] =% d\ n", I, arr [I]) }} / / displays the next public int headQueue () {if (isEmpty ()) {throw new RuntimeException ("queue is empty, no data ~");} return arr [front + 1];}}

Write test methods:

/ / create a queue ArrayQueue queue = new ArrayQueue (3); char key =''; Scanner scanner = new Scanner (System.in); / / boolean loop = true / / output a menu option while (loop) {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 queue header"); key = scanner.next () .charAt (0) / / receive a character switch (key) {case's data: / / display all data in the queue queue.showQueue (); break Case'asides: / / add data System.out.println ("output a number"); int value = scanner.nextInt (); queue.addQueue (value); break Case's data: / / take out the data try {int res = queue.getQueue (); System.out.printf ("the data taken out is% d\ n", res) } catch (Exception e) {/ / TODO: handle exception System.out.println (e.getMessage ());} break Case'hackers: / / View queue header pointing to try {int res = queue.headQueue (); System.out.printf ("queue header data is% d\ n", res) } catch (Exception e) {/ / TODO: handle exception System.out.println (e.getMessage ());} break Case'ebacks: / / exits the program scanner.close (); loop = false; break; default: break }} System.out.println ("Program exit ~");} above is all the content of the article "how to implement the queue queue data structure in java". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.