Winter vacation is coming. Let's summarize what we learned this semester.

Not to mention the basic properties of queues, we mainly talk about the queue in and out operations in the implementation of static arrays and the most basic constructors.

catalogue

1, Main problems:

2, Code implementation:

2.1 overview:

2.2 constructor:

2.3 destructor:

2.4 air judgment:

2.5 full Award:

2.6 team entry:

2.7 departure:

1, Main problems:

Since the array size is fixed, after a series of queue in and queue out operations, the end of the queue may have reached the end of the array, and there is still a position in front of the head of the queue. At this time, we should put the newly entered elements in front to form a ring like structure, as shown in the following figure.

1. Join 70, 80 and 50 teams:

2. Take 70 and 80 out of the team:

 

 3. Join 90 and 60 teams:

At this time, the end of the team has come to the end. Next, when entering the team, you should put the elements in the space in front, which is like a ring.

2, Code implementation:

2.1 overview:

#pragma once
#include<iostream>
using namespace std;
#Define capability 16 / / the size of the array
class Queue
{
private:
	int *myqueue;//Array implemented queue
	int front;//Queue header subscript
	int back;//The subscript of the next place at the end of the queue where data can be inserted
public:
	Queue() :front(0), back(0),myqueue(new int[CAPACITY]) {};//non-parameter constructor 
	Queue(const Queue& origin);//copy constructor 
    ~Queue();
	bool empty() const;//Air judgment
	bool full() const;//Full sentence
	void display();//print data
	bool enqueue(int newdata);//Join the team
	bool dequeue();//Out of the team
};

The functions implemented have been commented in the code.

2.2 constructor:

1. Parameterless constructor:

This function has been written out in the overview, which sets the head and tail to 0, and opens up a space as large as [capability] for the array.

2. Copy constructor:

Queue::Queue(const Queue& origin)
{
	if (!origin.empty())
	{
		int index = origin.front;//Subscript for traversal
		myqueue = new int[CAPACITY]();//Open up space
		while (index != origin.back)//Traversal assignment
		{
			this->myqueue[index] = origin.myqueue[index];//assignment
			index = (index + 1) % CAPACITY;
		}
	}
}

In the copy constructor, we assign the values of the original array to the new array one by one. Note that when the back of the origin is in front of the front, when the traversal index reaches the end of the array, we will return to the 0 subscript of the array, and then continue to assign values. This step is through code substitution

index = (index + 1) % CAPACITY;

Implementation. When the index exceeds the size of the array after increasing, it will return to the 0 subscript of the array. This operation also occurs in the incoming and outgoing queues.

2.3 destructor:

Very simple deconstruction. When the array has an open space, delete the space.

Queue::~Queue()
{
	if(myqueue != NULL)
	delete []myqueue;
	myqueue = NULL;
	front = 0;
	back = 0;
}

2.4 air judgment:

Define the condition that the queue is empty: front and back are the same.

bool Queue::empty() const
{
	return (front == back);
}

2.5 full Award:

In order not to conflict with the condition of empty judgment, the condition that the queue is full is defined as back, and the next position is front.

bool Queue::full() const
{
	return ((back + 1) % CAPACITY == front);
}

This also involves the loop of the static array. If the back is already in the last position, the next position of the back is at the 0 subscript, so a remainder operation needs to be done here.

2.6 team entry:

bool Queue::enqueue(int newdata)
{
	if (full()) return false;//false is returned when it is full
	myqueue[back] = newdata;//Add new data at the back
	if (++back == CAPACITY) back %= CAPACITY;//Move back,
        //If you move back to the end of the array, put back at the beginning of the 0 subscript
	return true;
}

There are also remainder operations here.

2.7 departure:

bool Queue::dequeue()
{
	if (empty()) return false;//Returns false if the queue is empty
	if (++front == CAPACITY) front %= CAPACITY;
	return true;
}

Because it is an array implementation, the out of queue operation is simply to increase the front by 1. Here, similarly, when the front reaches the end of the array, put the front again at the 0 subscript.