Create custom Queue class with O(1) Enqueue and O(1) Dequeue
This is your bottleneck in retrieving the new head at removal, which can not be avoided in a Singly-Linked structure, so it's \$O(n)\$.


while (temp.Next != head)  // Get the previous Node of the head
    temp = temp.Next;



Doubly-Linked

If you want fast removal \$O(1)\$, you can do so at the cost of slightly slower insertion. You'd need to augment the queue to a doubly linked queue:

var previous = head.Previous;
head.Previous = null;
head = previous;
head.Next = null;


Make sure at insertion, you'll set both Previous as Next references on the relevant nodes.

Circular Doubly-Linked

If you make the queue circular, you don't even need to store the tail, only the head. The tail would be head.Previous; In case of a single element, since it's circular, head.Previous would point to head. Make sure in iterators to terminate at head, instead of at null.