This is the sixth day of my participation in the August Wenwen Challenge.More challenges in August

preface

Last time we talked about optimizing the array simulation queue, making full use of arrays. So think of an array as a ring. (By taking the mode to achieve)

Ideas as follows

1) Change the meaning of the front variable: front refers to the first element of the queue, i.e. Arr [front] is the first element of the queue.

The initial value of front is 0

2) Adjust the meaning of the rear variable: rear points to the position after the last element in the queue. Because you want to leave a space (this space is to avoid the same conditions of void and full) as the convention

The initial value of rear is 0

(rear+1)%maxSize==front

4) Rear == front when the queue is empty

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

Graphics intuitive

Code implementation

package Demo; import java.util.Scanner; Down down down down down down down down down down down down down down public class CircleArrayQueue {public static void main(String[] args) { System.out.println(" Test array emulation ring queue "); CircleArray queue = new CircleArray(4); char key = ' '; Scanner Scanner = new Scanner(system.in); boolean loop = true; While (loop){system.out.println ("s(show): display queue "); System.out.println("a(add): add data to queue "); System.out.println("g(get): fetch data from queue "); System.out.println("e(exit): exit program "); System.out.println("h(head): view queue header data "); key = scanner.next().charAt(0); switch (key){ case 's': queue.showQueue(); break; Case 'a': system.out.println (" enter a number "); int value = scanner.nextInt(); queue.addQueue(value); break; Case 'g':// retrieve data try{int res = queue.getQueue(); System.out.printf(" fetch data is %d\n",res); }catch (Exception e){ System.out.println(e.getMessage()); } break; Case 'h':// Display queue header data try{system.out.println (); int res = queue.headQueue(); System.out.printf(" Queue header is %d\n",res); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; default: break; }} system.out.println (" program exit ~~"); }} left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left/down down down down down/serious circular queue code class CircleArray {private int maxSize; Private int front; // Queue header private int rear; Private int[] arr; Public CircleArray(int arrMaxSize){maxSize = arrMaxSize; arr = new int[maxSize]; Public Boolean isEmpty(){return rear == front; Public Boolean isFull(){return (rear + 1) % maxSize == front; Public void addQueue(int n){if(isFull()){system.out.println (" queue full, can't add data ~"); return ; } arr[rear] = n; Rear = (rear+1) % maxSize; Public int getQueue(){if(isEmpty()){throw new RuntimeException(" queue empty, can't fetch data "); } // front is the first element in the queue. Save the value of front to a temporary variable //2. Move front to consider modulo //3. Return int value = arr[front]; front = (front + 1) % maxSize; return value; Public void showQueue(){if(isEmpty()){system.out.println (" queue empty, no data "); return ; } for(int I = front; i < front + size(); i++){ System.out.printf("arr[%d] = %d\n",i % maxSize,arr[i % maxSize]); Public int size(){return (rear + maxSize - front) % maxSize; Public int headQueue(){if(isEmpty()){throw new RuntimeException(" Queue empty, no data ~~"); } return arr[front]; }}Copy the code