4.2.3.1 - Stacks and their operations (C#)

LIFO and stack state

A stack exposes one end, called the top, so the most recently added item is the first one removed.

Undo history fits LIFO: the last edit is undone first. Nested subroutine calls also finish in reverse order; a call stack holds information needed to return to suspended callers. A FIFO waiting line would instead need a queue.

For a fixed array representation, let top be the index of the current top element. Create int[] items = new int[3]; and set top = -1 for empty. Valid live elements are indexes 0 through top. The zeros initially present in the array are not stored stack items: top defines membership. After pushes of 7 and 2, top is 1 and the stack bottom-to-top is [7,2]. After popping 2, top is 0. The old 2 may remain physically in the array, but it is no longer live.

Different textbooks may make top point to the next free slot instead. Both conventions work; the initial value, tests and updates must agree. Use the current-top convention throughout this lesson.

Push, pop and peek

The order of top updates determines whether an operation uses the correct array slot.

After checking space, push increments top and then stores the new item. After checking nonempty, pop saves the value at top and then decrements top. Peek reads the same value but does not move top.

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<string> pages = new Stack<string>();
        pages.Push("Home");
        pages.Push("Search");
        pages.Push("Result");
        Console.WriteLine(pages.Peek());
        Console.WriteLine(pages.Pop());
        Console.WriteLine(pages.Peek());
        Console.WriteLine(pages.Count);
    }
}

It prints Result, Result, Search and 2 on separate lines. The first peek does not remove Result, so pop returns it too. This built-in stack grows its storage as needed; it has no fixed application capacity. Check Count == 0 before a removal or peek when emptiness is possible.