summary
Baidu Encyclopedia:
Queue is a special linear table, which only allows deletion at the front of the table and insertion at the back of the table. Like stack, queue is a linear table with limited operation. The end that performs the insertion operation is called the tail of the queue, and the end that performs the deletion operation is called the head of the queue. When there are no elements in the queue, it is called an empty queue.
The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called queue in, and deleting a queue element from a queue is called queue out. Because a queue can only be inserted at one end and deleted at the other end, only the elements that enter the queue first can be deleted from the queue first. Therefore, a queue is also called a FIFO first in first out linear table.
In short:
First, what is a queue? As the name suggests, it is a queue. For example, when buying milk tea, people line up in a long queue. Under normal circumstances, if the number of people in the queue increases, new people can only line up at the back of the queue. With the reduction of the number of people in the queue, only the people in front can buy milk tea and then go. This is the reduction of the number of people in the queue.
In programming, the increase and decrease of the number of people is the increase and decrease of data. Here we use arrays to implement this data structure.
Basic elements of the queue:
Creating a queue is equivalent to writing a class to implement the queue, which requires some basic elements
First of all, our queue must have a maximum capacity, because we implement it with an array, and we need to specify the length of the array.
Then we get the data from the queue header, so we have to define a variable to record the index of the queue header.
Correspondingly, the stored data is stored from the end of the queue. We need a variable to store the index at the end of the queue.
Single sequential queue
The following is a single queue:
This is very simple and not very practical. It is mainly to pave the way for the circular queue.
Queues require several necessary methods
1: Determine whether the queue is full
2: Determine whether the queue is empty
3: Add data
4: Fetch data
5: Show all data
6: Display header data
The principle of implementing this queue is:
First, both rear and front are defined as - 1, then move rear when saving data, move rear one bit backward, that is, rear+1, and then assign the data to arr[rear]. Take data: move front backward by one bit, that is, front+1, and then return arr[front+1]. To get data, you need to judge whether the queue is empty, and to save data, you need to judge whether the queue is full.
- Determine whether the queue is full
maxSize is the data capacity defined by us, that is, several data are stored. It starts from 1. The initial value of real is - 1, and then + 1 when saving data. It starts from 0, so it is real = = maxSize - Determine whether the queue is empty
The data fetching front will move backward. When the front catches up with the rear, that is, front==rear, the queue is empty - Add data
- Fetch data
- Show all data
Because each time front points to the location of the last retrieved data, the first data in the real queue should be the data pointed to by front+1, so this is front+1 - Display header data
- test
public static void main(String[] args) {
Queue queue = new Queue(3);
Scanner scanner = new Scanner(System.in);
boolean flag=true;
while (flag){
System.out.println("Stored data: 1");
System.out.println("Fetch data: 2");
System.out.println("Display all data in the queue: 3");
System.out.println("Display header data: 4");
System.out.println("Exit: 5");
char n=scanner.next().charAt(0); //CharAt(0) can get the first character of the string
switch (n) {
case '1': //Single quotation marks represent a single character
System.out.println("input data");
queue.addQueue(scanner.nextInt());
break;
case '2':
try {
int i=queue.getQueue();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '3':
queue.showQueue();
break;
case '4':
try {
int i=queue.showHead();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '5':
flag=false;
break;
default:
break;
}
}
}
Total code
import java.util.Scanner;
import java.util.concurrent.TimeoutException;
public class ArrayQueue {
public static void main(String[] args) {
Queue queue = new Queue(3);
Scanner scanner = new Scanner(System.in);
boolean flag=true;
while (flag){
System.out.println("Stored data: 1");
System.out.println("Fetch data: 2");
System.out.println("Display all data in the queue: 3");
System.out.println("Display header data: 4");
System.out.println("Exit: 5");
char n=scanner.next().charAt(0); //CharAt(0) can get the first character of the string
switch (n) {
case '1': //Single quotation marks represent a single character
System.out.println("input data");
queue.addQueue(scanner.nextInt());
break;
case '2':
try {
int i=queue.getQueue();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '3':
queue.showQueue();
break;
case '4':
try {
int i=queue.showHead();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '5':
flag=false;
break;
default:
break;
}
}
}
}
class Queue{
private int maxSize; //Maximum queue capacity
private int front; //Pair queue header
private int rear; //Queue tail
private int[] arr; //This array is used to store data and simulate queues
public Queue(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[maxSize];
this.front = -1;
this.rear = -1;
}
// Determine whether the queue is full
public boolean isFull(){
return rear==maxSize-1; //true is full and false is not full
}
// Determine whether the queue is empty
public boolean isEmpty(){
return front==rear; //true is null and false is non null
}
// Store data
public void addQueue(int n){
// Determine whether the queue is full
if(isFull()){
System.out.println("The queue is full and cannot be added");
return;
}
rear++;
arr[rear]=n;
}
// Fetch data
public int getQueue(){
if (isEmpty()){
/* Because this function has a return value, we don't need to return the value when we can't get the data
Therefore, function exit cannot be performed in the form of return value,
You can't return directly because you need a return value. If you use return, you must add value to it
Therefore, we can exit this function with the exception throw method and throw an exception
*/
throw new RuntimeException("The queue is empty, unable to fetch data");
}
front++;
return arr[front];
}
// Show all data in the queue
public void showQueue(){
if (isEmpty()){
System.out.println("No data");
return;
}
for (int i = front+1; i <= rear; i++) {
System.out.println("arr["+i+"]The values are:"+arr[i]);
}
}
// Display header data, not fetch data
public int showHead(){
if (isEmpty()){
throw new RuntimeException("No data");
}
return arr[front+1];
}
}
Circular queue
Single time is not very practical. Generally, circular queues are used.
Circular queue is to make some changes on the basis of single queue. In the one-time queue above, after the rear value reaches maxSize-1, even if front==rear, data cannot be added to this queue. Based on the cyclic queue again, if there is a vacancy in front of the queue, when the rear cannot move backward, the rear will jump to the front and add data from the front of the queue.
Implementation of circular queue
Just make some logical changes in the one-time queue.
Therefore, the circular queue also has those properties and methods.
In the loop queue, we set the initial values of rear and front to 0.
Here, in order to distinguish whether the queue is full or empty, we use the following method: leave a space at the end of the queue without storing data (the function here can be reflected in the later specific implementation)
Principle of circular queue:
Unlike the one-time queue, the rear and front start from 0. Moreover, the real reality of the queue is that one person walks in front and everyone moves forward behind. However, in the array, this movement efficiency is too slow, so we make a ring like idea, that is, there is no space behind the array. If there is space in front of the array, put it in front.
- Save data: we save the data first, and then move the front backward. Assuming that the queue is moved to the last position after the rear (because the data is saved first, and then the rear is moved backward, the position pointed to by the rear is empty and the last position of the array storing the queue), and the front does not point to the first position of the array (the data has been taken), if the data is stored again, Then we need to point to the beginning of the array. Therefore, each time we save data, only rear+1 is not enough. Then we need to make such a change to rear every time we save data: (rear+1)%maxSize. It goes without saying that each time the data is increased, the% remainder (modulo) operation of rear+1 is performed. That is, when the rear exceeds or is equal to maxSize-1 (maxSize-1 is the maximum index value of the array), when the rear exceeds or is equal to maxSize-1, the remainder is performed and the data is stored from the array header.
- Fetching data is the same as saving an array. Fetch first and then change the front. Similarly, we need to consider the operation from front to the end of the array and then get the data to the head of the array, so we also need to use% that is: (front+1)%maxSize
How to determine whether the queue is empty or full?
At this time, the advantage of reserving a data space for the queue is reflected.
- Judge that the queue is empty:
When front catches up with rear, that is, front=\=raer.
In this circular array, we save or retrieve data first, and then make changes to the real or front. Therefore, we just leave an empty bit in our circular queue to store data, so the position pointed by the real must be empty. Therefore, when the front catches up with the real, that is, both the front and the real point to the same storage space of the array, the queue is empty. - Judge that the queue is full:
In the ring queue, it is the rear that catches up with the front. That is, the position pointed by rear+1 overlaps with the position pointed by front. However, because we are a ring queue, when the rear runs to the end of the array, the module needs to be taken to add data to the rear
Therefore, the judgment conditions here should be as follows: (rear+1)%maxSize==front
To sum up, we can see that if no vacancy is reserved, whether the queue is full or empty, it is front==rear.
Code implementation:
- Determine whether the queue is full
- Determine whether the queue is empty
- Number of data in the queue
In order to traverse the queue or find the number of queue data, we need to get the number of valid data in the queue
Because it is a circular queue, its valid data may be divided into two segments, that is, the part with data behind the array, that is, maxsize front (why not maxSize-1-front? Because the position pointed to by front also has data, it needs to be regarded as a data at the position of front), and the part with data in front of the array, that is, rear+0. Or if there is only a part of the queue, the number of valid data is: rear front.
Therefore, the combination is: (rear front + maxsize)% maxsize. The% remainder operation is to deal with the situation that there is only part of the queue. For ease of understanding, this formula can be changed as follows:
(rear-front)%maxSize + maxSize%maxSize
- Add data
- Fetch data
- Show all data
In the process of traversal, the number of traversals is determined by the valid data in the queue, and the number of valid data is obtained through the number () function. Here, we do not use the method of i=0 and then increasing it to the value returned by number(). In order to use front in the body of the for loop, we change the cardinality here to front and increase it on the basis of front. Of course, front may return to the array header, so we also need to take the remainder here, that is, i%maxSize - Display header data
When there is data in the queue, the front always points to the queue header - test
public static void main(String[] args) {
CircularQueueDemo queue = new CircularQueueDemo(3);
Scanner scanner = new Scanner(System.in);
boolean flag=true;
while (flag){
System.out.println("Stored data: 1");
System.out.println("Fetch data: 2");
System.out.println("Display all data in the queue: 3");
System.out.println("Display header data: 4");
System.out.println("Exit: 5");
char n=scanner.next().charAt(0); //CharAt(0) can get the first character of the string
switch (n) {
case '1': //Single quotation marks represent a single character
System.out.println("input data");
queue.addQueue(scanner.nextInt());
break;
case '2':
try {
int i=queue.getQueue();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '3':
queue.showQueue();
break;
case '4':
try {
int i=queue.showHead();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '5':
flag=false;
break;
default:
break;
}
}
}
All codes
import java.util.Scanner;
public class CircularQueue {
public static void main(String[] args) {
CircularQueueDemo queue = new CircularQueueDemo(3);
Scanner scanner = new Scanner(System.in);
boolean flag=true;
while (flag){
System.out.println("Stored data: 1");
System.out.println("Fetch data: 2");
System.out.println("Display all data in the queue: 3");
System.out.println("Display header data: 4");
System.out.println("Exit: 5");
char n=scanner.next().charAt(0); //CharAt(0) can get the first character of the string
switch (n) {
case '1': //Single quotation marks represent a single character
System.out.println("input data");
queue.addQueue(scanner.nextInt());
break;
case '2':
try {
int i=queue.getQueue();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '3':
queue.showQueue();
break;
case '4':
try {
int i=queue.showHead();
System.out.println(i);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case '5':
flag=false;
break;
default:
break;
}
}
}
}
class CircularQueueDemo{
private int maxSize; //Maximum queue capacity
private int front; //Pair queue header
private int rear; //Queue tail
private int[] arr; //This array is used to store data and simulate queues
public CircularQueueDemo(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[maxSize];
this.front = 0;
this.rear = 0;
}
// Determine whether the queue is empty
public boolean isEmpty(){
return front==rear; //true is full and false is not full
}
// Determine whether the queue is full
public boolean isFull(){
return (rear+1)%maxSize==front;
}
// Get a total of several data in the queue. For printout
public int number(){
return (rear-front+maxSize)%maxSize;
}
// Add data
public void addQueue(int n){
// Determine whether the queue is full
if(isFull()){
System.out.println("The queue is full and cannot be added");
return;
}
arr[rear]=n;
rear=(rear+1)%maxSize;
}
// Fetch data
public int getQueue(){
if (isEmpty()){
/* Because this function has a return value, we don't need to return the value when we can't get the data
Therefore, function exit cannot be performed in the form of return value,
You can't return directly because you need a return value. If you use return, you must add value to it
Therefore, we can exit this function with the exception throw method and throw an exception
*/
throw new RuntimeException("The queue is empty, unable to fetch data");
}
int n = arr[front];
front=(front+1)%maxSize;
return n;
}
// Displays data for the queue
public void showQueue(){
if (isEmpty()){
System.out.println("No data");
return;
}
for (int i = front; i < front+number(); i++) {
System.out.println("arr["+(i%maxSize)+"]The values are:"+arr[(i%maxSize)]);
}
}
// Display header data
public int showHead(){
if (isEmpty()){
throw new RuntimeException("No data");
}
return arr[front];
}
}