一：概念
队列是一个”先进先出“的线性表，牛X的名字就是“First in First Out(FIFO)”，生活中有很多这样的场景，比如读书的时候去食堂打饭时的”排队“。当然我们拒绝插队。
二：存储结构
前几天也说过，线性表有两种”存储结构“，① 顺序存储,②链式存储。当然“队列”也脱离不了这两种服务，这里我就分享一下“顺序存储”。
顺序存储时，我们会维护一个叫做”head头指针“和”tail尾指针“，分别指向队列的开头和结尾。
代码段如下：
复制代码 代码如下:
#region 队列的数据结构
/// <summary>
/// 队列的数据结构
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
{
private const int maxSize = 100;
public int MaxSize
{
get { return maxSize; }
}
/// <summary>
/// 顺序队列的存储长度
/// </summary>
public T[] data = new T[maxSize];
//头指针
public int head;
//尾指针
public int tail;
}
#endregion
三：常用操作
队列的操作一般分为：
①： 初始化队列。
②: 出队。
③： 入队。
④： 获取队头。
⑤： 获取队长。
1：初始化队列
这个很简单，刚才也说过了，队列是用一个head和tail的指针来维护。分别设置为0即可。
2：出队
看着“队列”的结构图，大家都知道，出队肯定跟head指针有关，需要做两件事情，
第一： 判断队列是否为空，这个我想大家都知道。
第二： 将head头指针向后移动一位，返回head移动前的元素，时间复杂度为O(1)。
代码段如下：
复制代码 代码如下:
#region 队列元素出队
/// <summary>
/// 队列元素出队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("队列已空，不能进行出队操作");
var single = seqQueue.data[seqQueue.head];
//head指针自增
seqQueue.data[seqQueue.head++] = default(T);
return single;
}
#endregion
3：入队
这个跟”出队“的思想相反，同样也是需要做两件事情。
第一：判断队列是否已满。
第二：将tail指针向后移动一位，时间复杂度为O(1)。
代码段如下：
复制代码 代码如下:
#region 队列元素入队
/// <summary>
/// 队列元素入队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <param name="data"></param>
/// <returns></returns>
public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
{
//如果队列已满，则不能进行入队操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("队列已满,不能入队操作");
//入队操作
seqQueue.data[seqQueue.tail++] = data;
return seqQueue;
}
#endregion
4： 获取队头
知道”出队“和”入队“的原理，相信大家都懂的如何进行”获取队头“操作，唯一不一样的就是
他是只读操作，不会破坏”队列“结构，时间复杂度为O（1）。
代码段如下：
复制代码 代码如下:
#region 获取队头元素
/// <summary>
/// 获取队头元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("队列已空，不能进行出队操作");
return seqQueue.data[seqQueue.head];
}
#endregion
5: 获取队长
大家都知道，我们是用数组来实现队列，所以千万不要想当然的认为数组长度是XXX，
我们维护的是一个head和tail的指针，所以长度自然就是tail-head咯，时间复杂度为O(1)。
代码段如下：
复制代码 代码如下:
/// <summary>
/// 获取队列长度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
{
return seqQueue.tail - seqQueue.head;
}
然后上一下总的运行代码：
复制代码 代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SeqQueue
{
public class Program
{
static void Main(string[] args)
{
SeqQueue<Student> seqQueue = new SeqQueue<Student>();
SeqQueueClass queueManage = new SeqQueueClass();
Console.WriteLine("目前队列是否为空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");
Console.WriteLine("将ID=1和ID=2的实体加入队列");
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一线码农", Age = 23 });
Display(seqQueue);
Console.WriteLine("将队头出队");
//将队头出队
var student = queueManage.SeqQueueOut(seqQueue);
Display(seqQueue);
//获取队顶元素
student = queueManage.SeqQueuePeek(seqQueue);
Console.Read();
}
//展示队列元素
static void Display(SeqQueue<Student> seqQueue)
{
Console.WriteLine("******************* 链表数据如下 *******************");
for (int i = seqQueue.head; i < seqQueue.tail; i++)
Console.WriteLine("ID:" + seqQueue.data[i].ID +
",Name:" + seqQueue.data[i].Name +
",Age:" + seqQueue.data[i].Age);
Console.WriteLine("******************* 链表数据展示完毕 *******************\n");
}
}
#region 学生数据实体
/// <summary>
/// 学生数据实体
/// </summary>
public class Student
{
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
}
#endregion
#region 队列的数据结构
/// <summary>
/// 队列的数据结构
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
{
private const int maxSize = 100;
public int MaxSize
{
get { return maxSize; }
}
/// <summary>
/// 顺序队列的存储长度
/// </summary>
public T[] data = new T[maxSize];
//头指针
public int head;
//尾指针
public int tail;
}
#endregion
#region 队列的基本操作
/// <summary>
/// 队列的基本操作
/// </summary>
public class SeqQueueClass
{
#region 队列的初始化操作
/// <summary>
/// 队列的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
{
seqQueue.head = 0;
seqQueue.tail = 0;
return seqQueue;
}
#endregion
#region 队列是否为空
/// <summary>
/// 队列是否为空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
{
//如果两指针重合，说明队列已经清空
if (seqQueue.head == seqQueue.tail)
return true;
return false;
}
#endregion
#region 队列是否已满
/// <summary>
/// 队列是否已满
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
{
//如果尾指针到达数组末尾，说明队列已经满
if (seqQueue.tail == seqQueue.MaxSize)
return true;
return false;
}
#endregion
#region 队列元素入队
/// <summary>
/// 队列元素入队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <param name="data"></param>
/// <returns></returns>
public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
{
//如果队列已满，则不能进行入队操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("队列已满,不能入队操作");
//入队操作
seqQueue.data[seqQueue.tail++] = data;
return seqQueue;
}
#endregion
#region 队列元素出队
/// <summary>
/// 队列元素出队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("队列已空，不能进行出队操作");
var single = seqQueue.data[seqQueue.head];
//head指针自增
seqQueue.data[seqQueue.head++] = default(T);
return single;
}
#endregion
#region 获取队头元素
/// <summary>
/// 获取队头元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("队列已空，不能进行出队操作");
return seqQueue.data[seqQueue.head];
}
#endregion
/// <summary>
/// 获取队列长度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
{
return seqQueue.tail - seqQueue.head;
}
}
#endregion
}
大家看这张图，不知道可有什么异样的感觉，在这种状态下，我入队操作，发现程序提示队列
已满，但是tnd我这个数组还有一个空间啊，是的，这就是所谓的“假溢出”。
四：循环队列
俗话说的好啊，“没有跨不过的坎”。
1: 概念
之所以叫“循环”，得益于神奇的“%”。他让队列的首位进行相连，形成了一个我们思维中的
“圈圈”。
2：循环公式
tail=(tail+1)%array.Length;
多看几眼，大家就看通了其中循环的道理，我要做成如下的图:
3：对循环的改造
先前看了一些资料，有的压根就是错的，有的说想要循环，就要牺牲一个单位的空间。
我觉得没必要。我既要循环又不牺牲空间，所以反射了一下framework中的Queue类。
改造后代码如下：
复制代码 代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SeqQueue
{
public class Program
{
static void Main(string[] args)
{
SeqQueue<Student> seqQueue = new SeqQueue<Student>();
SeqQueueClass queueManage = new SeqQueueClass();
Console.WriteLine("目前队列是否为空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");
Console.WriteLine("将ID=1，2，3的实体加入队列\n");
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一线码农", Age = 23 });
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 3, Name = "51cto", Age = 23 });
Console.WriteLine("\n当前队列个数：" + queueManage.SeqQueueLen(seqQueue) + "");
Console.WriteLine("\n*********************************************\n");
Console.WriteLine("我要出队了\n");
queueManage.SeqQueueOut(seqQueue);
Console.WriteLine("哈哈，看看跟顺序队列异样之处，我再入队，看是否溢出\n");
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 4, Name = "博客园", Age = 23 });
Console.WriteLine("\n....一切正常，入队成功");
Console.WriteLine("\n当前队列个数：" + queueManage.SeqQueueLen(seqQueue) + "");
Console.Read();
}
}
#region 学生数据实体
/// <summary>
/// 学生数据实体
/// </summary>
public class Student
{
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
}
#endregion
#region 队列的数据结构
/// <summary>
/// 队列的数据结构
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
{
private const int maxSize = 3;
public int MaxSize
{
get { return maxSize; }
}
/// <summary>
/// 顺序队列的存储长度
/// </summary>
public T[] data = new T[maxSize];
//头指针
public int head;
//尾指针
public int tail;
//队列中有效的数字个数
public int size;
}
#endregion
#region 队列的基本操作
/// <summary>
/// 队列的基本操作
/// </summary>
public class SeqQueueClass
{
#region 队列的初始化操作
/// <summary>
/// 队列的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
{
seqQueue.size = seqQueue.head = seqQueue.tail = 0;
return seqQueue;
}
#endregion
#region 队列是否为空
/// <summary>
/// 队列是否为空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
{
//如果两指针重合，说明队列已经清空
if (seqQueue.size == 0)
return true;
return false;
}
#endregion
#region 队列是否已满
/// <summary>
/// 队列是否已满
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
{
//采用循环队列后，头指针
if (seqQueue.size == seqQueue.MaxSize)
return true;
return false;
}
#endregion
#region 队列元素入队
/// <summary>
/// 队列元素入队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <param name="data"></param>
/// <returns></returns>
public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
{
//如果队列已满，则不能进行入队操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("队列已满，还入啥队列啊！");
//采用循环队列,必须先赋值，在自增tail指针
seqQueue.data[seqQueue.tail] = data;
seqQueue.tail = (seqQueue.tail + 1) % seqQueue.MaxSize;
//队列实际元素增加
seqQueue.size++;
return seqQueue;
}
#endregion
#region 队列元素出队
/// <summary>
/// 队列元素出队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("队列已空，大哥，不要在出队了！");
//循环队列出队，展现的是head的灵活性
seqQueue.head = (seqQueue.head + 1) % seqQueue.MaxSize;
//队列实际元素递减
seqQueue.size--;
return seqQueue.data[seqQueue.head];
}
#endregion
#region 获取队头元素
/// <summary>
/// 获取队头元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("队列已空，不能进行出队操作");
return seqQueue.data[seqQueue.head];
}
#endregion
#region 获取队列长度
/// <summary>
/// 获取队列长度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
{
return seqQueue.size;
}
#endregion
}
#endregion
}
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。
苹果官方表示：
在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。
探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。
Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。
RTX 5090要首发 性能要翻倍！三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB，每个模块容量为2GB。其速度预设为32 Gbps（PAM3），但也可以降至28 Gbps，以提高产量和初始阶段的整体性能和成本效益。
据三星表示，GDDR7内存的能效将提高20%，同时工作电压仅为1.1V，低于标准的1.2V。通过采用更新的封装材料和优化的电路设计，使得在高速运行时的发热量降低，GDDR7的热阻比GDDR6降低了70%。