编程知识 cdmana.com

Java array simulation queue + optimization

Queue introduction

A queue is a sequence table , It can be realized by array or linked list . Follow the first in, first out principle .

namely : Data stored in the queue first , You have to take it out first . After the deposit to take out after Sketch Map :( Use arrays to simulate queue diagrams )

 

 

  Array mock queue

The queue itself has a sequence table , If you use the structure of the array to store the data of the queue , The declaration of the queue array is shown in the figure below , among maxSize Is the maximum capacity of the queue .

Because the output of the queue 、 Input is processed from the front and back end respectively , So we need two variables front And rear Record the subscripts at the front and back of the queue ,front Will change with data output , and rear It changes with data input ,

As shown in the figure :

When we put data in a queue, it's called ”addQueue”,

addQueue There are two steps to deal with :

Thought analysis Move the tail pointer back :

  rear+1 , When front == rear 【 empty 】 If the tail pointer rear Less than the maximum subscript of the queue maxSize-1, Then store the data in rear In the array element , Otherwise, data cannot be stored .

  rear == maxSize - 1[ The queue is full ] Code implementation Problem analysis and optimization

 

Code implementation

package com.lin.queue_0131;import java.util.Scanner;public class Array_Queue { public static void main(String[] args) {  ArrayQueue arrayQueue = new ArrayQueue(4);  Scanner scanner = new Scanner(System.in);  char c;  while(true) {   System.out.println("------------------------------");   System.out.println("|");   System.out.println("|");   System.out.println("------------------------------");   System.out.println("-1 s(show): Show queue , -2 e(exit): Exit procedure , -3 a(add): Add data to the queue , -4 g(get): Get the data of the queue , -5 h(head): View the queue header data  ");   System.out.println(" Please enter the above prompt character :");   c = scanner.next().charAt(0);   switch (c) {   case 's':    arrayQueue.showQueue();    break;   case 'e':    System.exit(0);    break;   case 'a':    System.out.println(" Please enter add data :");    int n = scanner.nextInt();    arrayQueue.addQueue(n);    break;   case 'g':    try {     System.out.println(" Out of the team :" + arrayQueue.getQueue());    } catch (NullQueueException e) {     System.err.println(e.getMessage());    }    break;   case 'h':    try {     System.out.println(" Header data :" + arrayQueue.headQueue());    } catch (NullQueueException e) {     System.err.println(e.getMessage());    }    break;   default:    break;   }  } }}class ArrayQueue{  private int fornt; private int rear; private int maxSize; private int[] arr;  //  Create a queue constructor  public ArrayQueue(int maxSize){  this.arr = new int[maxSize];  this.maxSize = maxSize;  this.rear = -1;  //  Data at the end of the line   this.fornt = -1; //  Point to the previous position of the queue head  }  //  Determine if the queue is full  public boolean isFull() {  return rear == (maxSize - 1); }  //  Determines if the queue is empty  public boolean isEmpty() {  return rear == fornt; }  //  The team  public void addQueue(int n) {  if(!isFull()) {   arr[++rear] = n;   System.out.println(" Add success !");  } else {   System.out.println(" The queue is full !");  } }  //  Out of the team  public int getQueue() throws NullQueueException {  if(isEmpty()) {   throw new NullQueueException(" The queue is empty !"); //  Custom exception   }  int arrNum = arr[++fornt];  arr[fornt] = 0;  return arrNum;   }  //  Traverse the queue  public void showQueue() {  if(isEmpty()) {   System.out.println(" The queue is empty , Unable to output data !");   return;  }  for (int i = 0; i < arr.length; i++) {   System.out.print("arr[" + i + "] = " + arr[i] + "\t");  }  System.out.println(); }  //  Display the header data of the queue  public int headQueue() throws NullQueueException {  if(isEmpty()) {   throw new NullQueueException(" The queue is empty !"); //  Custom exception   }  return arr[fornt +1]; }}
Be careful : Code arrays without optimization can only be used once , Even if the queue is empty , You can't add data .........

版权声明
本文为[Program ape Owen]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/01/20210131170206205e.html

Scroll to Top