Stacks - potatoscript/dsa GitHub Wiki

A stack is like a stack of plates 🍽️. You add plates to the top, and you also remove plates from the top. The last plate you add is the first plate you take off!

In computer science, this is called Last In, First Out (LIFO) — the last item added is the first one to be removed.

Top → [Plate 3] → [Plate 2] → [Plate 1] → Bottom

If you add a new plate (let’s call it “Plate 4”), it goes on top:

Top → [Plate 4] → [Plate 3] → [Plate 2] → [Plate 1] → Bottom

And when you remove a plate, you always remove from the top:

Take off Plate 4: Top → [Plate 3] → [Plate 2] → [Plate 1] → Bottom

• ✅ Reversible actions: Think about undoing an action. A stack helps us go back in the order of actions.
• ✅ Memory management: Helps in managing memory for things like function calls in programming.

In C#, we can use the Stack<T> class to easily implement a stack:

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

plateStack.Push("Plate 1");
plateStack.Push("Plate 2");
plateStack.Push("Plate 3");

string topPlate = plateStack.Pop();  // Removes "Plate 3"
Console.WriteLine("Removed: " + topPlate);

If you just want to see the top item without removing it, you can peek at it:

string topPlate = plateStack.Peek();  // Shows "Plate 2" without removing it
Console.WriteLine("Top plate: " + topPlate);

Stack<string> plateStack = new Stack<string>();
plateStack.Push("Plate 1");
plateStack.Push("Plate 2");
plateStack.Push("Plate 3");

Console.WriteLine("Stack after pushing plates:");
foreach (var plate in plateStack)
{
    Console.WriteLine(plate);
}

Output:

Plate 3
Plate 2
Plate 1

string removedPlate = plateStack.Pop();
Console.WriteLine("Removed Plate: " + removedPlate);

Console.WriteLine("Stack after popping a plate:");
foreach (var plate in plateStack)
{
    Console.WriteLine(plate);
}

Output:

Removed Plate: Plate 3
Plate 2
Plate 1

• ❌ Popping from an empty stack: You can’t pop an item from an empty stack, or you'll get an error. Always check if the stack is empty first.

if (plateStack.Count > 0)
{
    plateStack.Pop();
}
else
{
    Console.WriteLine("Stack is empty!");
}

When you run a program, each function call gets pushed onto the stack, and when a function finishes, it gets popped off.

Imagine editing a document:

• When you make changes, those actions are pushed onto the stack.
• When you undo the change, you pop it from the stack.

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

// Adding changes
undoStack.Push("Added 'Hello' to text");
undoStack.Push("Added 'World' to text");

// Undo action
if (undoStack.Count > 0)
{
    string lastAction = undoStack.Pop();
    Console.WriteLine("Undoing: " + lastAction);
}

• Push: O(1) – Adding an item to the top is quick!
• Pop: O(1) – Removing from the top is also quick!
• Peek: O(1) – Viewing the top without changing the stack is also fast!

Create a stack of 5 plates and remove them one by one, printing each plate’s name as you pop it off.

Create a simple text editor program with a stack to simulate the undo feature. Add a few actions and then undo them.

Write a program that checks if a string of parentheses is balanced using a stack (i.e., every opening parenthesis has a corresponding closing parenthesis).

• Single Stack: Standard stack, just one list of items.
• Multiple Stacks: A stack of stacks — used in complex situations like evaluating expressions with multiple operations.
• Array-Based Stack: When using arrays to store the stack.
• Linked List-Based Stack: When using linked lists to store the stack.

✅ Stacks store data in a LIFO (Last In, First Out) order.
✅ Add (Push) to the top, remove (Pop) from the top.
✅ Use them for managing function calls, undo operations, and more!
✅ Big O for stack operations: O(1) — they’re fast and efficient!