This is the third day of my participation in the August More text Challenge. For details, see:August is more challenging

This series of articles is a summary of personal learning, if there are mistakes or questions, welcome to comment!

This is the third article in the relearning data structure series. The previous articles are as follows: 1. Algorithm time complexity and space complexity 2. Relearn data structures – linked lists

1. Queue introduction

What is a queue? The simple understanding is that the bank queue to get money, the front of the line to get money first, the back of the line to get money.

• A queue is an ordered list, which can be implemented as an array or a linked list (we’re using an array here)
• Characteristics of the queue:First in first out, the data stored in the queue must be retrieved first. What is put in is taken out later

In data structures we often say queues have one-way queues and circular queues. Let’s use arrays to simulate these two types of queues.

2. Unidirectional queue

Array simulation:

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

• Since the output and input of the queue are processed from the front and back ends respectively, two variables, front(head pointer) and rear(tail pointer), are required to record the subscripts of the front and back ends of the queue respectively. Front will change with data retrieval, while rear will change with data retrieval, as shown in the figure:

  

• Initialize the

  Initialize array header pointer index == tail pointer index ==-1(that is, the queue has no elements)Copy the code

• Add data to the queue

  1) Determine whether the queue is full, if it is full, it cannot be added: tail pointer subscript = maximum capacity -1 2) Tail pointer moves back one position: rear+1; arr[rear] = nCopy the code

• Fetching data from a queue

  1) Determine whether the queue is null: head pointer subscript = tail pointer subscript 2) Front moves back one position: front+1Copy the code

implementation

public class ArrayQueue { private int maxSize; Private int front; // Private int rear; Private int [] arr; @param maxSize */ public ArrayQueue(int maxSize){this.maxSize = maxSize; arr = new int[maxSize]; rear = -1; front = -1; Public Boolean isEmpty(){return this.front == this.rear; } /** * check whether the queue isFull * @return */ public Boolean isFull(){return this.rear == this.maxsize -1; } @param value */ public void addQueue(int value){if (isFull()){system.out.println (" queue isFull, "); Cannot add data "); return; } this.arr[++rear] = value; } /** * queue */ public int getQueue(){if(isEmpty()){throw new RuntimeException(" queue isEmpty, there is no data to get "); } return arr[++front]; Public void showQueue(){if(isEmpty()){system.out.println (" there are no elements in the queue "); return; } for (int i = front+1; i <= rear; i++) { System.out.printf("arr[%d]=%d\n",i,arr[i]); Public int showQueueHead(){if(isEmpty()){throw new RuntimeException(" the queue isEmpty, there is no data to get "); } return arr[front+1]; }}Copy the code

Testing:

public static void main(String[] args) { ArrayQueue queue = new ArrayQueue(4); queue.addQueue(1); queue.addQueue(3); queue.addQueue(4); queue.addQueue(5); queue.addQueue(6); System.out.println(" display all elements in the queue: "); queue.showQueue(); System.out.println(" queue header element is "+queue.showQueueHead()); System.out.println(); System.out.println(" the queued element is "+queue.getQueue()); System.out.println(" the queued element is "+queue.getQueue()); System.out.println(" the queued element is "+queue.getQueue()); }Copy the code

3. Circular queue

For a normal queue, arrays cannot be reused, thus creating a waste of space. How do you make queues reusable? Change the queue to a ring so it can be reused.

Ideas:

• Here’s an adjustment to the meaning of the front variable: front refers to the first element of the queue, which means that arr[front] is the first element of the queue with an initial value of front = 0
• The meaning of the rear variable is adjusted: rear points to the position after the last element in the queue. Because I want to make room for the convention that the initial value of rear is equal to 0
• When the queue is full, the condition is(rear + 1) % maxSize == front
• If the queue is empty,rear == front
• When we analyze it this way, the number of valid data in the queue(rear + maxSize - front) % maxSize
• We can modify on a one-way queue to get a circular queue

Implementation:

public class CircleQueue { private int maxSize; // Private int rear; // Queue rear points to the position after the last element of the queue. Private int front; private int front; Private int[] arr; @param maxSize */ public CircleQueue(int maxSize){this.maxSize = maxSize; arr = new int[maxSize]; } /** * check whether the queue isFull * @return */ public Boolean isFull(){system.out.println ("rear="+rear+"\tfront="+front "); return (rear+1)%maxSize==front; Public Boolean isEmpty(){return rear == front; return rear == front; } @param n */ public void addQueue(int n){if (isFull()){system.out.println (" queue isFull, can't add data "); return; } arr[rear] = n; rear = (rear+1)%maxSize; } @return */ public int getQueue(){if(isEmpty()){throw new RuntimeException(" the queue isEmpty, there is no data to take "); } int value = arr[front]; front = (front+1)%maxSize; System.out.println("rear="+rear+"\tfront="+front); return value; Public void showQueue(){if(isEmpty()){system.out.println (" the queue isEmpty, there is no data to display "); return; } for (int i = front; i < front + size(); i++) { System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]); }} @return */ public int showQueueHead(){if(isEmpty()){throw new RuntimeException(" if the queue isEmpty, No data to show "); } return arr[front]; } public int size(){return (rear-front+maxSize)%maxSize; }}Copy the code

Testing:

public static void main(String[] args) { CircleQueue queue = new CircleQueue(4); boolean loop = true; char key = ' '; // Accept user input Scanner sc = new Scanner(system.in); While (loop){system.out.println ("s(show) display queue "); System.out.println("g(get) fetch data from queue "); System.out.println("a(add) add data "); System.out.println("h(Head) displays queue header data "); System.out.println("e(exit)"); key = sc.next().charAt(0); Switch (key){case 's': queue.showqueue (); break; case 'g': try { int value = queue.getQueue(); Printf (" %d\n",value); system.out.printf (" %d\n",value); }catch (Exception e){ System.out.println(e.getMessage()); } break; Case 'a': system.out.println (" Enter the number you want to add "); int val = sc.nextInt(); queue.addQueue(val); break; case 'h': try { int value = queue.showQueueHead(); System.out.printf(" queue header data %d\n",value); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e': sc.close(); loop = false; break; default: break; }}}Copy the code

\