Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

Algorithm

Basic Implementation

basic.cs 
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static string Render(List<int> values) => string.Join(" -> ", values);
    static void Main() {
        var stack = new Stack<int>();
        foreach (var value in new[] {10, 20, 30}) stack.Push(value);
        var popped = new List<int>();
        while (stack.Count > 0) popped.Add(stack.Pop());
        Console.WriteLine(Render(popped));
    }
}

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • Stack<int> is the BCL LIFO container; Push appends to managed backing storage that grows as needed and is reclaimed by GC. Pop() would throw on an empty stack, so the implementation guards removal with stack.Count > 0.
  • The popped values go into a List<int> only for deterministic rendering; the important state is the stack top changing across the grouped push and pop phases.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.