A stack represents a constrained linear collection where insertion and removal occur exclusively at one endpoint. This restriction creates a Last-In-First-Out (LIFO) discipline: the most recently added element becomes the first accessible item.

Structural Terminology

• Peak: The active end permitting insertions and deletions
• Base: The static, inaccessible terminal

Fundamental Operations

• Initialization
• Vacancy verification
• Insertion (Push)
• Removal (Pop)
• Peak inspection with out removal
• Deallocation

Array-Based Implementation

Static allocation employs a fixed-size array with a index tracking the peak position.

#define MAX_CAP 128
typedef int Item;

typedef struct {
    Item buffer[MAX_CAP];
    int peakIdx;  // -1 indicates empty
} ArrayStack;

Initialization

void init_stack(ArrayStack *s) {
    s->peakIdx = -1;
}

Vacancy Check

bool is_empty(ArrayStack s) {
    return s.peakIdx == -1;
}

Insertion

bool push(ArrayStack *s, Item val) {
    if (s->peakIdx >= MAX_CAP - 1) return false;
    s->buffer[++s->peakIdx] = val;
    return true;
}

Removal

Item pop(ArrayStack *s) {
    if (s->peakIdx < 0) exit(1);  // Underflow
    return s->buffer[s->peakIdx--];
}

Peak Inspection

Item peek(ArrayStack s) {
    if (s.peakIdx < 0) exit(1);
    return s.buffer[s.peakIdx];
}

Deallocation: For static allocation, resetting peakIdx to -1 suffices; no heap cleanup required.

Linked Implementation

Dynamic allocasion eliminates capacity constraints using nodes.

typedef struct Node {
    Item payload;
    struct Node *succ;
} Node;

typedef struct {
    Node *head;  // Points to peak element
} LinkedStack;

Initialization

bool init_linked(LinkedStack *s) {
    s->head = NULL;
    return true;
}

Vacancy Check

bool is_linked_empty(LinkedStack s) {
    return s.head == NULL;
}

Insertion

bool linked_push(LinkedStack *s, Item val) {
    Node *fresh = malloc(sizeof(Node));
    if (!fresh) return false;
    fresh->payload = val;
    fresh->succ = s->head;
    s->head = fresh;
    return true;
}

Removal

Item linked_pop(LinkedStack *s) {
    if (!s->head) exit(1);
    Node *tmp = s->head;
    Item val = tmp->payload;
    s->head = tmp->succ;
    free(tmp);
    return val;
}

Peak Inspection

Item linked_peek(LinkedStack s) {
    if (!s.head) exit(1);
    return s.head->payload;
}

Deallocation

void destroy_linked(LinkedStack *s) {
    Node *curr = s->head;
    while (curr) {
        Node *tmp = curr;
        curr = curr->succ;
        free(tmp);
    }
    s->head = NULL;
}