数据结构笔记5 队列

队列的概念和定义

定义：

队列是只允许在一端进行插入，另一端进行删除的线性表。

他所有的插入操作均限定在表的一端进行，该端称为队尾。

所有的删除操作则限定在另一端进行，该端则称为对头。

基本操作：

• 入队：将一个数据插入到队尾的操作。
• 出队：读取队头结点数据并删除该结点的操作

顺序队列的两个指示器与队列中数据元素的关系图

循环顺序队列

循环顺序队列操作

 

队列的实现

using System;
namespace EveryDayStudy.数据结构
{
public class DAPQueue
{
private object[] _array; //存放元素的数组
private int _growFactor; //增长因子
private int _head;//队头指针
private const int _MinimumGrow = 4;//最小增长值
private const int _ShrinkThreshold = 0x20;//初始容量
private int _size;//指示元素个数
private int _tail;//队尾指针
public DAPQueue() : this(_ShrinkThreshold, 2f)
{
}
public DAPQueue(int capacity,float growFactor)
{
if (capacity<0)
{
throw new ArgumentOutOfRangeException("capacity","初始容量不能小于0");
}
if (growFactor<1.0|| growFactor>10.0)
{
throw  new ArgumentOutOfRangeException("growFactor","增长因子必须在1.0到是10.0之间");
}
_array = new object[capacity];
_head = 0;
_tail = 0;
_size = 0;
_growFactor = (int) (growFactor*100f);
}
/// <summary>
/// 出队
/// </summary>
/// <returns></returns>
public virtual object Dequeue()
{
if (_size ==0)
{
throw  new InvalidOperationException("队列为空。"); //队下溢
}
object obj2 = _array[_head];
_array[_head] = null;//删除出队指针
_head = (_head + 1)%_array.Length; //移动队头指针
_size--;
return obj2;
}
/// <summary>
/// 入队
/// </summary>
/// <param name="obj"></param>
public virtual void Enqueue(object obj)
{
if (_size == _array.Length)
{
int capacity = (int)((_array.Length*_growFactor)/100L);
if (capacity <(_array.Length+_MinimumGrow))
{
capacity = _array.Length + _MinimumGrow;
}
SetCapacity(capacity);
}
_array[_tail] = obj;
_tail = (_tail + 1)%_array.Length;
_size++;
}
/// <summary>
/// 内存搬家
/// </summary>
/// <param name="capacity"></param>
private void SetCapacity(int capacity)
{
//在内存中开辟新空间
object[] destinationArray = new object[capacity];
if (_head<_tail)
{
//当头指针在尾指针前面时
Array.Copy(_array,_head,destinationArray,0,_size);
}
//当头指针在尾指针后面时
else
{
//先搬头指针后面的元素再搬数组头部到尾指针之间的元素
Array.Copy(_array, _head, destinationArray, 0, _array.Length - _head);
Array.Copy(_array, 0, destinationArray, _array.Length - _head, _tail);
}
_array = destinationArray;
_head = 0;
_tail = (_size == capacity) ? 0 : _size;
}
/// <summary>
/// 元素个数
/// </summary>
public  virtual  int Count
{
get
{
return _size;
}
}
}
}