Experiment 1
Title Requirements
Use C # to construct a Queue. This Queue is required to be a circular Queue, and the incoming and outgoing tests shall be carried out
Topic meaning analysis
-
Encapsulate the circular queue into a class, and implement the operations such as queue entry, queue exit and display within the class
-
Select the array as the data structure of the storage queue
-
Write the test function in the Main() method
data structure
queue
It is a FIFO linear table, which only allows enqueue, push at the end of the queue and dequeue, pop at the front. Among them, during initialization, rear == front. After there are elements, rear points to the next position of the tail element. At this time, when the rear is the same as * * MAX_SIZE * *, it indicates that the queue has reached the upper limit.
In the actual representation queue, arrays or linked lists are often used for storage. When using arrays or specifying the upper limit of queue capacity, the following problems often occur: * * the tail of the queue keeps increasing backward (subscript becomes larger, the same below), and the head of the queue keeps increasing backward (dequeue), * * then:
Students will find "ah, isn't this a waste? There is still a place, but the report queue can't fit".
There is a way to solve the above problem: after each team, keep moving all the elements forward. It is easy to know that the time complexity of this method is O(n), which is a waste of time.
So someone said, "can we logically connect the header and footer into a circular table, and then save it from subscript 0 after reaching the top of the rear. In this way, the space is continuously recycled and reused, so we don't have to worry about remaining space."
Circular queue
Circular queue came into being!
This data structure solves the problem of wasting space and time, but it also brings new problems: how to judge whether the queue is empty or full?
In the original simple queue, it only needs if (front == rear) to judge the empty team, while it only needs if (rear - front == MAX_SIZE) to judge the full team. In the circular queue, the head and tail of the team will meet when the team is empty and full, causing trouble to everyone. Someone proposed such a solution: add a location to represent the number of elements in the queue. But the faster and space saving solution is to sacrifice a space and point to it with a real. In this way, the judgment condition of team empty is still if (front == rear), while the condition of team full becomes if (rare + 1 == front).
The condition of full team becomes if (rare + 1 == front)
(do you feel there's something wrong with that?)
We say that the circular queue is only a logical circular queue, and the physical storage is still an array (a continuous memory address), so it is entirely possible to have such a situation: front == 0 and rear == MAX_SIZE, there is a problem at this time. rear+1 is still a large number, not 0. Therefore, we need to change the judgment statement slightly:
(rare + 1) % q.Length == front
In this way, when the rear reaches or exceeds the maximum value of the array, it will return to the beginning by taking the module, so as to achieve the effect of loop.
Complete code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace C_Sharp_test
{
public class Queue
{
// Macro definition
private const int OVERFLOW = -1;
private const int QNULL = -2;
// Private member definition
private double[] q;
private uint front = 0;
private uint rear = 0;
// method
public Queue() { q = new double[100]; } // The default queue size is 100
public Queue(uint size)
{
while (size == 0)
{
Console.WriteLine("Queue capacity cannot be 0!");
Console.WriteLine("Please enter the correct queue capacity: ");
size = Convert.ToUInt32(Console.ReadLine().Trim());
}
q = new double[size + 1];
}
public int enqueue(double ele)
{
if ((rear + 1) % q.Length == front)
return OVERFLOW;
q[rear] = ele;
rear = (uint)((rear + 1) % q.Length);
return 1;
}
public int dequeue(ref double ele)
{
if (is_empty())
return QNULL;
ele = q[front];
front = (uint)((front + 1) % q.Length);
return 1;
}
public void show_queue()
{
Console.WriteLine("Queue: ");
if (is_empty())
{
Console.WriteLine("The queue is empty!");
return;
}
uint sub_rear = (uint)((rear + q.Length - 1) % q.Length);
while (sub_rear != front)
{
Console.Write("{0} ", q[sub_rear]);
sub_rear = (uint)((sub_rear + q.Length - 1) % q.Length);
}
Console.Write(q[sub_rear]);
Console.WriteLine();
return;
}
public uint get_len()
{
return (uint)((q.Length + rear - front) % q.Length);
}
public bool is_empty()
{
return rear == front;
}
}
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Please enter the queue capacity: ");
uint size = Convert.ToUInt32(Console.ReadLine().Trim());
Queue q = new Queue(size);
// Team test
Console.WriteLine("Please enter the queue data: ");
string[] lst = Console.ReadLine().Trim().Split(' ');
if (lst.Length > size)
{
Console.WriteLine("Queue capacity exceeded!");
goto end;
}
for (int i = 0; i < lst.Length; i++)
q.enqueue(Convert.ToDouble(lst[i]));
q.show_queue();
// Out of team test
double element = 0;
uint len = q.get_len();
Console.WriteLine("Outgoing data: ");
while (len != 0)
{
q.dequeue(ref element);
Console.Write("{0} ", element);
len--;
}
Console.WriteLine();
q.show_queue();
// Cyclic test
Console.WriteLine("Queue circularity test: ");
for (int i = 0; i < lst.Length; i++)
q.enqueue(Convert.ToDouble(lst[i])); // Put some elements in the queue first
q.show_queue();
for (int i = 0; i < size * 2; i += 2)
{
q.enqueue(i + 1);
q.enqueue(i + 2);
q.dequeue(ref element);
q.dequeue(ref element);
q.show_queue();
}
// end
end:
Console.WriteLine("Please press any key to continue...");
Console.ReadLine();
}
}
}
Code fragment analysis
In class Queue
// Macro definition private const int OVERFLOW = -1; private const int QNULL = -2;
To prevent the occurrence of exceptions, define the return value of the error in advance (overflow is - 1, queue empty is - 2)
C # is a pure object-oriented programming language. All "macro definitions" should be written in classes.
size = Convert.ToUInt32(Console.ReadLine().Trim());
The ReadLine() method of Console class returns a string instead of directly assigning the read data to variables in C/C + +
The Trim() method in the String class means to delete the white space characters at the beginning and end. Its brothers are TrimStart(), TrimEnd(), which means to delete the white space characters at the beginning and at the end respectively
The ToUInt32() method in the Convert class represents converting a string into a 32-bit unsigned integer (that is, uint)
In this way, the read string is converted into an unsigned integer through one-step code.
Students who have studied Python will feel very familiar with the above operations. It is equivalent to the following Python code:
size = int(input().strip()) // Python
Let's look down
q = new double[size + 1];
Because a space is sacrificed, the capacity of one more element is opened up when opening up the space.
public int enqueue(double ele)
{
if ((rear + 1) % q.Length == front)
return OVERFLOW;
q[rear] = ele;
rear = (uint)((rear + 1) % q.Length);
return 1;
}
public int dequeue(ref double ele)
{
if (is_empty())
return QNULL;
ele = q[front];
front = (uint)((front + 1) % q.Length);
return 1;
}
Translate the above data structure into C# language to express it, and the result is like this.
In C + +, types such as double & in dequeue (double & ELE) appear, which are called references. Add & before the variable name (or after the type, if there is only one variable) to represent the reference type. The function is to give the variable an alias, which points to the same memory address as the original variable. In other words, changing its value is equivalent to changing the value of the original variable (because it is changed directly in the corresponding memory location).
In C #, there is also a keyword called ref, which has the same function as the reference in C + +, that is, the parameter is passed by reference. But in C#, when calling parameters containing ref reference methods, you must add ref (as shown below), while there is no corresponding requirement in C++.
q.dequeue(ref element);
The reason for using reference is that you need to pop up the element to be popped in the queue to a variable, otherwise it will be lost (of course, you can also write a function like get_front). If return is used, the value will be confused with the returned error information.
Let's look down
In method show_ In queue():
uint sub_rear = (uint)((rear + q.Length - 1) % q.Length);
In the actual test, it is found that when q.Length is swapped with the - 1 position on its right, the program will bug. The reason should be that the rear is uint, and - 1 may cause overflow problems, so it needs to be swapped.
public uint get_len()
{
return (uint)((q.Length + rear - front) % q.Length);
}
The function of this method is to return the queue length. The first time I wrote this program was return q.Length. Don't make such a mistake. Here, what to return is not the capacity of the queue array, but the "length" of the circular queue.
In the Main() method
// Team test
Console.WriteLine("Please enter the queue data: ");
string[] lst = Console.ReadLine().Trim().Split(' ');
The Split() method "splits" the string according to the specified parameter and returns a string array whose elements are the split string
Students who have studied Python will still feel very familiar with the above operations. It is equivalent to the following Python code:
lst = input().strip().split() // Python
Let's look down
// Cyclic test
This test is to test whether the loop function of the queue is normal, rather than the function that can be achieved by a simple linear table
// end
end:
Console.WriteLine("Please press any key to continue...");
Console.ReadLine();
When you press F5 in VS or click "start" above, VS will run the code, but after running, it will exit the program directly instead of waiting for the user to press the key like the previous C/C + +. So we need to manually create an end pause, just like the code above. Another possible way is to press Ctrl+F5, which will wait for the user to press the key after the program runs.
After a series of hard understanding and coding, our circular queue is finally completed! 😃
summary
Through the first question of Experiment 1, we learned the data structure of queue and its representation - circular queue. Of course, our queues are stored through arrays. Next, we can continue to learn to use linked lists to represent queues. We also learned some knowledge about C #'s reading and processing, Convert conversion platform, ref reference and so on.
reference
Yan Weimin, WU Weimin Data structure (C language version): Tsinghua University Press, 2012
Li Chunbao, Zeng Ping, Yu Dandan C# programming course (3rd Edition): Tsinghua University Press, 2015
Copyright @ 2021, CSDN: ForeverMeteor, all rights reserved.