Queueが空のときにDequeueメソッドを呼び出すと、null/Nothingが返されるのではなく、例外InvalidOperationExceptionがスローされます。 このため、Dequeueメソッドの戻り値からQueueが空だったかどうかを判断することはできません。

Queueが空の状態でDequeueメソッドを呼び出すとInvalidOperationExceptionとなる
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    var q = new Queue<string>();

    Console.WriteLine($"Count = {q.Count}"); // 0

    // Queueが空の状態でDequeue操作を行うとInvalidOperationExceptionがスローされる
    Console.WriteLine(q.Dequeue());
  }
}
実行結果
Count = 0
Unhandled exception. System.InvalidOperationException: Queue empty.
   at System.Collections.Generic.Queue`1.ThrowForEmptyQueue()
   at System.Collections.Generic.Queue`1.Dequeue()
   at Sample.Main() in /home/smdn/samplecodes/dotnet/cs/test.cs:line 12

Queueが空かどうかに関わらず、例外をスローせずにポップ操作を試行するメソッドとしてTryDequeueメソッドが用意されています。

このほか、DequeueメソッドでInvalidOperationExceptionを避けるには、Dequeueメソッドを呼び出す前にCountプロパティを参照して、要素が1つ以上格納されているかチェックするようにします。