说明
（此系列帖子记录数据结构学习成果,如侵犯视频作者权益，立删)
视频链接:离忧夏天C#数据结构
本文实现队列需要用到动态数组ArrayList和单链表的相关知识，详细请看：C#数据结构专栏
文章目录
一：队列的基本概念
队列是一种遵循先进先出原则的线性表
二：队列的基本操作
- 入队（Enqueue）
- 出队（DeQueue）
- 获取队列的大小（Count）
- 检查队列是否为空（IsEmpty）
- 查看队头元素（GetFirst）
实现队列的接口
public interface IQueue<T>
{
//查看元素数量
int Count { get; }
//判空
bool IsEmpty { get; }
//入队
void Enqueue(T data);
//出队
T Dequeue();
//查看队首元素
T Peek();
}
三：队列的实现
1.数组队列(由动态数组实现)
| 数组队列 | 时间复杂度 |
|---|---|
| 入队（Enqueue） | O（1） |
| 出队（DeQueue） | O（n） |
| 获取队列的大小（Count） | O（1） |
| 检查队列是否为空（IsEmpty） | O（1） |
| 查看队头元素（GetFirst） | O（1） |
public class Array1Queue<T> : IQueue<T>
{
private Array1<T> arr;
public int Count => arr.Count;
public bool IsEmpty => arr.IsEmpty;
public Array1Queue(int capacity)
{
arr = new Array1<T>(capacity);
}
public Array1Queue()
{
arr = new Array1<T>();
}
//入队
public void Enqueue(T data)
{
arr.AddLast(data);
}
//出队
public T Dequeue()
{
return arr.RemoveFirst();
}
//查看队首元素
public T Peek()
{
return arr.GetFirst();
}
public override string ToString()
{
return "Queue: Head" + arr.ToString() + "Tail";
}
}
2.循环队列(由循环数组实现)
循环数组其中的元素可以在数组的末端重新改回到起始位置，其头尾相连形成一个闭环。
- 头部由fist指针标识
- 尾部由last指针标识
- 当到达数组的末尾时,last指针会重写指向数组的起始位置，从而充分利用整个数组空间，避免了不必要的内存浪费。
- 其中需要取余操作是必须的，这样可以保证数组的循环，即==（last+1）% data.length==
循环数组的实现
public class Array2<T>
{
private T[] data; //存储元素
private int first;//记录头部
private int last;//记录尾部
private int size;//当前元素个数
public Array2(int capacity)
{
data = new T[capacity];
first = 0;
last = 0;
size = 0;
}
public Array2() : this(10) { }
public int Count => size;
public bool IsEmpty => size == 0;
//添加元素
public void AddLast(T newData)
{
if (size == data.Length)
ResetCapacity(2 * data.Length);
data[last] = newData;
last = (last+1)%data.Length;
size++;
}
//删除元素
public T RemoveFirst()
{
if (IsEmpty)
throw new Exception("数组为空");
T res = data[first];
data[first] = default(T);
first = (first + 1) % data.Length;
size--;
if (size == data.Length / 4)
ResetCapacity(data.Length / 2);
return res;
}
//获取元素
public T GetFirst()
{
if (IsEmpty)
throw new Exception("数组为空");
return data[first];
}
private void ResetCapacity(int newCapacity)
{
T[] newData = new T[newCapacity];
for (int i = 0; i < size; i++)
newData[i] = data[(first + i) % data.Length];
data = newData;
first = 0;
last = size;
}
public override string ToString()
{
StringBuilder res = new StringBuilder();
res.Append("[");
for(int i = 0; i < size; i++)
{
res.Append(data[(first + i) % data.Length]);
if((first + i + 1) % data.Length != last)
res.Append(", ");
}
res.Append("]");
return res.ToString();
}
}
循环队列的实现
| 循环队列 | 时间复杂度 |
|---|---|
| 入队（Enqueue） | O（1） |
| 出队（DeQueue） | O（1） |
| 获取队列的大小（Count） | O（1） |
| 检查队列是否为空（IsEmpty） | O（1） |
| 查看队头元素（GetFirst） | O（1） |
public class Array2Queue<T> : IQueue<T>
{
private Array2<T> arr;
public Array2Queue(int capacity)
{
arr = new Array2<T>(capacity);
}
public Array2Queue()
{
arr = new Array2<T>();
}
public int Count => arr.Count;
public bool IsEmpty => arr.IsEmpty;
//入队,往队尾添加元素O(1)
public void Enqueue(T data)
{
arr.AddLast(data);
}
//出队，删除队首的元素O(1)
public T Dequeue()
{
return arr.RemoveFirst();
}
//查看队首元素O(1)
public T Peek()
{
return arr.GetFirst();
}
public override string ToString()
{
return "Queue: front" + arr.ToString() + "Tail";
}
}
3.链表队列(由只带头指针的链表实现)
因为在向单链表添加元素的过程中，每次添加元素，我们都需要用一层for循环遍历到链表尾部，然后再添加元素，因此入队的时间复杂度是O(n)
| 链表队列 | 时间复杂度 |
|---|---|
| 入队（Enqueue） | O(n) |
| 出队（DeQueue） | O（1） |
| 获取队列的大小（Count） | O（1） |
| 检查队列是否为空（IsEmpty） | O（1） |
| 查看队头元素（GetFirst） | O（1） |
public class LinkedList1Queue<T> : IQueue<T>
{
private LinkedList1<T> list;
public LinkedList1Queue()
{
list = new LinkedList1<T>();
}
public int Count => list.Count;
public bool IsEmpty => list.IsEmpty;
//删除队列头部=>删除链表头部O(1)
public T Dequeue()
{
return list.RemoveFirst();
}
//添加到队列尾部=>添加链表尾部O(n)
public void Enqueue(T data)
{
list.AddLast(data);
}
//查看队列头部==查看链表头部O(1
public T Peek()
{
return list.GetFirst();
}
public override string ToString()
{
return "Queue front" + list.ToString() +"tail";
}
}
4.链表队列(由带头尾指针的链表实现)
和只有头指针的单链表类似，在尾指针添加元素，只需要让尾指针的下一个节点为newNode，并让newNode为尾指针即可
即tail.next = node; tail = node;
| 链表队列（带尾指针） | 时间复杂度 |
|---|---|
| 入队（Enqueue） | O(1) |
| 出队（DeQueue） | O（1） |
| 获取队列的大小（Count） | O（1） |
| 检查队列是否为空（IsEmpty） | O（1） |
| 查看队头元素（GetFirst） | O（1） |
带尾指针的单链表的实现
public class LinkedList02<T>
{
private class Node
{
public T data;
public Node next;
public Node(T data)
{
this.data = data;
this.next = null;
}
public Node(T data , Node next)
{
this.data = data;
this.next = next;
}
public override string ToString()
{
return base.ToString();
}
}
private Node head;
private Node tail;
private int size;
public LinkedList02()
{
this.head = null;
this.tail = null;
this.size = 0;
}
public int Count => size;
public bool IsEmpty => size == 0;
//链表尾部添加元素
public void AddLast(T newData)
{
Node node = new Node(newData);
if (IsEmpty)
{
head = node;
tail = node;
}
else
{
tail.next = node;
tail = node;
}
size++;
}
//链表头部删除元素
public T RemoveFirst()
{
if (IsEmpty)
throw new InvalidOperationException("链表为空");
T deldata = head.data;
head = head.next;
size--;
if(head == null)
tail = null;
return deldata;
}
//查看头部
public T GetFirst()
{
if (IsEmpty)
throw new InvalidOperationException("链表为空");
return head.data;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
Node cur = head;
while (cur != null)
{
sb.Append(cur.data + "->");
cur = cur.next;
}
sb.Append("Null");
return sb.ToString();
}
}
通过带有尾指针的链表实现的队列
public class LinkedList2Queue<T> : IQueue<T>
{
private LinkedList02<T> list;
public LinkedList2Queue()
{
list = new LinkedList02<T>();
}
public int Count => list.Count;
public bool IsEmpty => list.IsEmpty;
//入队
public void Enqueue(T data)
{
list.AddLast(data);
}
//出队
public T Dequeue()
{
return list.RemoveFirst();
}
//查看队首元素
public T Peek()
{
return list.GetFirst();
}
public override string ToString()
{
return "Queue front" + list.ToString() +"tail";
}
}
四：性能分析比较
对于队列的测试，编写TestQueue方法
//测试队列的性能
private static long TestQueue(IQueue<int> queue, int N)
{
Stopwatch t = new Stopwatch();
t.Start();
for (int i = 0; i < N; i++)
{
queue.Enqueue(i);
}
for (int i = 0; i < N; i++)
{
queue.Dequeue();
}
t.Stop();
return t.ElapsedMilliseconds;
}
数组队列 VS 循环队列(win)
int N = 100000;
//数组队列
Array1Queue<int> array1Queue = new Array1Queue<int>();
long t1 = TestQueue(array1Queue, N);
Console.WriteLine("Array1Queue Time:" + t1+"ms");
//循环队列
Array2Queue<int> array2Queue = new Array2Queue<int>();
long t2 = TestQueue(array2Queue, N);
Console.WriteLine("Array2Queue Time:" + t2 + "ms");
Console.ReadKey();
我们可以清楚的看到：循环队列的性能对于数组队列是大幅度提升的。
由只有头指针链表实现的队列 VS 由具有头尾指针链表实现的队列(win)
int N = 100000;
//链表队列(头指针)
LinkedList1Queue<int> linkedList1Queue = new LinkedList1Queue<int>();
long t1 = TestQueue(linkedList1Queue, N);
Console.WriteLine("linkedList1Queue Time:" + t1+"ms");
//链表队列(头尾指针)
LinkedList2Queue<int> linkedList2Queue = new LinkedList2Queue<int>();
long t2 = TestQueue(linkedList2Queue, N);
Console.WriteLine("linkedList2Queue Time:" + t2 + "ms");
Console.ReadKey();
我们可以清楚的看到，通过优化链表，使得具有尾指针，并通过尾指针添加元素，使得性能对于普通的单链表是大幅度提升的。