6.6 - Stack<T>

A Stack<T> is a specialized collection that follows the Last-In-First-Out (LIFO) principle: the last element added to the stack is the first one to be removed. Think of a stack like a pile of plates—you add plates to the top and remove them from the top.

Why Use Stack<T>?

Stacks are ideal for scenarios where you need to:

1. Track history or state: Keeping track of previous states or operations.
2. Implement undo functionality: Allowing users to revert recent actions.
3. Manage nested operations: Handling operations that need to be unwound in reverse order.
4. Implement depth-first algorithms: Used in pathfinding, tree traversal, and other algorithms.

Common game development uses include:

• Undo/redo systems
• Navigation history
• Expression evaluation
• Backtracking algorithms
• Game state management
• Recursive function simulation

Creating and Initializing Stacks

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

Basic Creation

// Create an empty stack of integers
Stack<int> numberStack = new Stack<int>();

// Create an empty stack of strings
Stack<string> historyStack = new Stack<string>();

// Create a stack with an initial capacity
Stack<GameObject> objectStack = new Stack<GameObject>(100);

Initializing with Elements

// Initialize from an existing collection
int[] numbers = { 1, 2, 3, 4, 5 };
Stack<int> numberStack = new Stack<int>(numbers);
// Note: The elements will be pushed in reverse order
// The top of the stack will be 5, then 4, 3, 2, 1

// Initialize from a list
List<string> actions = new List<string> { "Move", "Attack", "Jump" };
Stack<string> actionStack = new Stack<string>(actions);
// The top of the stack will be "Jump", then "Attack", "Move"

Stack Operations

Stacks have a few core operations that align with their LIFO nature:

Adding Elements (Push)

To add an element to the top of the stack:

Stack<string> undoStack = new Stack<string>();

// Add elements to the stack
undoStack.Push("Create Object");
undoStack.Push("Move Object");
undoStack.Push("Resize Object");

Console.WriteLine($"Stack count: {undoStack.Count}"); // 3

Removing Elements (Pop)

To remove and return the element at the top of the stack:

Stack<string> undoStack = new Stack<string>();
undoStack.Push("Create Object");
undoStack.Push("Move Object");
undoStack.Push("Resize Object");

// Process actions in reverse order (undo)
string lastAction = undoStack.Pop(); // "Resize Object"
Console.WriteLine($"Undoing: {lastAction}");

string secondLastAction = undoStack.Pop(); // "Move Object"
Console.WriteLine($"Undoing: {secondLastAction}");

Console.WriteLine($"Remaining actions: {undoStack.Count}"); // 1

caution

Calling Pop() on an empty stack will throw an InvalidOperationException. Always check if the stack has elements before popping.

Viewing the Top Element (Peek)

To view the element at the top of the stack without removing it:

Stack<string> undoStack = new Stack<string>();
undoStack.Push("Create Object");
undoStack.Push("Move Object");

// Look at the top action without removing it
string nextUndoAction = undoStack.Peek(); // "Move Object"
Console.WriteLine($"Next undo action: {nextUndoAction}");

// The stack is unchanged
Console.WriteLine($"Stack count: {undoStack.Count}"); // 2

caution

Like Pop(), calling Peek() on an empty stack will throw an InvalidOperationException.

Checking and Clearing

Additional useful operations:

Stack<string> undoStack = new Stack<string>();
undoStack.Push("Create Object");
undoStack.Push("Move Object");

// Check if the stack contains a specific element
bool containsMoveObject = undoStack.Contains("Move Object"); // true
bool containsDeleteObject = undoStack.Contains("Delete Object"); // false

// Check if the stack is empty
bool isEmpty = undoStack.Count == 0; // false

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

Iterating Through a Stack

You can iterate through a stack without modifying it:

Stack<string> undoStack = new Stack<string>();
undoStack.Push("Create Object");
undoStack.Push("Move Object");
undoStack.Push("Resize Object");

// Iterate through the stack (does not modify the stack)
Console.WriteLine("Undo history (most recent first):");
foreach (string action in undoStack)
{
    Console.WriteLine(action);
}
// Output:
// Resize Object
// Move Object
// Create Object

// The stack is still intact
Console.WriteLine($"Stack count: {undoStack.Count}"); // 3

info

When you iterate through a stack, the elements are returned in LIFO order (top to bottom). This is the reverse of the order in which they were pushed.

Converting Between Stacks and Other Collections

You can convert between stacks and other collection types:

Stack<int> numberStack = new Stack<int>();
numberStack.Push(1);
numberStack.Push(2);
numberStack.Push(3);

// Convert stack to array
int[] numberArray = numberStack.ToArray();
// numberArray will be { 3, 2, 1 } (LIFO order)

// Convert stack to list
List<int> numberList = new List<int>(numberStack);
// numberList will be { 3, 2, 1 } (LIFO order)

// Create a new stack from the array
Stack<int> newStack = new Stack<int>(numberArray);
// The elements will be pushed in reverse order again
// So the top of newStack will be 1, then 2, 3

Stack<T> in Game Development

Stacks are particularly useful in game development for tracking history and managing nested operations. Here are some practical examples:

Example: Undo/Redo System

public interface ICommand
{
    void Execute();
    void Undo();
}

public class MoveCommand : ICommand
{
    private GameObject target;
    private Vector3 startPosition;
    private Vector3 endPosition;
    
    public MoveCommand(GameObject target, Vector3 endPosition)
    {
        this.target = target;
        this.startPosition = target.transform.position;
        this.endPosition = endPosition;
    }
    
    public void Execute()
    {
        target.transform.position = endPosition;
    }
    
    public void Undo()
    {
        target.transform.position = startPosition;
    }
}

public class RotateCommand : ICommand
{
    private GameObject target;
    private Quaternion startRotation;
    private Quaternion endRotation;
    
    public RotateCommand(GameObject target, Quaternion endRotation)
    {
        this.target = target;
        this.startRotation = target.transform.rotation;
        this.endRotation = endRotation;
    }
    
    public void Execute()
    {
        target.transform.rotation = endRotation;
    }
    
    public void Undo()
    {
        target.transform.rotation = startRotation;
    }
}

public class CommandManager : MonoBehaviour
{
    // Stack for undo operations
    private Stack<ICommand> undoStack = new Stack<ICommand>();
    
    // Stack for redo operations
    private Stack<ICommand> redoStack = new Stack<ICommand>();
    
    // Execute a new command
    public void ExecuteCommand(ICommand command)
    {
        // Execute the command
        command.Execute();
        
        // Add to undo stack
        undoStack.Push(command);
        
        // Clear redo stack since we've taken a new action
        redoStack.Clear();
        
        Debug.Log($"Command executed. Undo stack size: {undoStack.Count}");
    }
    
    // Undo the last command
    public void Undo()
    {
        if (undoStack.Count > 0)
        {
            // Get the last command
            ICommand command = undoStack.Pop();
            
            // Undo it
            command.Undo();
            
            // Add to redo stack
            redoStack.Push(command);
            
            Debug.Log($"Command undone. Undo stack size: {undoStack.Count}, Redo stack size: {redoStack.Count}");
        }
        else
        {
            Debug.Log("Nothing to undo");
        }
    }
    
    // Redo the last undone command
    public void Redo()
    {
        if (redoStack.Count > 0)
        {
            // Get the last undone command
            ICommand command = redoStack.Pop();
            
            // Execute it again
            command.Execute();
            
            // Add back to undo stack
            undoStack.Push(command);
            
            Debug.Log($"Command redone. Undo stack size: {undoStack.Count}, Redo stack size: {redoStack.Count}");
        }
        else
        {
            Debug.Log("Nothing to redo");
        }
    }
    
    // Clear all command history
    public void ClearHistory()
    {
        undoStack.Clear();
        redoStack.Clear();
        Debug.Log("Command history cleared");
    }
}

// Example usage in a level editor
public class LevelEditor : MonoBehaviour
{
    [SerializeField] private CommandManager commandManager;
    [SerializeField] private GameObject selectedObject;
    
    // Move the selected object
    public void MoveObject(Vector3 newPosition)
    {
        if (selectedObject != null)
        {
            MoveCommand moveCommand = new MoveCommand(selectedObject, newPosition);
            commandManager.ExecuteCommand(moveCommand);
        }
    }
    
    // Rotate the selected object
    public void RotateObject(Quaternion newRotation)
    {
        if (selectedObject != null)
        {
            RotateCommand rotateCommand = new RotateCommand(selectedObject, newRotation);
            commandManager.ExecuteCommand(rotateCommand);
        }
    }
    
    // UI button handlers
    public void OnUndoButtonClicked()
    {
        commandManager.Undo();
    }
    
    public void OnRedoButtonClicked()
    {
        commandManager.Redo();
    }
}

Example: Navigation History

public class UINavigationManager : MonoBehaviour
{
    [SerializeField] private GameObject mainMenuPanel;
    [SerializeField] private GameObject inventoryPanel;
    [SerializeField] private GameObject shopPanel;
    [SerializeField] private GameObject settingsPanel;
    [SerializeField] private GameObject characterPanel;
    
    // Stack to track UI navigation history
    private Stack<GameObject> navigationHistory = new Stack<GameObject>();
    
    // Currently active panel
    private GameObject currentPanel;
    
    void Start()
    {
        // Start with main menu
        ShowPanel(mainMenuPanel);
    }
    
    // Show a specific panel
    public void ShowPanel(GameObject panel)
    {
        // Hide current panel if it exists
        if (currentPanel != null)
        {
            // Add current panel to history before hiding it
            navigationHistory.Push(currentPanel);
            currentPanel.SetActive(false);
        }
        
        // Show the new panel
        panel.SetActive(true);
        currentPanel = panel;
        
        Debug.Log($"Showing panel: {panel.name}. History depth: {navigationHistory.Count}");
    }
    
    // Go back to the previous panel
    public void GoBack()
    {
        if (navigationHistory.Count > 0)
        {
            // Get the previous panel
            GameObject previousPanel = navigationHistory.Pop();
            
            // Hide current panel
            if (currentPanel != null)
            {
                currentPanel.SetActive(false);
            }
            
            // Show previous panel
            previousPanel.SetActive(true);
            currentPanel = previousPanel;
            
            Debug.Log($"Navigated back to: {previousPanel.name}. History depth: {navigationHistory.Count}");
        }
        else
        {
            Debug.Log("Can't go back - at root level");
        }
    }
    
    // Clear navigation history and return to main menu
    public void ReturnToMainMenu()
    {
        // Hide current panel
        if (currentPanel != null)
        {
            currentPanel.SetActive(false);
        }
        
        // Clear history
        navigationHistory.Clear();
        
        // Show main menu
        mainMenuPanel.SetActive(true);
        currentPanel = mainMenuPanel;
        
        Debug.Log("Returned to main menu, history cleared");
    }
    
    // UI button handlers
    public void OnInventoryButtonClicked()
    {
        ShowPanel(inventoryPanel);
    }
    
    public void OnShopButtonClicked()
    {
        ShowPanel(shopPanel);
    }
    
    public void OnSettingsButtonClicked()
    {
        ShowPanel(settingsPanel);
    }
    
    public void OnCharacterButtonClicked()
    {
        ShowPanel(characterPanel);
    }
    
    public void OnBackButtonClicked()
    {
        GoBack();
    }
    
    public void OnHomeButtonClicked()
    {
        ReturnToMainMenu();
    }
}

Example: Expression Evaluator

public class ExpressionEvaluator
{
    // Evaluate a simple mathematical expression
    public float Evaluate(string expression)
    {
        // Remove all whitespace
        expression = expression.Replace(" ", "");
        
        // Stack for numbers
        Stack<float> numbers = new Stack<float>();
        
        // Stack for operators
        Stack<char> operators = new Stack<char>();
        
        for (int i = 0; i < expression.Length; i++)
        {
            char c = expression[i];
            
            // If the character is a digit or decimal point
            if (char.IsDigit(c) || c == '.')
            {
                // Extract the full number
                string number = "";
                while (i < expression.Length && (char.IsDigit(expression[i]) || expression[i] == '.'))
                {
                    number += expression[i];
                    i++;
                }
                i--; // Adjust for the loop increment
                
                // Parse and push the number
                numbers.Push(float.Parse(number));
            }
            // If the character is an opening parenthesis
            else if (c == '(')
            {
                operators.Push(c);
            }
            // If the character is a closing parenthesis
            else if (c == ')')
            {
                // Process all operators until the opening parenthesis
                while (operators.Count > 0 && operators.Peek() != '(')
                {
                    ProcessOperation(numbers, operators);
                }
                
                // Remove the opening parenthesis
                if (operators.Count > 0 && operators.Peek() == '(')
                {
                    operators.Pop();
                }
            }
            // If the character is an operator
            else if (c == '+' || c == '-' || c == '*' || c == '/')
            {
                // Process operators with higher or equal precedence
                while (operators.Count > 0 && Precedence(operators.Peek()) >= Precedence(c))
                {
                    ProcessOperation(numbers, operators);
                }
                
                // Push the current operator
                operators.Push(c);
            }
        }
        
        // Process any remaining operators
        while (operators.Count > 0)
        {
            ProcessOperation(numbers, operators);
        }
        
        // The final result should be the only number left in the stack
        return numbers.Pop();
    }
    
    // Process a single operation
    private void ProcessOperation(Stack<float> numbers, Stack<char> operators)
    {
        char op = operators.Pop();
        
        // Skip opening parenthesis
        if (op == '(')
            return;
        
        // Need at least two numbers for an operation
        if (numbers.Count < 2)
            throw new InvalidOperationException("Invalid expression");
        
        float b = numbers.Pop();
        float a = numbers.Pop();
        
        switch (op)
        {
            case '+':
                numbers.Push(a + b);
                break;
            case '-':
                numbers.Push(a - b);
                break;
            case '*':
                numbers.Push(a * b);
                break;
            case '/':
                if (b == 0)
                    throw new DivideByZeroException("Division by zero");
                numbers.Push(a / b);
                break;
        }
    }
    
    // Get operator precedence
    private int Precedence(char op)
    {
        switch (op)
        {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return 0;
        }
    }
}

// Example usage
public class Calculator : MonoBehaviour
{
    [SerializeField] private InputField expressionInput;
    [SerializeField] private Text resultText;
    
    private ExpressionEvaluator evaluator = new ExpressionEvaluator();
    
    public void EvaluateExpression()
    {
        try
        {
            string expression = expressionInput.text;
            float result = evaluator.Evaluate(expression);
            resultText.text = result.ToString();
        }
        catch (Exception e)
        {
            resultText.text = "Error: " + e.Message;
        }
    }
}

Performance Considerations

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

1. Push and Pop Operations: These are generally O(1) operations, making stacks efficient for their intended use case.

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

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

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

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

Stack<T> vs. Other Collections

Here's how stacks compare to other collection types:

Collection	Strengths	Weaknesses	When to Use
Stack<T>	Fast last-in-first-out operations, tracks history	No random access, limited operations	When you need to process items in reverse order of addition
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
List<T>	Random access, flexible operations	Less efficient for LIFO 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: Depth-First Search Algorithm

Stacks are essential for depth-first search algorithms, which are commonly used in pathfinding, maze generation, and tree traversal. Here's an example implementation:

public class MazeNode
{
    public int X { get; private set; }
    public int Y { get; private set; }
    public bool IsVisited { get; set; }
    public bool[] Walls { get; private set; } // [Top, Right, Bottom, Left]
    
    public MazeNode(int x, int y)
    {
        X = x;
        Y = y;
        IsVisited = false;
        Walls = new bool[] { true, true, true, true }; // All walls initially present
    }
    
    // Remove wall between this node and another
    public void RemoveWallBetween(MazeNode other)
    {
        // Determine the direction from this node to the other
        if (other.X == X && other.Y == Y - 1) // Other is above
        {
            Walls[0] = false; // Remove top wall
            other.Walls[2] = false; // Remove other's bottom wall
        }
        else if (other.X == X + 1 && other.Y == Y) // Other is to the right
        {
            Walls[1] = false; // Remove right wall
            other.Walls[3] = false; // Remove other's left wall
        }
        else if (other.X == X && other.Y == Y + 1) // Other is below
        {
            Walls[2] = false; // Remove bottom wall
            other.Walls[0] = false; // Remove other's top wall
        }
        else if (other.X == X - 1 && other.Y == Y) // Other is to the left
        {
            Walls[3] = false; // Remove left wall
            other.Walls[1] = false; // Remove other's right wall
        }
    }
}

public class MazeGenerator : MonoBehaviour
{
    [SerializeField] private int width = 10;
    [SerializeField] private int height = 10;
    
    private MazeNode[,] maze;
    
    void Start()
    {
        GenerateMaze();
    }
    
    void GenerateMaze()
    {
        // Initialize the maze grid
        maze = new MazeNode[width, height];
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                maze[x, y] = new MazeNode(x, y);
            }
        }
        
        // Generate the maze using depth-first search
        DepthFirstGeneration();
        
        // Visualize the maze
        VisualizeMaze();
    }
    
    void DepthFirstGeneration()
    {
        // Start at a random cell
        int startX = Random.Range(0, width);
        int startY = Random.Range(0, height);
        MazeNode startNode = maze[startX, startY];
        
        // Mark as visited
        startNode.IsVisited = true;
        
        // Stack for backtracking
        Stack<MazeNode> nodeStack = new Stack<MazeNode>();
        nodeStack.Push(startNode);
        
        // Continue until all cells are visited
        while (nodeStack.Count > 0)
        {
            // Get the current cell
            MazeNode current = nodeStack.Peek();
            
            // Get unvisited neighbors
            List<MazeNode> unvisitedNeighbors = GetUnvisitedNeighbors(current);
            
            if (unvisitedNeighbors.Count > 0)
            {
                // Choose a random unvisited neighbor
                MazeNode next = unvisitedNeighbors[Random.Range(0, unvisitedNeighbors.Count)];
                
                // Remove the wall between current and next
                current.RemoveWallBetween(next);
                
                // Mark the next cell as visited
                next.IsVisited = true;
                
                // Push the next cell to the stack
                nodeStack.Push(next);
            }
            else
            {
                // No unvisited neighbors, backtrack
                nodeStack.Pop();
            }
        }
    }
    
    List<MazeNode> GetUnvisitedNeighbors(MazeNode node)
    {
        List<MazeNode> neighbors = new List<MazeNode>();
        
        // Check the four adjacent cells (top, right, bottom, 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 maze
            if (newX >= 0 && newX < width && newY >= 0 && newY < height)
            {
                // Add to neighbors if not visited
                if (!maze[newX, newY].IsVisited)
                {
                    neighbors.Add(maze[newX, newY]);
                }
            }
        }
        
        return neighbors;
    }
    
    void VisualizeMaze()
    {
        // This would create visual representations of the maze
        // For example, instantiating wall prefabs where walls exist
        Debug.Log("Maze generation complete");
        
        // Simple text visualization for debugging
        string mazeText = "";
        
        // Top border
        for (int x = 0; x < width; x++)
        {
            mazeText += "+---";
        }
        mazeText += "+\n";
        
        // Maze cells
        for (int y = 0; y < height; y++)
        {
            // Left border
            mazeText += "|";
            
            // Cell contents and right walls
            for (int x = 0; x < width; x++)
            {
                mazeText += "   ";
                mazeText += maze[x, y].Walls[1] ? "|" : " ";
            }
            mazeText += "\n";
            
            // Bottom walls
            mazeText += "+";
            for (int x = 0; x < width; x++)
            {
                mazeText += maze[x, y].Walls[2] ? "---" : "   ";
                mazeText += "+";
            }
            mazeText += "\n";
        }
        
        Debug.Log(mazeText);
    }
}

This example demonstrates how a stack is used in depth-first maze generation:

1. We start with a grid where all cells have walls between them
2. We choose a starting cell, mark it as visited, and push it onto the stack
3. We repeatedly look at the top cell in the stack, choose an unvisited neighbor, remove the wall between them, and push the neighbor onto the stack
4. If a cell has no unvisited neighbors, we pop it from the stack (backtrack)
5. This continues until the stack is empty, meaning we've visited all cells

The stack naturally implements the backtracking behavior needed for depth-first traversal.

Conclusion

Stack<T> is a specialized collection that excels at last-in, first-out (LIFO) operations. It's an essential data structure for many game development scenarios, particularly those involving history tracking, undo functionality, or depth-first algorithms.

Key points to remember:

• Stacks follow the LIFO principle: last in, first out
• The main operations are Push() (add to top), Pop() (remove from top), and Peek() (view top without removing)
• Stacks are ideal for tracking history and implementing undo systems
• Common game uses include undo/redo systems, navigation history, expression evaluation, and depth-first search algorithms

In the next section, we'll explore HashSet<T>, a collection type designed for storing unique elements with fast lookups.