C# 算法系列一基本数据结构

```    /// <summary>
/// 自定义队列
/// </summary>
public class Queue
{
private object[] _array;

/// <summary>
/// 队列头
/// </summary>

/// <summary>
/// 队列尾
/// </summary>
private int _tail;

/// <summary>
/// 当前数组的长度
/// </summary>
private int _size;

/// <summary>
/// 使用默认构造函数时,给定队列默认的长度4
/// </summary>
public Queue() : this(4)
{

}

/// <summary>
/// 初始化指定容量的队列
/// </summary>
/// <param name="capacity"></param>
public Queue(int capacity)
{
if (capacity < 0)
{
throw new Exception("初始容量不能小于0");
}
_array = new object[capacity];
_tail = 0;
_size = 0;
}

/// <summary>
/// 入队
/// </summary>
public virtual void Enqueue(object obj)
{
_array[_tail] = obj;
_tail = _tail + 1;
_size++;
}

/// <summary>
/// 出队
/// </summary>
/// <returns></returns>
public virtual object Dequeue()
{
if (Count == 0)
{
throw new InvalidOperationException("当前队列为空,无法执行Dequeue操作");
}

_size--;
return result;
}

/// <summary>
/// 当前队列的长度
/// </summary>
public int Count { get { return _size; } }
}```

```    class Program
{
static void Main(string[] args)
{
var q = new Queue();
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);
q.Enqueue(4);
Console.WriteLine("出队:{0},{1},{2},{3}", q.Dequeue(), q.Dequeue(), q.Dequeue(), q.Dequeue());
}
}```

```    /// <summary>
/// 自定义队列
/// </summary>
public class Queue
{
private object[] _array;

/// <summary>
/// 队列头
/// </summary>

/// <summary>
/// 队列尾
/// </summary>
private int _tail;

/// <summary>
/// 当前数组的长度
/// </summary>
private int _size;

/// <summary>
/// 使用默认构造函数时,给定队列默认的长度32
/// </summary>
public Queue() : this(4)
{

}

/// <summary>
/// 初始化指定容量的队列
/// </summary>
/// <param name="capacity"></param>
public Queue(int capacity)
{
if (capacity < 0)
{
throw new Exception("初始容量不能小于0");
}
_array = new object[capacity];
_tail = 0;
_size = 0;
}

/// <summary>
/// 入队
/// </summary>
public virtual void Enqueue(object obj)
{
if (_array.Length == _size)
{
int capacity = _array.Length * 2;
SetCapacity(capacity);
}
_array[_tail] = obj;
_tail = _tail + 1;
_size++;
}

/// <summary>
/// 出队
/// </summary>
/// <returns></returns>
public virtual object Dequeue()
{
if (Count == 0)
{
throw new InvalidOperationException("当前队列为空,无法执行Dequeue操作");
}

_size--;
return result;
}

/// <summary>
/// 当前队列的长度
/// </summary>
public int Count { get { return _size; } }

/// <summary>
/// 重新设定原始数组的容量
/// </summary>
private void SetCapacity(int capacity)
{
var newArray = new object[capacity];
Array.Copy(_array,newArray, _array.Length);
_array = newArray;
_tail = _size;
}
}```

ok,现在每次都会以原数组*2的长度扩展原始数组,但是还是有问题,如果这中间存在出队,实际的_size会减一,但是数组实际的长度还是为原来的,区别就是出队的那个元素的位置会被设置为null,会存在以下bug：

```            var q = new Queue();
q.Enqueue(1);
q.Dequeue();
q.Enqueue(2);
q.Enqueue(3);
q.Enqueue(4);
q.Enqueue(5);
Console.WriteLine("出队:{0},{1},{2},{3}", q.Dequeue(), q.Dequeue(), q.Dequeue(), q.Dequeue());

0 条评论