使用链表的队列实现:C#

Question

我正在学习数据结构。今天，我想使用链表实现队列。因为我们有队列入口点的 FRONT 和 REAR 第一个索引。如果有人要求我实现带有链表的队列，请确认我的以下实现(我能够在没有 REAR 对象的情况下实现队列目标。

此实现有效吗？

class Queue
{
Node head;
class Node
{
public int Value;
public Node next;
public Node()
{
next = null;
}
}
public void addElement(int val)
{
if (head == null)
{
Node temp = new Node();
temp.Value = val;
head = temp;
return;
}
Node tempNode = head;
while (tempNode.next != null)
{
tempNode = tempNode.next;
}
Node newElement = new Node();
newElement.Value = val;
tempNode.next = newElement;
}
public void Dequeue()
{
if (head != null)
{
if (head.next != null)
{
head = head.next;
return;
}
head = null;
}
}
}
class Program
{
static void Main(string[] args)
{
Queue queue = new Queue();
queue.addElement(10);
queue.addElement(20);
queue.addElement(30);
queue.addElement(40);
queue.Dequeue();
queue.Dequeue();
queue.Dequeue();
queue.Dequeue();
}
}

Answer 1

好吧，如果我们想拥有前端和后端，让我们拥有它们：

private Node m_Head;
private Node m_Tail;

你只有一个Node head;领域，这就是为什么你的实现至少效率低下：你O(N)时间复杂度来addElement：

...
while (tempNode.next != null)
{
tempNode = tempNode.next;
}
...

当你可以轻松拥有O(1)

我建议使用像Enqueue这样的典型名称而不是addElement并且有Try方法(通常，如果队列为空，我们不希望出现异常(。最后，让我们使用泛型：MyQueue<T>其中T是项的类型。

public class MyQueue<T> {
private class Node {
public Node(Node next, T value) {
Next = next;
Value = value;
}
public Node Next { get; internal set; }
public T Value { get; }
}
private Node m_Head;
private Node m_Tail;
public void Enqueue(T item) {
Node node = new Node(null, item);
if (m_Tail == null) {
m_Head = node;
m_Tail = node;
}
else {
m_Tail.Next = node;
m_Tail = node;
}
}
public bool TryPeek(out T item) {
if (m_Head == null) {
item = default(T);
return false;
}
item = m_Head.Value;
return true;
}
public T Peek() {
if (m_Head == null)
throw new InvalidOperationException("Queue is empty.");
return m_Head.Value;
}
public bool TryDequeue(out T item) {
if (m_Head == null) {
item = default(T);
return false;
}
item = m_Head.Value;
m_Head = m_Head.Next;
return true;
}
public T Dequeue() {
if (m_Head == null)
throw new InvalidOperationException("Queue is empty.");
T item = m_Head.Value;
m_Head = m_Head.Next;
return item;
}
}