Un HashSet<T> guarda cada valor una sola vez y responde a Contains en tiempo constante. Add devuelve false cuando el valor ya estaba, así que detectar duplicados cabe en una línea. Como los diccionarios, los conjuntos aceptan un comparador: new HashSet<string>(StringComparer.OrdinalIgnoreCase).
Una Queue<T> es el primero que entra, el primero que sale: Enqueue añade al final y Dequeue saca del principio, como una fila en un mostrador. Una Stack<T> es el último que entra, el primero que sale: Push y Pop, como un historial de deshacer. Llamar a Dequeue o Pop sobre una colección vacía lanza InvalidOperationException, así que comprueba Count o usa TryDequeue y TryPop.
Elegir la colección adecuada a menudo te ahorra un bucle: un conjunto sustituye a las búsquedas de "¿ya lo he visto?" y una cola mantiene el orden de llegada sin llevar la cuenta de índices.
Un conjunto para "¿ya lo he visto?", una cola para el orden de llegada y una pila para deshacer.