上一章说到的数组模拟队列存在的问题,问题分析并优化
对前面的数组模拟队列的优化,充分利用数组。因此将数组看做是一个环形的。(通过去模的方式来实现即可)
分析说明:
实现思路如下:
public class CircleArrayQueue
{
//队列最大值
private int _maxSize;
//队列头部
private int _front;
//队列尾部
private int _rear;
//存储值的数组
private int[] _tempArray;
public CircleArrayQueue(int maxSize)
{
Console.WriteLine($"MaxSize : { maxSize }");
_maxSize = maxSize;
_tempArray = new int[_maxSize];
//front指向队列第一个元素
_front = 0;
//rear指向队列的最后一个元素的后一个位置
_rear = 0;
}
public bool IsFull()
{
return (_rear + 1) % _maxSize == _front;
}
public bool IsEmpty()
{
return _rear == _front;
}
/// <summary>
/// 有效数据个数
/// </summary>
/// <returns></returns>
public int Num()
{
return (_rear + _maxSize - _front) % _maxSize;
}
public void EnQueue(int val)
{
if (IsFull())
{
Console.WriteLine("队列已满,无法加入数据!");
return;
}
//直接插入数据
_tempArray[_rear] = val;
//_rear后移一位,这里必须考虑取模
_rear = (_rear + 1) % _maxSize;
}
public int DeQueue()
{
if (IsEmpty())
{
throw new Exception("队列是空的,无法取出数据!");
}
//这里需要分析出front是指向队列的第一个元素
//1.先把front对应的值保留到一个临时变量
//2.将front后移
//3.将临时保存的变量返回
var tempVal = _tempArray[_front];
_front = (_front + 1) % _maxSize;
return tempVal;
}
public void ShowAll()
{
if (IsEmpty())
{
Console.WriteLine("队列是空的!");
return;
}
Console.WriteLine("显示队列所有内容:");
for (int i = _front; i < _front + Num(); i++)
{
Console.Write($"{ _tempArray[i % _maxSize] }\t");
}
Console.WriteLine();
}
public void PeekFirst()
{
if (IsEmpty())
{
Console.WriteLine("队列是空的,无法取出数据!");
return;
}
Console.WriteLine($"查看第一个值:{ _tempArray[_front] }");
}
}
代码调用
class Program
{
static void Main(string[] args)
{
//MySparseArray sparseArray = new MySparseArray();
//sparseArray.Print();
try
{
CircleArrayQueue queue = new CircleArrayQueue(4);
queue.EnQueue(97);
queue.EnQueue(98);
queue.EnQueue(200);
queue.EnQueue(1000);
//查看第一个值
queue.PeekFirst();
//显示队列里所有的内容
queue.ShowAll();
//取出一个值
Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
queue.PeekFirst();
queue.EnQueue(200);
queue.ShowAll();
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
Console.Read();
}
}
运行效果