C#数据结构：顺序队列
1、 顺序队列的假溢出现象
队列的一种顺序存储称为顺序队列。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组 Queue[MAXSIZE]。
由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针 front 和 rear。
front:指示队头元素在数组中的位置；
rear:指示真实队尾元素相邻的下一个位置。
初始化队列时，令 front = rear =0；
入队时，直接将新元素送入尾指针 rear 所指的单元，然后尾指针增 1；出队时，直接取出队头指针 front 所指的元素，然后头指针增 1。显然，在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。当 rear==MAXSIZE 时，认为队满。但此时不一定是真的队满，因为随着部分元素的出队，数组前面会出现一些空单元，如下图(d)所示。由于只能在队尾入队，使得上述空单元无法使用。把这种现象称为假溢出，真正队满的条件是 rear - front=MAXSIZE 。
img.jpg
2、 循环队列
为了解决假溢出现象并使得队列空间得到充分利用，一个较巧妙的办法是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，我们形象地称之为循环队列。
假设队列数组为 Queue[MAXSIZE]，当 rear+1=MAXSIZE 时，令rear=0，即可求得最后一个单元 Queue[MAXSIZE-1]的后继：Queue[0]。更简便的办法是通过数学中的取模（求余）运算来实现：
ear=（rear+1）mod MAXSIZE，显然，当 rear+1=MAXSIZE 时，rear=0，
同样可求得最后一个单元 Queue[MAXSIZE-1]的后继：Queue[0]。所以，借助于取模（求余）运算，可以自动实现队尾指针、队头指针的循环变化。
进队操作时，队尾指针的变化是：rear=（rear+1）mod MAXSIZE ；
而出队操作时，队头指针的变化是：front=（front+1）mod MAXSIZE。
3、顺序队列的实现：
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 顺序队列
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
{
private T[] data;
private int front;//队首
private int rear;//队尾
private int count;//队中个数
//初始化
public SeqQueue(int size)//size:最大容量
{
data = new T[size];
front = 0;
rear = 0;
count = 0;
}
public SeqQueue() : this(10)
{
}
//最大容量
public int MaxSize
{
get
{
return data.Length;
}
}
//队中元素个数
public int Count
{
get
{
return count;
}
set
{
count = value;
}
}
//判空
public bool IsEmpty()
{
return Count == 0;
}
//判满
public bool IsFull()
{
return Count == MaxSize;
}
//入队
public void Enqueue(T item)
{
if (IsFull())
{
throw new System.Exception("队满，无法入队！");
}
data[rear] = item;
Count++;
rear = (rear + 1) % MaxSize;//修改队尾指针
}
//出队
public T Dequeue()
{
if (IsEmpty())
{
throw new System.Exception("队空，无法出队！");
}
T t = data[front];
front = (front + 1) % MaxSize; //修改队首指针
Count--;
return t;
}
//访问队首元素
public T Peek()
{
if (IsEmpty())
{
throw new System.Exception("队空，无法访问队首！");
}
return data[front];
}
//清空队列
public void Clear()
{
front = 0;
rear = 0;
Count = 0;
}
}
顺序队列：测试用例
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class _008_SeqQueue : MonoBehaviour
{
SeqQueue<string> seqQueue;
void Start()
{
//初始化队列
seqQueue = new SeqQueue<string>(4);//size=4
//队列最大容量
Debug.Log("队列最大容量：" + seqQueue.MaxSize);
//判空
Debug.Log("队列是否空：" + seqQueue.IsEmpty());
//判满
Debug.Log("队列是否满：" + seqQueue.IsFull());
//入队列
Debug.Log("入队列：" + "1,2,3,4");
seqQueue.Enqueue("1");
seqQueue.Enqueue("2");
seqQueue.Enqueue("3");
seqQueue.Enqueue("4");
//队列中元素个数
Debug.Log("队列中元素个数： " + seqQueue.Count);
//判满
Debug.Log("队列是否满：" + seqQueue.IsFull());
//出队列
Debug.Log("出队列-----出队列值为：" + seqQueue.Dequeue());
//队列中元素个数
Debug.Log("出队列后，队列中元素个数： " + seqQueue.Count);
//访问队首元素
Debug.Log("队首元素值： " + seqQueue.Peek());
//队列中元素个数
Debug.Log("访问队首后，队列中元素个数： " + seqQueue.Count);
//清空队列
seqQueue.Clear();
Debug.Log("清空队列！");
//队列中元素个数
Debug.Log("清空队列后，队列中元素个数： " + seqQueue.Count);
}
}
输出结果：
img.jpg
注：
1、 队列的定义与特点
队列 (Queue) 是另一种限定性的线性表，它只允许在表的一端插入元素，而在另
一端删除元素。队列具有先进先出 (Fist In Fist Out，缩写为 FIFO)的特性。
2、 队列的基本操作
进队（插入）、出队（删除）。
3、 队列的存储：链队列、循环队列
4、 循环队列：将顺序队列数组视为首尾相接的队列，模运算支持克服假溢出。
区分循环队列队空队满的两种方法：
- 损失一个元素空间；
- 增设标志量 count。
网友评论