|
队列是一个”先进先出“的线性表，牛X的名字就是“First in First Out(FIFO)”，生活中有很多这样的场景，比如读书的时候去食堂打饭时的”排队“。当然我们拒绝插队。
二：存储结构
前几天也说过，线性表有两种”存储结构“，① 顺序存储,②链式存储。当然“队列”也脱离不了这两种服务，这里我就分享一下“顺序存储”。
顺序存储时，我们会维护一个叫做”head头指针“和”tail尾指针“，分别指向队列的开头和结尾。
代码段如下：
复制代码 代码如下:
#region 队列的数据结构
/// <summary>
/// 队列的数据结构
/// </summary>
/// <typeparam></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></typeparam>
/// <param></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></typeparam>
/// <param></param>
/// <param></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></typeparam>
/// <param></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)。
代码段如下：
复制代码 代码如下: （编辑：焦作站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
