The Stack and Heap

The Stack and Heap

Stack and Heap Recap

In a previous tutorial, we learnt that a variable is a storage location that stores modifiable values. There are two types of variables: value and reference.

A variable can exist in multiple contexts:

  • A local variable.
  • A variable being used as a parameter.
  • As a member of an object or as an element in an array.

The Stack

The stack is a last-in, first-out (LIFO) data structure that is responsible for holding local variables and parameters. The stack grows and shrinks as functions are entered and exited.

A stack of plates

A stack is a last in first out data structure just like the way you can only get to the last plate placed on a stack.

Taking a recursive function (a function that calls itself) such as the Fibonacci sequence, the stack will grow every time it has to store a new integer (entering the function) and will shrink every time it exits a function.

public static int fib(int n)
{
 if (n == 0)
 {
 return 0;
 }
 if (n == 1 || n == 2)
 {
 return 1;
 }
 else
 {
 return (fib(n - 1) + fib(n - 2));
 }
}
for (int i = 0; i < n; i++) {
 Console.WriteLine(fib(i));
} 

The Heap and Garbage Collection

Objects may also rive inside the heap. The heap stores reference to variables whenever they are created. As the execution of a program progresses, the heap will start to fill up with many references. To prevent excessive memory usage the .NET runtime has a garbage collector that will check to see if the variable is still needed and if it is not, then the garbage collector will deallocate this value.

public class Car{
 public Car(string colour, int bhp){
 this.colour = colour;
 this.bhp = bhp;
 }
 public string colour;
 public int bhp;
}
public class Program
{
public static void Main()
{
 Car car1 = new Car("Blue", 100);
 Car car2 = new Car("Green", 2);
 Console.WriteLine(car1.bhp); //car1 deallocated
 Console.WriteLine(car2.bhp); //car 2 deallocated
}
}

Static fields are allocated to the heap and are not deallocated until the application is stopped.

Definite Assignment

C# makes it impossible to access a variable that is yet to be initialised with a value, this is because the underlying memory associated with that value is also unassigned. This also means that arguments for functions need to be supplied when a method is called.

An exception to this is when the runtime automatically initializes some values such as array elements.

string motto;
Console.WriteLine(motto); //Error