There is an strong feel ofShlemiel the painter’s algorithm in removing entries from the queue. The longer the queue, the longer it takes. Adding a reference to the tail will prevent this.

Also, this is pretty much a textbook example of something to which we can apply generics.

public class Queue<T>{    private readonly static Node<T> HeadNode = new Node<T>(default(T));    private readonly Node<T> _head;    private Node<T> _tail;    public Queue()    {        _head = HeadNode;        _tail = _head;    }    public int Count { get; private set; }    public void Enqueue(T value)    {        _tail = _tail.Add(value);        Count++;    }    public T Dequeue()    {        Count--;        return _head.Remove();              }    public override string ToString()    {        return string.Join(" ", GetValues().Select(v => v.ToString()));    }    private IEnumerable<T> GetValues()    {        var current = _head.Next;        while(current != null)        {           yield return current.Value;           current = current.Next;        }    }    # region Node    private class Node<TNode>    {        public Node(T value)        {           Value = value;        }        public T Value { get;  }        public Node<T> Next { get; private set; }        public Node<T> Add(T value)        {           Next = new Node<T>(value);           return Next;        }        public T Remove()        {           if(Next == null)           {              throw new InvalidOperationException();           }           var ret = Next.Value;           Next = Next.Next;           return ret;        }    }    #endregion }

• There is no need for theNode class to be visible outside theQueue. It is an implementation detail of theQueue.
• Adding the permanent_head removes any need for null checks
• size andCount can be merged.
• Moving theAdd() andRemove() operations into theNode defines the interface for theNode in terms of operations one can perform on it, rather than in terms of the visible members. We can't erroneously scribble on either theValue or theNext reference.

• \$\begingroup\$the "permanent_head" is often called "sentinel"\$\endgroup\$

  Vogel612

  – Vogel612

  2017-03-25 18:19:26 +00:00

  CommentedMar 25, 2017 at 18:19

Good

• You are following the .NET Naming Guidelines
• The variables are in the correct scope

Review

Omitting braces{} although they might be optional can lead to hidden and therfore hard to track down bugs. I would like to encourage you to always use them.

Regardingpublic string PrintElements() I would suggest to simply overrideToString() which is more idiomatic.

If we take a closer look at theEnqueue(int n) method we notice that the difference between theif and theelse part is simply the value ofnext. We can remove this code duplication by adding a variableNode node and assignhead like so

public void Enqueue(int n){    Node node = head;    head = new Node    {        value = n,        next = node    };        size++;}

much better, isn't it ?

A C# developer would expect from aQueue that if theQueue is empty (in your case ifsize == 0) a call toDequeue() would throw anInvalidOperationException.

In addition to excellent answers above, I'd addinterface implementation - a typical .NET/C# generic data structure, such as theSystem.Collections.Generic.Queue<T> class, can be passed in to functions or stored in other data containers as anIEnumerable<T>. Here's an example implementation ofIEnumerable<T> (you'd need to make your queue generic):

public class Queue<T> : IEnumerable<T>{    //...    //Your code    //...    public IEnumerator<T> GetEnumerator()    {        return new QueueEnumerator(this);    }    IEnumerator IEnumerable.GetEnumerator()    {        return GetEnumerator();    }    //Inner class    private class QueueEnumerator : IEnumerator<T>    {        private Queue<T> queue;        private Node<T> currentNode;        public QueueEnumerator(Queue<T> queue)        {            this.queue = queue;        }        public T Current => currentNode.value;        object IEnumerator.Current => Current;        public void Dispose() { }        public bool MoveNext()        {            if(queue.head == null)            {                return false;            }            if(currentNode == null)            {                currentNode = queue.head;                return true;            }            if(currentNode.next == null)            {                return false;            }            currentNode = currentNode.next;            return true;        }        public void Reset()        {            currentNode = null;        }    }}

NOTE: Since yourEnqueue method insertsbefore head, you'd need to modify the enumeration accordingly, or changeEnqueue method to insertafter head, or make you backing linked list a doubly-linked list (so you can traverse it backwards from tail to head).

• c#
• unit-testing
• linked-list
• queue