算法系列15天速成 第九天 队列
一:概念
队列是一个”先进先出“的线性表,牛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
}
上一篇: 算法系列15天速成 第七天 线性表【上】
下一篇: 减肥吃什么米让减肥变得不那么辛苦