渣渣写算法之队列
标签：pre line item ret throw cep ISE class ons
队列 Queue
队列可以用数组和链表来实现
考虑到队列的移除时数组数据的调整，分成了几个情况
①移动数组，这样当然来讲，是性能不咋好的，通过一个指针并移动整体位置来实现，从一个角度解决了由于出对导致非环形的数组中无用项的问题
public class ArrayQueue
{
public int Length
{
get
{
return curIndex + 1;
}
}
private int maxSize = 100;
private int curIndex = -1;
private T[] _data = null;
public ArrayQueue()
{
_data = new T[maxSize];
}
public void Clear()
{
curIndex = -1;
}
public void EnQueue(T item)
{
curIndex++;
if (curIndex >= maxSize)
{
Console.WriteLine("队列已满");
return;
}
_data[curIndex] = item;
}
public T DeQueue()
{
if (curIndex > -1)
{
var data = _data[0];
if (curIndex > 0)
{
for (int i = 1; i
②环形数组实现1，利用俩指针配合来完成数组的利用，用count统计控制当前有效的个数
public class CircleArrayQueue
{
private int maxSize = 100;
private int firstIndex = -1;
private int lastIndex = -1;
private T[] _data = null;
public CircleArrayQueue(int setMaxSize = 4)
{
maxSize = setMaxSize;
_data = new T[maxSize];
}
private bool isFull()
{
return Length== maxSize;
}
private bool isEmpty()
{
return Length==0;
}
public void Clear()
{
firstIndex = lastIndex = -1;
Length = 0;
}
public int Length { get; private set; } = 0;
public void EnQueue(T item)
{
if (isFull())
{
Console.WriteLine("已满");
return;
}
Length++;
lastIndex++;
if (lastIndex >= maxSize)
{
lastIndex = 0;
}
_data[lastIndex] = item;
if (firstIndex == -1)
{
firstIndex = 0;
}
}
public T DeQueue()
{
if (isEmpty())
{
throw new Exception("没有元素");
}
Length--;
var data = _data[firstIndex];
firstIndex++;
if (firstIndex >= maxSize)
{
firstIndex = 0;
}
return data;
}
}
③环形数组实现2，其实两个指针也可以统计出队列中有效项的个数，不用额外定义一个count个数
public class CircleArray2Queue
{
private int maxSize = 100;
private int firstIndex = -1;
private int lastIndex = -1;
private T[] _data = null;
public CircleArray2Queue(int setMaxSize = 4)
{
maxSize = setMaxSize;
_data = new T[maxSize];
}
private bool isFull()
{
return (lastIndex + 1) % maxSize == firstIndex;
}
private bool isEmpty()
{
return firstIndex == -1||lastIndex == firstIndex;
}
public int Length
{
get
{
return firstIndex == -1 ? 0 : (lastIndex + maxSize - firstIndex) % maxSize + 1;
}
}
public void Clear()
{
firstIndex = lastIndex = -1;
}
public void EnQueue(T item)
{
if (isFull())
{
Console.WriteLine("已满");
return;
}
lastIndex++;
if (lastIndex >= maxSize)
{
lastIndex = 0;
}
_data[lastIndex] = item;
if (firstIndex == -1)
{
firstIndex = 0;
}
}
public T DeQueue()
{
if (isEmpty())
{
throw new Exception("没有元素");
}
var data = _data[firstIndex];
if (firstIndex != lastIndex)
{
firstIndex++;
if (firstIndex >= maxSize)
{
firstIndex = 0;
}
}
return data;
}
}
④ 当然 ，还可以使用单链表来实现，通过链表的指针指向下一个，来找下一个元素，出队的时候修正链表指针即可
public class CircleLinkQueue
{
private class Item
{
public Item Next;
public T Data;
}
private Item curItem = null;
private Item firstItem = null;
public int Length { get; private set; } = 0;
public void Clear()
{
Length = 0;
firstItem = null;
curItem = null;
}
public void EnQueue(T item)
{
Length++;
var d = new Item()
{
Data = item
};
if (curItem == null)
{
firstItem = d;
}
else
{
curItem.Next = d;
}
curItem = d;
}
public T DeQueue()
{
if (Length > 0 && firstItem != null)
{
var dd = firstItem.Data;
Length--;
firstItem = firstItem.Next;
return dd;
}
else
{
throw new Exception("No Elem");
}
}
}
相比较于数组本身，数组有天然的指针结构，相邻的元素有着天然的联系，但是维护起来需要一定的逻辑，所以链表就定义了一个结构，包含了对元素本身和执行下一个元素，来方便指定联系，链表中相连的元素在内部可能是不连续的。
渣渣写算法之队列
标签：pre line item ret throw cep ISE class ons
原文地址：https://www.cnblogs.com/wwkk/p/13199211.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
渣渣写算法之队列
文章链接：http://soscw.com/essay/81753.html
评论