Stack och Queue

Stack och Queue är specialiserade collections som följer specifika ordningsregler - perfekta för situationer där ordning verkligen spelar roll!

🎯 Efter denna artikel kommer du att:

Förstå LIFO vs FIFO - Last In First Out vs First In First Out 📚🚶‍♂️
**Använda Stack** - för undo-funktioner, funktionsanrop, och "senaste först" scenarion 📚
**Använda Queue** - för schemaläggning, bufferts, och "första först" scenarion 🚶‍♂️
Veta när att använda vad - och undvika vanliga misstag! 💡

📚 Stack - LIFO Principen

Grundläggande koncept

Stack = “trave” eller “hög” - tänk som en trave tallrikar eller böcker.

LIFO: Last In, First Out - sista in, första ut
Push: Lägg till på toppen
Pop: Ta bort från toppen
Peek: Kika på toppen utan att ta bort

using System;
using System.Collections.Generic;

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

// Push - lägg till på toppen
books.Push("C# Grunderna");
books.Push("Advanced C#");
books.Push("Clean Code");

Console.WriteLine($"Antal böcker: {books.Count}"); // 3

// Peek - kika på toppen utan att ta bort
string topBook = books.Peek();
Console.WriteLine($"Överst: {topBook}"); // "Clean Code"
Console.WriteLine($"Antal efter Peek: {books.Count}"); // 3 (oförändrat)

// Pop - ta bort från toppen
string removedBook = books.Pop();
Console.WriteLine($"Tog bort: {removedBook}"); // "Clean Code"
Console.WriteLine($"Antal efter Pop: {books.Count}"); // 2

Stack Methods och Properties

Stack<int> numbers = new Stack<int>();

// Properties
Console.WriteLine($"Count: {numbers.Count}");     // 0

// Push - lägg till element (void method)
numbers.Push(10);
numbers.Push(20);
numbers.Push(30);

// Peek - kika på toppen (returnerar element)
int top = numbers.Peek();                         // 30
// Throws InvalidOperationException om stack är tom!

// Pop - ta bort och returnera från toppen
int removed = numbers.Pop();                      // 30
// Throws InvalidOperationException om stack är tom!

// Contains - kontrollera om element finns
bool hasValue = numbers.Contains(20);             // true

// ToArray - konvertera till array (i LIFO ordning!)
int[] array = numbers.ToArray();                  // {20, 10}

// Clear - ta bort alla element
numbers.Clear();

// TryPeek och TryPop (säkra versioner - .NET 6+)
if (numbers.TryPeek(out int topValue))
{
    Console.WriteLine($"Top: {topValue}");
}
else
{
    Console.WriteLine("Stack är tom");
}

Stack användningsområden

// 1. Undo-funktionalitet
Stack<string> undoStack = new Stack<string>();

void PerformAction(string action)
{
    undoStack.Push(action);
    Console.WriteLine($"Utförde: {action}");
}

void Undo()
{
    if (undoStack.Count > 0)
    {
        string lastAction = undoStack.Pop();
        Console.WriteLine($"Ångra: {lastAction}");
    }
}

PerformAction("Skapa fil");
PerformAction("Skriv text");
PerformAction("Formatera text");
Undo(); // Ångra: Formatera text
Undo(); // Ångra: Skriv text

// 2. Parenteser-matchning
bool IsValidParentheses(string input)
{
    Stack<char> stack = new Stack<char>();

    foreach (char c in input)
    {
        if (c == '(' || c == '[' || c == '{')
        {
            stack.Push(c);
        }
        else if (c == ')' || c == ']' || c == '}')
        {
            if (stack.Count == 0) return false;

            char opening = stack.Pop();
            if (!IsMatchingPair(opening, c)) return false;
        }
    }

    return stack.Count == 0;
}

bool IsMatchingPair(char opening, char closing)
{
    return (opening == '(' && closing == ')') ||
           (opening == '[' && closing == ']') ||
           (opening == '{' && closing == '}');
}

Console.WriteLine(IsValidParentheses("({[]})"));  // true
Console.WriteLine(IsValidParentheses("({[}])"));  // false

🚶‍♂️ Queue - FIFO Principen

Grundläggande koncept

Queue = “kö” - tänk som en kö i butiken eller på bussen.

FIFO: First In, First Out - första in, första ut
Enqueue: Ställ dig sist i kön
Dequeue: Första personen lämnar kön
Peek: Kika på första utan att ta bort

using System;
using System.Collections.Generic;

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

// Enqueue - ställ sig sist i kön
customerQueue.Enqueue("Anna");
customerQueue.Enqueue("Bert");
customerQueue.Enqueue("Cilla");

Console.WriteLine($"Antal i kön: {customerQueue.Count}"); // 3

// Peek - kika på första utan att ta bort
string nextCustomer = customerQueue.Peek();
Console.WriteLine($"Nästa kund: {nextCustomer}"); // "Anna"
Console.WriteLine($"Antal efter Peek: {customerQueue.Count}"); // 3

// Dequeue - första kunden lämnar
string servedCustomer = customerQueue.Dequeue();
Console.WriteLine($"Betjänade: {servedCustomer}"); // "Anna"
Console.WriteLine($"Antal efter Dequeue: {customerQueue.Count}"); // 2

Queue Methods och Properties

Queue<int> taskQueue = new Queue<int>();

// Properties
Console.WriteLine($"Count: {taskQueue.Count}");   // 0

// Enqueue - lägg till element sist (void method)
taskQueue.Enqueue(1);
taskQueue.Enqueue(2);
taskQueue.Enqueue(3);

// Peek - kika på första (returnerar element)
int first = taskQueue.Peek();                     // 1
// Throws InvalidOperationException om queue är tom!

// Dequeue - ta bort och returnera första
int served = taskQueue.Dequeue();                 // 1
// Throws InvalidOperationException om queue är tom!

// Contains - kontrollera om element finns
bool hasValue = taskQueue.Contains(3);            // true

// ToArray - konvertera till array (i FIFO ordning!)
int[] array = taskQueue.ToArray();                // {2, 3}

// Clear - ta bort alla element
taskQueue.Clear();

// TryDequeue och TryPeek (säkra versioner - .NET Core 2.0+)
if (taskQueue.TryDequeue(out int nextTask))
{
    Console.WriteLine($"Nästa task: {nextTask}");
}
else
{
    Console.WriteLine("Queue är tom");
}

Queue användningsområden

// 1. Task scheduling - first come, first served
Queue<string> jobQueue = new Queue<string>();

void AddJob(string job)
{
    jobQueue.Enqueue(job);
    Console.WriteLine($"La till jobb: {job}");
}

void ProcessNextJob()
{
    if (jobQueue.Count > 0)
    {
        string job = jobQueue.Dequeue();
        Console.WriteLine($"Bearbetar: {job}");
    }
    else
    {
        Console.WriteLine("Inga jobb att bearbeta");
    }
}

AddJob("Backup databas");
AddJob("Skicka emails");
AddJob("Generera rapporter");

ProcessNextJob(); // Bearbetar: Backup databas
ProcessNextJob(); // Bearbetar: Skicka emails

// 2. Breadth-First Search (BFS) i träd/graf
void BreadthFirstSearch(TreeNode root)
{
    if (root == null) return;

    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        TreeNode current = queue.Dequeue();
        Console.WriteLine(current.Value);

        // Lägg till alla barn i kön
        foreach (TreeNode child in current.Children)
        {
            queue.Enqueue(child);
        }
    }
}

// 3. Buffer för streaming data
Queue<byte> dataBuffer = new Queue<byte>();
const int MAX_BUFFER_SIZE = 1024;

void AddDataToBuffer(byte[] data)
{
    foreach (byte b in data)
    {
        if (dataBuffer.Count >= MAX_BUFFER_SIZE)
        {
            // Ta bort äldsta data för att göra plats
            dataBuffer.Dequeue();
        }
        dataBuffer.Enqueue(b);
    }
}

🆚 Stack vs Queue - När använda vad?

Använd Stack när:

// ✅ LIFO behavior krävs
// ✅ Undo/Redo funktionalitet
Stack<ICommand> undoStack = new Stack<ICommand>();

// ✅ Parsning och evaluation (parenteser, uttryck)
Stack<char> expressionStack = new Stack<char>();

// ✅ Funktionsanrop (call stack simulation)
Stack<string> callStack = new Stack<string>();

// ✅ Backtracking algoritmer
Stack<Position> pathStack = new Stack<Position>();

// ✅ Browser history (back button)
Stack<string> browserHistory = new Stack<string>();

Använd Queue när:

// ✅ FIFO behavior krävs
// ✅ Task/job scheduling
Queue<ITask> taskQueue = new Queue<ITask>();

// ✅ Print job queues
Queue<PrintJob> printQueue = new Queue<PrintJob>();

// ✅ Breadth-first search
Queue<TreeNode> bfsQueue = new Queue<TreeNode>();

// ✅ Buffering (data streaming)
Queue<byte> streamBuffer = new Queue<byte>();

// ✅ Event handling (first registered, first processed)
Queue<EventHandler> eventQueue = new Queue<EventHandler>();

⚡ Performance Comparison

Operation	Stack	Queue	List	Array
Add (Push/Enqueue)	O(1)	O(1)	O(1)*	N/A
Remove (Pop/Dequeue)	O(1)	O(1)	O(1)*	N/A
Peek	O(1)	O(1)	O(1)	O(1)
Contains	O(n)	O(n)	O(n)	O(n)
Memory	Minimal	Minimal	Dynamic	Fixed

*Amortized time - occasionally O(n) when internal array needs resizing

💡 Common Pitfalls och Best Practices

// ❌ Glöm inte att kontrollera om tom innan Pop/Dequeue
Stack<int> stack = new Stack<int>();
// int value = stack.Pop(); // InvalidOperationException!

// ✅ Kontrollera först
if (stack.Count > 0)
{
    int value = stack.Pop();
}

// ✅ Eller använd Try-metoder (.NET Core 2.0+)
if (stack.TryPop(out int safeValue))
{
    Console.WriteLine($"Got value: {safeValue}");
}

// ❌ Modifiera Stack/Queue medan du itererar
Stack<int> numbers = new Stack<int>(new[] {1, 2, 3});
foreach (int num in numbers)
{
    if (num > 1) numbers.Pop(); // InvalidOperationException!
}

// ✅ Kopiera först, eller använd while
Stack<int> numbersCopy = new Stack<int>(numbers);
while (numbersCopy.Count > 0)
{
    int num = numbersCopy.Pop();
    if (num > 1)
    {
        numbers.Pop(); // OK - modifierar olika collection
    }
}

🎯 Praktiska Tips

// Stack för "senaste först" scenarios
Stack<string> recentFiles = new Stack<string>();
recentFiles.Push("Document1.txt");
recentFiles.Push("Document2.txt");
string mostRecent = recentFiles.Peek(); // "Document2.txt"

// Queue för "första först" scenarios
Queue<Customer> serviceQueue = new Queue<Customer>();
serviceQueue.Enqueue(new Customer("Anna"));
serviceQueue.Enqueue(new Customer("Bert"));
Customer nextToServe = serviceQueue.Peek(); // Anna

// Kombinera för avancerade scenarios
Stack<ICommand> undoStack = new Stack<ICommand>();
Stack<ICommand> redoStack = new Stack<ICommand>();

void ExecuteCommand(ICommand command)
{
    command.Execute();
    undoStack.Push(command);
    redoStack.Clear(); // Clear redo när ny action utförs
}

void Undo()
{
    if (undoStack.Count > 0)
    {
        ICommand command = undoStack.Pop();
        command.Undo();
        redoStack.Push(command);
    }
}

void Redo()
{
    if (redoStack.Count > 0)
    {
        ICommand command = redoStack.Pop();
        command.Execute();
        undoStack.Push(command);
    }
}

🎓 TL;DR

**Stack**: LIFO (Last In, First Out) - använd för undo, parsing, backtracking
**Queue**: FIFO (First In, First Out) - använd för scheduling, buffering, BFS
Båda: O(1) för add/remove, O(n) för search
Säkerhet: Kontrollera Count > 0 innan Pop/Dequeue, eller använd Try-metoder

Obligatorisk dad-joke

Varför gillar programmerare Stack och Queue?

För att de alltid håller ordning på saker och ting - Stack tar det översta allvarligt, medan Queue är rättvis mot alla! 📚🚶‍♂️

Stack och Queue

🎯 Efter denna artikel kommer du att:

📚 **Stack - LIFO Principen**

Grundläggande koncept

**Stack Methods och Properties**

Stack användningsområden

🚶‍♂️ **Queue - FIFO Principen**

Grundläggande koncept

**Queue Methods och Properties**

Queue användningsområden

🆚 Stack vs Queue - När använda vad?

**Använd Stack när:**

**Använd Queue när:**

⚡ Performance Comparison

💡 Common Pitfalls och Best Practices

🎯 Praktiska Tips

🎓 TL;DR

Obligatorisk dad-joke

📚 Stack - LIFO Principen

Stack Methods och Properties

🚶‍♂️ Queue - FIFO Principen

Queue Methods och Properties

Använd Stack när:

Använd Queue när: