What is a queue

  • A queue is an ordered list that can be implemented as an array or linked list.
  • Follow the first-in, first-out principle, that is, the data stored in the queue should be taken out first. Data saved later, taken out later.

Look at a simulation of queues. 1, 2, and 3 represent the same Queue. There are two Pointers in the queue, front for the head of the queue, rear for the tail.

  1. Figure 1 shows that there is no data in the queue yet, so front and rear are both initialized to -1.
  2. When data is stored in Figure 2, front does not change, while rear changes as data increases. I put 4 data in, so rear is equal to 3.
  3. In figure 3, front becomes 2, rear does not change, because the first two data are taken out first, so the head of the team becomes 2.



    This is the fifO of the queue.

Use arrays to simulate queues

The idea is simple, because the output and input of a queue are processed from the front and rear ends, so two variables, front and rear, record the subscripts of the front and rear ends of the queue respectively. Front changes with data output, rear changes with data input.

package sparsearray; import java.util.Scanner; Public class MyArrayQueue {public static void main(String[] args) {// Create a queue ArrayQueue ArrayQueue = new ArrayQueue(3); char key = ' '; Scanner Scanner = new Scanner(system.in); boolean loop = true; While (loop) {system.out.println ("s(show): display queue "); System.out.println("e(exit): exit program "); System.out.println("a(add): add data to queue "); System.out.println("g(get): fetch data from queue "); System.out.println("h(head): display queue head "); key = scanner.next().charAt(0); // Receive a character switch (key) {case's: arrayqueue.showqueue (); break; Case 'a': system.out.println (" please add number "); int value = scanner.nextInt(); arrayQueue.addQueue(value); break; case 'g': try { int res = arrayQueue.getQueue(); System.out.printf(" %d", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { int headValue = arrayQueue.showHeadQueue(); System.out.printf(" queue header is: %d", headValue); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; }} system.out.println (" exit program "); ArrayQueue class ArrayQueue {private int maxSize; Private int front; Private int rear; Private int[] arr; private int[] arr; Public ArrayQueue(int arrMaxSize) {maxSize = arrMaxSize; arr = new int[maxSize]; front = -1; // Rear = -1; Public Boolean isFull() {return rear == maxSize - 1; Public Boolean isEmpty() {return rear == front; Public void addQueue(int num) {if (isFull()) {system.out.println (" queue isFull, no data can be added "); return; } rear++; Arr [rear] = num; Public int getQueue() {if (isEmpty()) {throw new RuntimeException(" queue isEmpty, no data is needed "); } front++; // return arr[front]; Public void showQueue() {if (isEmpty()) {system.out.println (" queue isEmpty "); return; } for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d]=%d\n", i, arr[i]); Public int showHeadQueue() {if (isEmpty()) {throw new RuntimeException(" Queue empty, no data "); } return arr[front + 1]; // Notice why +1 is used, because it refers to the position before the head of the queue}}Copy the code

You can do everything individually in code, and it seems to work. But there is a problem. You create an array that you can’t use once, like when you’re done fetching data and then adding data to it.

So we’re going to optimize it, use the algorithm, and make it a ring queue. The next chapter continues.