Case Study 1: Building a Generic Stack and Queue

The Scenario

In Chapter 15, we built a stack and a queue using pointers and linked lists. Those implementations were type-specific: the stack held integers, the queue held strings. To use them with other types, we would need to duplicate all the code. In this case study, we rebuild both data structures as generics, creating reusable implementations that work with any type — and then demonstrate that the old pointer-based versions from Chapter 15 can be completely replaced.

The Generic Stack

unit GenericStack;

{$mode objfpc}{$H+}

interface

uses
  SysUtils;

type
  generic TStack<T> = class
  private
    FItems: array of T;
    FCount: Integer;
    FCapacity: Integer;
    procedure Grow;
  public
    constructor Create; overload;
    constructor Create(AInitialCapacity: Integer); overload;
    procedure Push(AValue: T);
    function Pop: T;
    function Peek: T;
    function IsEmpty: Boolean;
    function ToArray: specialize TArray<T>;
    procedure Clear;
    property Count: Integer read FCount;
    property Capacity: Integer read FCapacity;
  end;

  EStackError = class(Exception);

implementation

constructor TStack.Create;
begin
  Create(8);
end;

constructor TStack.Create(AInitialCapacity: Integer);
begin
  inherited Create;
  FCount := 0;
  if AInitialCapacity < 4 then
    AInitialCapacity := 4;
  FCapacity := AInitialCapacity;
  SetLength(FItems, FCapacity);
end;

procedure TStack.Grow;
begin
  FCapacity := FCapacity * 2;
  SetLength(FItems, FCapacity);
end;

procedure TStack.Push(AValue: T);
begin
  if FCount >= FCapacity then
    Grow;
  FItems[FCount] := AValue;
  Inc(FCount);
end;

function TStack.Pop: T;
begin
  if FCount = 0 then
    raise EStackError.Create('Stack underflow: cannot pop from empty stack');
  Dec(FCount);
  Result := FItems[FCount];
end;

function TStack.Peek: T;
begin
  if FCount = 0 then
    raise EStackError.Create('Stack underflow: cannot peek empty stack');
  Result := FItems[FCount - 1];
end;

function TStack.IsEmpty: Boolean;
begin
  Result := FCount = 0;
end;

function TStack.ToArray: specialize TArray<T>;
var
  i: Integer;
begin
  SetLength(Result, FCount);
  for i := 0 to FCount - 1 do
    Result[i] := FItems[i];
end;

procedure TStack.Clear;
begin
  FCount := 0;
end;

end.

The Generic Queue

unit GenericQueue;

{$mode objfpc}{$H+}

interface

uses
  SysUtils;

type
  generic TQueue<T> = class
  private
    FItems: array of T;
    FHead: Integer;   { Index of the front of the queue }
    FTail: Integer;   { Index of the next insertion point }
    FCount: Integer;
    FCapacity: Integer;
    procedure Grow;
  public
    constructor Create; overload;
    constructor Create(AInitialCapacity: Integer); overload;
    procedure Enqueue(AValue: T);
    function Dequeue: T;
    function Peek: T;
    function IsEmpty: Boolean;
    procedure Clear;
    property Count: Integer read FCount;
  end;

  EQueueError = class(Exception);

implementation

constructor TQueue.Create;
begin
  Create(8);
end;

constructor TQueue.Create(AInitialCapacity: Integer);
begin
  inherited Create;
  if AInitialCapacity < 4 then
    AInitialCapacity := 4;
  FCapacity := AInitialCapacity;
  SetLength(FItems, FCapacity);
  FHead := 0;
  FTail := 0;
  FCount := 0;
end;

procedure TQueue.Grow;
var
  NewItems: array of T;
  i: Integer;
begin
  SetLength(NewItems, FCapacity * 2);
  { Copy items in order from head to tail }
  for i := 0 to FCount - 1 do
    NewItems[i] := FItems[(FHead + i) mod FCapacity];
  FItems := NewItems;
  FHead := 0;
  FTail := FCount;
  FCapacity := FCapacity * 2;
end;

procedure TQueue.Enqueue(AValue: T);
begin
  if FCount >= FCapacity then
    Grow;
  FItems[FTail] := AValue;
  FTail := (FTail + 1) mod FCapacity;
  Inc(FCount);
end;

function TQueue.Dequeue: T;
begin
  if FCount = 0 then
    raise EQueueError.Create('Queue underflow: cannot dequeue from empty queue');
  Result := FItems[FHead];
  FHead := (FHead + 1) mod FCapacity;
  Dec(FCount);
end;

function TQueue.Peek: T;
begin
  if FCount = 0 then
    raise EQueueError.Create('Queue underflow: cannot peek empty queue');
  Result := FItems[FHead];
end;

function TQueue.IsEmpty: Boolean;
begin
  Result := FCount = 0;
end;

procedure TQueue.Clear;
begin
  FHead := 0;
  FTail := 0;
  FCount := 0;
end;

end.

Demonstration Program

program GenericCollectionsDemo;

{$mode objfpc}{$H+}

uses
  SysUtils, GenericStack, GenericQueue;

type
  TIntStack = specialize TStack<Integer>;
  TStringStack = specialize TStack<String>;
  TIntQueue = specialize TQueue<Integer>;
  TStringQueue = specialize TQueue<String>;

{ Demo 1: Integer Stack }
procedure DemoIntStack;
var
  Stack: TIntStack;
begin
  WriteLn('--- Integer Stack ---');
  Stack := TIntStack.Create;
  try
    Stack.Push(10);
    Stack.Push(20);
    Stack.Push(30);
    WriteLn('Pushed: 10, 20, 30');
    WriteLn('Peek: ', Stack.Peek);
    WriteLn('Count: ', Stack.Count);
    Write('Pop all: ');
    while not Stack.IsEmpty do
      Write(Stack.Pop, ' ');
    WriteLn;
  finally
    Stack.Free;
  end;
  WriteLn;
end;

{ Demo 2: String Stack (undo buffer) }
procedure DemoUndoBuffer;
var
  UndoStack: TStringStack;
  Action: String;
begin
  WriteLn('--- Undo Buffer (String Stack) ---');
  UndoStack := TStringStack.Create;
  try
    UndoStack.Push('Type "Hello"');
    UndoStack.Push('Bold selection');
    UndoStack.Push('Change font to Arial');
    UndoStack.Push('Delete paragraph');
    WriteLn('Actions performed: ', UndoStack.Count);

    WriteLn('Undoing actions:');
    while not UndoStack.IsEmpty do
    begin
      Action := UndoStack.Pop;
      WriteLn('  Undo: ', Action);
    end;
  finally
    UndoStack.Free;
  end;
  WriteLn;
end;

{ Demo 3: Integer Queue (task scheduling) }
procedure DemoTaskQueue;
var
  Tasks: TIntQueue;
begin
  WriteLn('--- Task Queue (Integer Queue) ---');
  Tasks := TIntQueue.Create;
  try
    Tasks.Enqueue(101);
    Tasks.Enqueue(102);
    Tasks.Enqueue(103);
    Tasks.Enqueue(104);
    WriteLn('Enqueued tasks: 101, 102, 103, 104');
    WriteLn('Queue count: ', Tasks.Count);

    Write('Processing order: ');
    while not Tasks.IsEmpty do
      Write(Tasks.Dequeue, ' ');
    WriteLn;
    WriteLn('(FIFO order preserved)');
  finally
    Tasks.Free;
  end;
  WriteLn;
end;

{ Demo 4: String Queue (print queue) }
procedure DemoPrintQueue;
var
  PrintQueue: TStringQueue;
begin
  WriteLn('--- Print Queue (String Queue) ---');
  PrintQueue := TStringQueue.Create;
  try
    PrintQueue.Enqueue('report.pdf');
    PrintQueue.Enqueue('photo.jpg');
    PrintQueue.Enqueue('letter.docx');
    WriteLn('Documents queued: ', PrintQueue.Count);

    WriteLn('Printing:');
    while not PrintQueue.IsEmpty do
      WriteLn('  Printing: ', PrintQueue.Dequeue);
  finally
    PrintQueue.Free;
  end;
  WriteLn;
end;

{ Demo 5: Exception handling }
procedure DemoExceptions;
var
  Stack: TIntStack;
begin
  WriteLn('--- Exception on Empty Pop ---');
  Stack := TIntStack.Create;
  try
    try
      Stack.Pop;
    except
      on E: EStackError do
        WriteLn('Caught: ', E.Message);
    end;
  finally
    Stack.Free;
  end;
  WriteLn;
end;

{ Main }
begin
  WriteLn('=== Generic Stack and Queue Demo ===');
  WriteLn;
  DemoIntStack;
  DemoUndoBuffer;
  DemoTaskQueue;
  DemoPrintQueue;
  DemoExceptions;
  WriteLn('=== All demos complete ===');
end.

Comparison: Pointer-Based vs. Generic

Key Takeaways

1. Generic collections replace pointer-based data structures. The generic versions are safer, shorter, more readable, and just as fast.
2. One definition, unlimited specializations. TStack<Integer>, TStack<String>, TStack<TExpense> — all from one class definition.
3. Circular buffer for queues. The TQueue<T> uses a circular buffer (modular arithmetic on head/tail indices), which is more efficient than shifting array elements.
4. Exception handling integrates naturally. Custom EStackError and EQueueError exceptions provide clear error messages for underflow conditions.