6.5 - Queue<T>

A Queue<T> is a specialized collection that follows the First-In-First-Out (FIFO) principle: the first element added to the queue is the first one to be removed. Think of a queue like a line of people waiting for a service—the person who arrives first gets served first.

Why Use Queue<T>?

Queues are ideal for scenarios where you need to:

1. Process items in order of arrival: Ensuring that elements are handled in the sequence they were received.
2. Implement waiting lists: Managing entities that need to be processed in a specific order.
3. Buffer data: Temporarily storing data that will be processed later in the same order it was received.
4. Implement breadth-first algorithms: Used in pathfinding, tree traversal, and other algorithms.

Common game development uses include:

• Command queues for turn-based games
• Message or event queues
• Animation sequences
• AI action planning
• Level loading queues
• Sound effect playback queues

Creating and Initializing Queues

Here's how to create and initialize a Queue<T>:

Basic Creation

// Create an empty queue of integers
Queue<int> numberQueue = new Queue<int>();

// Create an empty queue of strings
Queue<string> messageQueue = new Queue<string>();

// Create a queue with an initial capacity
Queue<GameObject> objectQueue = new Queue<GameObject>(100);

Initializing with Elements

// Initialize from an existing collection
int[] numbers = { 1, 2, 3, 4, 5 };
Queue<int> numberQueue = new Queue<int>(numbers);

// Initialize from a list
List<string> messages = new List<string> { "Hello", "World", "!" };
Queue<string> messageQueue = new Queue<string>(messages);

Queue Operations

Queues have a few core operations that align with their FIFO nature:

Adding Elements (Enqueue)

To add an element to the end of the queue:

Queue<string> commandQueue = new Queue<string>();

// Add elements to the queue
commandQueue.Enqueue("Move Forward");
commandQueue.Enqueue("Turn Left");
commandQueue.Enqueue("Attack");

Console.WriteLine($"Queue count: {commandQueue.Count}"); // 3

Removing Elements (Dequeue)

To remove and return the element at the beginning of the queue:

Queue<string> commandQueue = new Queue<string>();
commandQueue.Enqueue("Move Forward");
commandQueue.Enqueue("Turn Left");
commandQueue.Enqueue("Attack");

// Process commands in order
string firstCommand = commandQueue.Dequeue(); // "Move Forward"
Console.WriteLine($"Executing: {firstCommand}");

string secondCommand = commandQueue.Dequeue(); // "Turn Left"
Console.WriteLine($"Executing: {secondCommand}");

Console.WriteLine($"Remaining commands: {commandQueue.Count}"); // 1

caution

Calling Dequeue() on an empty queue will throw an InvalidOperationException. Always check if the queue has elements before dequeuing.

Viewing the Next Element (Peek)

To view the element at the beginning of the queue without removing it:

Queue<string> commandQueue = new Queue<string>();
commandQueue.Enqueue("Move Forward");
commandQueue.Enqueue("Turn Left");

// Look at the next command without removing it
string nextCommand = commandQueue.Peek(); // "Move Forward"
Console.WriteLine($"Next command: {nextCommand}");

// The queue is unchanged
Console.WriteLine($"Queue count: {commandQueue.Count}"); // 2

caution

Like Dequeue(), calling Peek() on an empty queue will throw an InvalidOperationException.

Checking and Clearing

Additional useful operations:

Queue<string> commandQueue = new Queue<string>();
commandQueue.Enqueue("Move Forward");
commandQueue.Enqueue("Turn Left");

// Check if the queue contains a specific element
bool containsTurnLeft = commandQueue.Contains("Turn Left"); // true
bool containsAttack = commandQueue.Contains("Attack"); // false

// Check if the queue is empty
bool isEmpty = commandQueue.Count == 0; // false

// Clear all elements
commandQueue.Clear();
Console.WriteLine($"Queue count after clear: {commandQueue.Count}"); // 0

Iterating Through a Queue

You can iterate through a queue without modifying it:

Queue<string> commandQueue = new Queue<string>();
commandQueue.Enqueue("Move Forward");
commandQueue.Enqueue("Turn Left");
commandQueue.Enqueue("Attack");

// Iterate through the queue (does not modify the queue)
Console.WriteLine("All queued commands:");
foreach (string command in commandQueue)
{
    Console.WriteLine(command);
}

// The queue is still intact
Console.WriteLine($"Queue count: {commandQueue.Count}"); // 3

info

When you iterate through a queue, you're viewing a snapshot of its contents. The iteration order matches the dequeue order (first in, first out).

Converting Between Queues and Other Collections

You can convert between queues and other collection types:

Queue<int> numberQueue = new Queue<int>();
numberQueue.Enqueue(1);
numberQueue.Enqueue(2);
numberQueue.Enqueue(3);

// Convert queue to array
int[] numberArray = numberQueue.ToArray();

// Convert queue to list
List<int> numberList = new List<int>(numberQueue);

// Create a new queue from the array
Queue<int> newQueue = new Queue<int>(numberArray);

Queue<T> in Game Development

Queues are particularly useful in game development for managing sequences of actions or events. Here are some practical examples:

Example: Turn-Based Combat System

public class CombatManager : MonoBehaviour
{
    // Queue of characters waiting for their turn
    private Queue<Character> turnQueue = new Queue<Character>();
    
    // Currently active character
    private Character activeCharacter;
    
    // Is a turn in progress?
    private bool turnInProgress = false;
    
    void Start()
    {
        // Initialize the combat
        InitializeCombat();
    }
    
    void InitializeCombat()
    {
        // Get all characters in the scene
        Character[] allCharacters = FindObjectsOfType<Character>();
        
        // Sort characters by initiative (speed)
        Array.Sort(allCharacters, (a, b) => b.Initiative.CompareTo(a.Initiative));
        
        // Clear the queue and add all characters
        turnQueue.Clear();
        foreach (Character character in allCharacters)
        {
            turnQueue.Enqueue(character);
            character.PrepareForCombat();
        }
        
        // Start the first turn
        StartNextTurn();
    }
    
    void StartNextTurn()
    {
        if (turnInProgress || turnQueue.Count == 0)
            return;
            
        // Get the next character in the queue
        activeCharacter = turnQueue.Dequeue();
        
        // Skip defeated characters
        while (activeCharacter.IsDefeated && turnQueue.Count > 0)
        {
            activeCharacter = turnQueue.Dequeue();
        }
        
        // Check if we have a valid character
        if (!activeCharacter.IsDefeated)
        {
            turnInProgress = true;
            
            // Notify the character it's their turn
            activeCharacter.StartTurn();
            
            Debug.Log($"{activeCharacter.Name}'s turn");
            
            // If it's an AI character, start their decision process
            if (activeCharacter.IsAI)
            {
                StartCoroutine(ExecuteAITurn());
            }
            // Otherwise, enable player input for this character
            else
            {
                EnablePlayerControls();
            }
        }
        else
        {
            // No valid characters left, combat might be over
            CheckCombatEnd();
        }
    }
    
    // Called when a character ends their turn
    public void EndTurn()
    {
        if (!turnInProgress)
            return;
            
        turnInProgress = false;
        
        // Re-add the character to the end of the queue
        turnQueue.Enqueue(activeCharacter);
        
        // Start the next turn
        StartNextTurn();
    }
    
    // AI character turn logic
    IEnumerator ExecuteAITurn()
    {
        // Wait a moment for dramatic effect
        yield return new WaitForSeconds(1f);
        
        // Let the AI choose and execute an action
        activeCharacter.ChooseAndExecuteAction();
        
        // Wait for the action to complete
        yield return new WaitForSeconds(2f);
        
        // End the turn
        EndTurn();
    }
    
    // Enable controls for player character
    void EnablePlayerControls()
    {
        // Implementation depends on your input system
        Debug.Log("Player controls enabled for " + activeCharacter.Name);
    }
    
    // Check if combat has ended
    void CheckCombatEnd()
    {
        bool allEnemiesDefeated = true;
        bool allPlayersDefeated = true;
        
        foreach (Character character in FindObjectsOfType<Character>())
        {
            if (!character.IsDefeated)
            {
                if (character.IsEnemy)
                    allEnemiesDefeated = false;
                else
                    allPlayersDefeated = false;
            }
        }
        
        if (allEnemiesDefeated)
        {
            EndCombat(true); // Victory
        }
        else if (allPlayersDefeated)
        {
            EndCombat(false); // Defeat
        }
        else
        {
            // Combat continues
            StartNextTurn();
        }
    }
    
    void EndCombat(bool victory)
    {
        Debug.Log(victory ? "Combat Victory!" : "Combat Defeat!");
        // Handle end of combat (rewards, game over, etc.)
    }
}

Example: Command Queue for RTS Units

public enum CommandType
{
    Move,
    Attack,
    Gather,
    Build,
    Stop
}

public class Command
{
    public CommandType Type { get; private set; }
    public Vector3 TargetPosition { get; private set; }
    public GameObject TargetObject { get; private set; }
    
    public Command(CommandType type, Vector3 position, GameObject target = null)
    {
        Type = type;
        TargetPosition = position;
        TargetObject = target;
    }
}

public class UnitController : MonoBehaviour
{
    // Queue of commands for this unit
    private Queue<Command> commandQueue = new Queue<Command>();
    
    // Is the unit currently executing a command?
    private bool isExecutingCommand = false;
    
    // Unit properties
    public float moveSpeed = 5f;
    public float attackRange = 2f;
    public float attackDamage = 10f;
    
    void Update()
    {
        // If we're not executing a command and have commands queued, start the next one
        if (!isExecutingCommand && commandQueue.Count > 0)
        {
            ExecuteNextCommand();
        }
    }
    
    // Add a new command to the queue
    public void EnqueueCommand(Command command, bool clearQueue = false)
    {
        // Optionally clear existing commands
        if (clearQueue)
        {
            commandQueue.Clear();
            isExecutingCommand = false;
            StopAllCoroutines();
        }
        
        // Add the new command
        commandQueue.Enqueue(command);
        
        Debug.Log($"Command queued: {command.Type}. Queue size: {commandQueue.Count}");
        
        // If we're not busy, execute immediately
        if (!isExecutingCommand)
        {
            ExecuteNextCommand();
        }
    }
    
    // Execute the next command in the queue
    void ExecuteNextCommand()
    {
        if (commandQueue.Count == 0)
            return;
            
        // Get the next command
        Command command = commandQueue.Dequeue();
        isExecutingCommand = true;
        
        // Execute based on command type
        switch (command.Type)
        {
            case CommandType.Move:
                StartCoroutine(ExecuteMoveCommand(command));
                break;
                
            case CommandType.Attack:
                StartCoroutine(ExecuteAttackCommand(command));
                break;
                
            case CommandType.Gather:
                StartCoroutine(ExecuteGatherCommand(command));
                break;
                
            case CommandType.Build:
                StartCoroutine(ExecuteBuildCommand(command));
                break;
                
            case CommandType.Stop:
                StopAllCommands();
                break;
        }
    }
    
    // Move command implementation
    IEnumerator ExecuteMoveCommand(Command command)
    {
        Debug.Log("Executing move command");
        
        // Continue until we reach the target position
        while (Vector3.Distance(transform.position, command.TargetPosition) > 0.1f)
        {
            // Calculate direction and move
            Vector3 direction = (command.TargetPosition - transform.position).normalized;
            transform.position += direction * moveSpeed * Time.deltaTime;
            
            // Rotate towards the movement direction
            if (direction != Vector3.zero)
            {
                transform.rotation = Quaternion.LookRotation(direction);
            }
            
            yield return null;
        }
        
        // Command completed
        isExecutingCommand = false;
        
        // Execute the next command if available
        if (commandQueue.Count > 0)
        {
            ExecuteNextCommand();
        }
    }
    
    // Attack command implementation
    IEnumerator ExecuteAttackCommand(Command command)
    {
        Debug.Log("Executing attack command");
        
        // Check if the target is still valid
        if (command.TargetObject == null)
        {
            Debug.Log("Attack target no longer exists");
            isExecutingCommand = false;
            
            // Execute the next command if available
            if (commandQueue.Count > 0)
            {
                ExecuteNextCommand();
            }
            yield break;
        }
        
        // Move to attack range
        while (Vector3.Distance(transform.position, command.TargetObject.transform.position) > attackRange)
        {
            // Calculate direction and move
            Vector3 direction = (command.TargetObject.transform.position - transform.position).normalized;
            transform.position += direction * moveSpeed * Time.deltaTime;
            
            // Rotate towards the target
            transform.rotation = Quaternion.LookRotation(direction);
            
            // Check if target was destroyed while moving
            if (command.TargetObject == null)
            {
                Debug.Log("Attack target no longer exists");
                isExecutingCommand = false;
                
                // Execute the next command if available
                if (commandQueue.Count > 0)
                {
                    ExecuteNextCommand();
                }
                yield break;
            }
            
            yield return null;
        }
        
        // We're in range, perform the attack
        Debug.Log("Attacking target");
        
        // Apply damage to the target
        Health targetHealth = command.TargetObject.GetComponent<Health>();
        if (targetHealth != null)
        {
            targetHealth.TakeDamage(attackDamage);
        }
        
        // Command completed
        isExecutingCommand = false;
        
        // Execute the next command if available
        if (commandQueue.Count > 0)
        {
            ExecuteNextCommand();
        }
    }
    
    // Gather command implementation (simplified)
    IEnumerator ExecuteGatherCommand(Command command)
    {
        Debug.Log("Executing gather command");
        
        // Implementation would be similar to attack but with resource gathering logic
        yield return new WaitForSeconds(2f);
        
        // Command completed
        isExecutingCommand = false;
        
        // Execute the next command if available
        if (commandQueue.Count > 0)
        {
            ExecuteNextCommand();
        }
    }
    
    // Build command implementation (simplified)
    IEnumerator ExecuteBuildCommand(Command command)
    {
        Debug.Log("Executing build command");
        
        // Implementation would involve moving to location and construction logic
        yield return new WaitForSeconds(3f);
        
        // Command completed
        isExecutingCommand = false;
        
        // Execute the next command if available
        if (commandQueue.Count > 0)
        {
            ExecuteNextCommand();
        }
    }
    
    // Stop all commands
    void StopAllCommands()
    {
        Debug.Log("Stopping all commands");
        
        // Clear the queue
        commandQueue.Clear();
        
        // Stop current command execution
        StopAllCoroutines();
        isExecutingCommand = false;
    }
}

Example: Message Processing System

public class Message
{
    public string Sender { get; private set; }
    public string Content { get; private set; }
    public float DisplayTime { get; private set; }
    
    public Message(string sender, string content, float displayTime = 3f)
    {
        Sender = sender;
        Content = content;
        DisplayTime = displayTime;
    }
}

public class MessageSystem : MonoBehaviour
{
    [SerializeField] private Text messageText;
    [SerializeField] private Text senderText;
    [SerializeField] private GameObject messagePanel;
    
    // Queue of messages waiting to be displayed
    private Queue<Message> messageQueue = new Queue<Message>();
    
    // Is a message currently being displayed?
    private bool isDisplayingMessage = false;
    
    void Start()
    {
        // Hide the message panel initially
        messagePanel.SetActive(false);
    }
    
    // Add a message to the queue
    public void QueueMessage(string sender, string content, float displayTime = 3f)
    {
        Message message = new Message(sender, content, displayTime);
        messageQueue.Enqueue(message);
        
        Debug.Log($"Message queued from {sender}. Queue size: {messageQueue.Count}");
        
        // If we're not displaying a message, start now
        if (!isDisplayingMessage)
        {
            DisplayNextMessage();
        }
    }
    
    // Display the next message in the queue
    void DisplayNextMessage()
    {
        if (messageQueue.Count == 0)
        {
            // No more messages
            messagePanel.SetActive(false);
            isDisplayingMessage = false;
            return;
        }
        
        // Get the next message
        Message message = messageQueue.Dequeue();
        isDisplayingMessage = true;
        
        // Update the UI
        senderText.text = message.Sender;
        messageText.text = message.Content;
        messagePanel.SetActive(true);
        
        // Schedule the next message
        StartCoroutine(MessageDisplayTimer(message.DisplayTime));
    }
    
    // Timer for message display
    IEnumerator MessageDisplayTimer(float displayTime)
    {
        yield return new WaitForSeconds(displayTime);
        
        // Display the next message
        DisplayNextMessage();
    }
    
    // Clear all pending messages
    public void ClearMessageQueue()
    {
        messageQueue.Clear();
        StopAllCoroutines();
        
        messagePanel.SetActive(false);
        isDisplayingMessage = false;
    }
}

Performance Considerations

When working with queues, keep these performance considerations in mind:

1. Enqueue and Dequeue Operations: These are generally O(1) operations, making queues efficient for their intended use case.

2. Contains Operation: Checking if a queue contains a specific element is an O(n) operation, as it needs to scan through all elements.

3. Memory Usage: Like other collections, queues allocate memory dynamically. If you know the approximate size in advance, specify an initial capacity.

4. Iteration: Iterating through a queue does not dequeue elements, but it's still an O(n) operation.

5. Thread Safety: The standard Queue<T> is not thread-safe. For concurrent access, use ConcurrentQueue<T> from the System.Collections.Concurrent namespace.

Queue<T> vs. Other Collections

Here's how queues compare to other collection types:

Collection	Strengths	Weaknesses	When to Use
Queue<T>	Fast first-in-first-out operations, maintains order	No random access, limited operations	When you need to process items in the order they were added
Stack<T>	Fast last-in-first-out operations	No random access, limited operations	When you need to process items in reverse order of addition
List<T>	Random access, flexible operations	Less efficient for FIFO operations	When you need random access and flexible operations
LinkedList<T>	Efficient insertions and removals	No random access	When you need frequent insertions and removals at both ends

Practical Example: Breadth-First Search Algorithm

Queues are essential for breadth-first search algorithms, which are commonly used in pathfinding and graph traversal. Here's an example implementation:

public class GridNode
{
    public int X { get; private set; }
    public int Y { get; private set; }
    public bool IsWalkable { get; set; }
    public GridNode Parent { get; set; }
    
    public GridNode(int x, int y, bool isWalkable = true)
    {
        X = x;
        Y = y;
        IsWalkable = isWalkable;
    }
}

public class PathFinder : MonoBehaviour
{
    [SerializeField] private int gridWidth = 20;
    [SerializeField] private int gridHeight = 20;
    
    private GridNode[,] grid;
    
    void Start()
    {
        // Initialize the grid
        InitializeGrid();
    }
    
    void InitializeGrid()
    {
        grid = new GridNode[gridWidth, gridHeight];
        
        // Create nodes
        for (int x = 0; x < gridWidth; x++)
        {
            for (int y = 0; y < gridHeight; y++)
            {
                // Randomly make some nodes unwalkable (obstacles)
                bool isWalkable = Random.value > 0.2f;
                grid[x, y] = new GridNode(x, y, isWalkable);
            }
        }
    }
    
    // Find a path using breadth-first search
    public List<GridNode> FindPath(int startX, int startY, int goalX, int goalY)
    {
        // Validate input
        if (startX < 0 || startX >= gridWidth || startY < 0 || startY >= gridHeight ||
            goalX < 0 || goalX >= gridWidth || goalY < 0 || goalY >= gridHeight)
        {
            Debug.LogError("Start or goal position is outside the grid");
            return null;
        }
        
        // Get start and goal nodes
        GridNode startNode = grid[startX, startY];
        GridNode goalNode = grid[goalX, goalY];
        
        // Check if start or goal is unwalkable
        if (!startNode.IsWalkable || !goalNode.IsWalkable)
        {
            Debug.LogError("Start or goal position is unwalkable");
            return null;
        }
        
        // Initialize the search
        Queue<GridNode> frontier = new Queue<GridNode>();
        HashSet<GridNode> visited = new HashSet<GridNode>();
        
        // Start from the start node
        frontier.Enqueue(startNode);
        visited.Add(startNode);
        
        // Reset parent references
        for (int x = 0; x < gridWidth; x++)
        {
            for (int y = 0; y < gridHeight; y++)
            {
                grid[x, y].Parent = null;
            }
        }
        
        bool pathFound = false;
        
        // Breadth-first search
        while (frontier.Count > 0)
        {
            // Get the next node to explore
            GridNode current = frontier.Dequeue();
            
            // Check if we've reached the goal
            if (current == goalNode)
            {
                pathFound = true;
                break;
            }
            
            // Get neighboring nodes
            List<GridNode> neighbors = GetNeighbors(current);
            
            // Explore each neighbor
            foreach (GridNode neighbor in neighbors)
            {
                // Skip if already visited or unwalkable
                if (visited.Contains(neighbor) || !neighbor.IsWalkable)
                    continue;
                
                // Add to frontier and mark as visited
                frontier.Enqueue(neighbor);
                visited.Add(neighbor);
                
                // Set parent for path reconstruction
                neighbor.Parent = current;
            }
        }
        
        // If no path was found
        if (!pathFound)
        {
            Debug.Log("No path found");
            return null;
        }
        
        // Reconstruct the path
        List<GridNode> path = new List<GridNode>();
        GridNode pathNode = goalNode;
        
        while (pathNode != null)
        {
            path.Add(pathNode);
            pathNode = pathNode.Parent;
        }
        
        // Reverse to get path from start to goal
        path.Reverse();
        
        Debug.Log($"Path found with {path.Count} nodes");
        return path;
    }
    
    // Get walkable neighbors of a node
    private List<GridNode> GetNeighbors(GridNode node)
    {
        List<GridNode> neighbors = new List<GridNode>();
        
        // Check the four adjacent nodes (up, right, down, left)
        int[] dx = { 0, 1, 0, -1 };
        int[] dy = { 1, 0, -1, 0 };
        
        for (int i = 0; i < 4; i++)
        {
            int newX = node.X + dx[i];
            int newY = node.Y + dy[i];
            
            // Check if the position is within the grid
            if (newX >= 0 && newX < gridWidth && newY >= 0 && newY < gridHeight)
            {
                neighbors.Add(grid[newX, newY]);
            }
        }
        
        return neighbors;
    }
    
    // Visualize the path (would be called from elsewhere)
    public void VisualizePathBFS(int startX, int startY, int goalX, int goalY)
    {
        List<GridNode> path = FindPath(startX, startY, goalX, goalY);
        
        if (path != null)
        {
            // Visualization code would go here
            // This could involve instantiating objects, drawing lines, etc.
            Debug.Log("Path visualization complete");
        }
    }
}

This example demonstrates how a queue is used in breadth-first search:

1. We start with the initial node and add it to the frontier queue
2. We repeatedly dequeue a node, check if it's the goal, and enqueue its unvisited neighbors
3. This ensures we explore nodes in order of their distance from the start, which guarantees the shortest path in an unweighted graph

Conclusion

Queue<T> is a specialized collection that excels at first-in, first-out (FIFO) operations. It's an essential data structure for many game development scenarios, particularly those involving ordered processing, waiting lists, or breadth-first algorithms.

Key points to remember:

• Queues follow the FIFO principle: first in, first out
• The main operations are Enqueue() (add to end), Dequeue() (remove from beginning), and Peek() (view beginning without removing)
• Queues are ideal for processing items in the order they were received
• Common game uses include turn systems, command queues, message systems, and breadth-first search algorithms

In the next section, we'll explore Stack<T>, a collection type that follows the opposite principle: last in, first out (LIFO).