队列有两种实现方式,一种是数组一种是链表。(这里用数组模拟队列)
图中,左一
图中,中间
图中,右一
队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中MaxSize是队列的最大容量。
因为队列的输入、输入是分别从后端来处理,因此需要两个变量front及rear分别记录队列前后端的下标,front会随着数据输出而改变,而rear则是随着数据输入而改变。
如图:
当我们将数据存入队列时称为“Add Queue”,Add Queue的处理需要有两个步骤:
public class MyQueue1
{
//队列最大值
private int _maxSize;
//队列头部
private int _front;
//队列尾部
private int _rear;
//存储值的数组
private int[] _tempArray;
public MyQueue1(int maxSize)
{
_maxSize = maxSize;
_tempArray = new int[_maxSize];
_front = -1;//指向队列头的前一个位置
_rear = -1;//指向队列尾,指向队列最后一个数据
}
public bool IsFull()
{
return _rear == _maxSize - 1;
}
public bool IsEmpty()
{
return _rear == _front;
}
public void EnQueue(int val)
{
if (IsFull())
{
Console.WriteLine("队列已满,无法加入数据!");
return;
}
_rear++;
_tempArray[_rear] = val;
}
public int DeQueue()
{
if (IsEmpty())
{
throw new Exception("队列是空的,无法取出数据!");
}
_front++;
return _tempArray[_front];
}
public void ShowAll()
{
if (IsEmpty()) {
Console.WriteLine("队列是空的!");
return;
}
Console.WriteLine("显示队列所有内容:");
foreach (var item in _tempArray)
{
Console.Write($"{ item }\t");
}
Console.WriteLine();
}
public void PeekFirst()
{
if (IsEmpty()) {
Console.WriteLine("队列是空的,无法取出数据!");
return;
}
Console.WriteLine($"查看第一个值:{ _tempArray[_front + 1] }");
}
}
调用
MyQueue1 queue = new MyQueue1(3);
queue.EnQueue(97);
queue.EnQueue(98);
queue.EnQueue(200);
//查看第一个值
queue.PeekFirst();
//显示队列里所有的内容
queue.ShowAll();
//取出一个值
Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
queue.PeekFirst();
queue.EnQueue(200);
看到这里,其实在想操作这个队列已经是不可能的了。因为front和rear两个指针没有重置。下一章将会提到环形队列。