queue
- Queue is a sequential list, which can be implemented by array (sequential storage) or linked list (linked storage).
- Follow the principle of first in, first out. That is, the data stored in the queue should be taken out first. After the deposit, it shall be taken out.
Simulating queues using arrays
- The queue itself has a sequence table. If the array structure 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.
- Because the output and input of the queue are processed from the front and rear ends respectively, two variables front and rear are required to record the subscripts of the front and rear ends of the queue respectively. The front will change with the data output, while the rear will change with the data input.
As shown in the figure:
Train of thought analysis:
When we store data into a queue, it is called addQueue. The processing of addQueue needs two steps
- Move the tail pointer back: rear+1, when front == rear [empty]
- If the tail pointer rear is less than the maximum subscript maxSize - 1 of the queue, the data will be stored in the array element referred to by rear, otherwise the data cannot be stored. rear == maxSize -1 [queue full].
Code implementation:
Use an array to simulate a queue and write an ArrayQueue class
class ArrayQueue{
private int maxSize; //Represents the maximum capacity of the array
private int front; //Queue header
private int rear; //Queue tail
private int [] arr; //This array is used to store data and simulate queues
//Constructor to create a queue
public ArrayQueue(int arrMaxSize){
this.maxSize=arrMaxSize;
this.arr=new int[this.maxSize];
this.front=-1; //Point to the queue header and analyze that front is the previous position pointing to the queue header.
this.rear=-1; //Data pointing to the end of the queue (the last data in the queue).
}
//Determine whether the queue is full
public boolean isFull(){
return this.rear == this.maxSize-1;
}
//Determine whether the queue is empty
public boolean isEmpty(){
return this.rear == this.front;
}
//Add data to queue
public void addQueue(int n){
if (isFull()){
System.out.println("The queue is full and data cannot be added");
return;
}
this.rear++; //Move rear
this.arr[rear]=n;
}
//Get the data of the queue and get out of the queue
public int getQueue(){
//Determine whether the queue is empty
if (isEmpty()){
//By throwing an exception
throw new RuntimeException("The queue is empty and data cannot be retrieved");
}
front++; //front backward
return arr[front];
}
//Displays all data for the queue
public void showQueue(){
if (isEmpty()){
System.out.println("Queue empty, no data");
}
for (int i=0;i<arr.length;i++){
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
//The header data of the queue is displayed. Note: it is not fetched
public int headQueue(){
//judge
if (isEmpty()){
throw new RuntimeException("The queue is empty and there is no data");
}
return arr[front+1];
}
}
Test the simulated queue
public static void main(String[] args) {
ArrayQueue arrayQueue= new ArrayQueue(3);
Scanner inpunt =new Scanner(System.in);
Boolean b=true;
do {
switch (inpunt.nextInt()){
case 1:{
try {
System.out.println("Show all data in the queue");
arrayQueue.showQueue();
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 2:{
System.out.println("Add data to queue");
arrayQueue.addQueue(inpunt.nextInt());
break;
}
case 3:{
try {
System.out.println("Displays the header data of the queue");
int headQueue = arrayQueue.headQueue();
System.out.println("Queue header:"+headQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 4:{
try {
System.out.println("Fetch data from queue");
int queueQueue = arrayQueue.getQueue();
System.out.println("Fetch data:"+queueQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
default:{
b=false;
}
}
}while (b);
}
- Test 1: add data and display all data in the queue. It can be seen that three data are added in the queue, namely 10, 20 and 30
- Test 2: check the header data, and then check the header data again after taking out the data. Because the queue follows the principle of first in first out, check the queue after taking the data here. The header data is the data added for the second time.
- Test 3: take out all data and add data. Note here that when we get the data, there will be problems adding data.
Problem analysis and Optimization:
- At present, our array can not be used once, which does not achieve the effect of reuse.
- We can use the algorithm to improve this array into a ring queue.
Use arrays to simulate ring queues
Train of thought analysis
- Adjust the meaning of the front variable. Front points to the first element of the queue, that is, arr[front] is the first element of the queue, and the initial value of front = 0;
- The meaning of the rear variable is also adjusted. Rear points to the last position of the last element of the queue. Because I want to make a space as an agreement. The initial value of real = 0;
- When the queue is full, the condition is (rear+1)% maxSize = front [Full]
- When the queue is empty, the condition is rear == front empty.
- Number of valid data in the queue (rear + maxsize front)% maxsize / / rear = 1 front = 0
code implementation
The previous array simulation queue is optimized to make full use of the array, so the array is regarded as a ring. (it can be realized by taking mold)
class CircleArray{
private int maxSize; //Represents the maximum capacity of the array
//Adjust the meaning of the front variable. Front points to the first element of the queue, that is, arr[front] is the first element of the queue, and the initial value of front = 0;
private int front;
//The meaning of the rear variable is also adjusted. Rear points to the last position of the last element of the queue. Because I want to make a space as an agreement. The initial value of real = 0;
private int rear;
private int [] arr; //This array is used to store data and simulate queues
public CircleArray(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
}
//Determine whether the queue is full
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
//Determine whether the queue is empty
public boolean isEmpty(){
return this.rear == this.front;
}
//Add data to queue
public void addQueue(int n){
if (isFull()){
System.out.println("The queue is full and data cannot be added");
return;
}
//Add data directly
arr[rear] = n;
//Moving rear, we must consider de modulo here
rear = (rear + 1) % maxSize;
}
//Get the data of the queue and get out of the queue
public int getQueue(){
//Determine whether the queue is empty
if (isEmpty()){
//By throwing an exception
throw new RuntimeException("The queue is empty and data cannot be retrieved");
}
/**
* Here, we need to analyze that front is the first element pointing to the queue
* 1.First, keep the value corresponding to front to a temporary variable
* 2.Move the front back and consider taking the mold
* 3.Return temporarily saved variables
*/
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
//Displays all data for the queue
public void showQueue(){
//ergodic
if (isEmpty()){
throw new RuntimeException("Queue empty, no data");
}
//Idea: start traversing from front, and how many elements are traversed
for (int i= front; i < front + size();i++){
System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
}
}
//Find the number of valid data in the current queue
public int size(){
return (rear + maxSize - front) % maxSize;
}
//The header data of the queue is displayed. Note: it is not fetched
public int headQueue(){
//judge
if (isEmpty()){
throw new RuntimeException("The queue is empty and there is no data");
}
return arr[front];
}
}
Test the ring queue
public static void main(String[] args) {
//The test array simulates a ring queue
CircleArray circleArray= new CircleArray(4); //Set 4, and the maximum valid data of its queue is 3
Scanner inpunt =new Scanner(System.in);
Boolean b=true;
do {
switch (inpunt.nextInt()){
case 1:{
try {
System.out.println("Show all data in the queue");
circleArray.showQueue();
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 2:{
System.out.println("Add data to queue");
circleArray.addQueue(inpunt.nextInt());
break;
}
case 3:{
try {
System.out.println("Displays the header data of the queue");
int headQueue = circleArray.headQueue();
System.out.println("Queue header:"+headQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 4:{
try {
System.out.println("Fetch data from queue");
int queueQueue = circleArray.getQueue();
System.out.println("Fetch data:"+queueQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
default:{
b=false;
}
}
}while (b);
}
-
Test 1 adding data to the ring queue
-
Test 2 fetching data from ring queue
-
Test 3: add data again after fetching data
For more wonderful articles, please visit Cs pull cycle !