Understanding Abstract Data Types (ADTs)

An Abstract Data Type defines what a structure does, but not how it is implemented in memory. In C, we can implement the same ADT using either static arrays or dynamic linked lists.

The Stack (LIFO)

A stack follows the Last-In, First-Out principle. Imagine a stack of dinner plates: you can only add or remove the plate at the top.

Operations:

• Push: Add an item to the top.
• Pop: Remove the top item.
• Peek: Look at the top item without removing it.

Array-Based Implementation

An array is the fastest way to build a stack if you know the maximum size in advance.

#define MAX 100
int stack[MAX];
int top = -1;

void push(int val) {
    if (top < MAX - 1) stack[++top] = val;
}

int pop() {
    if (top >= 0) return stack[top--];
    return -1; // Error
}

The Queue (FIFO)

A queue follows the First-In, First-Out principle. Like a line at a supermarket, the person who arrived first is served first.

Operations:

• Enqueue: Add to the back.
• Dequeue: Remove from the front.

The Circular Buffer

If you use a simple array for a queue, “dequeuing” from the front leaves wasted space at the beginning. To solve this, we use a Circular Buffer where the tail wraps back to the beginning of the array when it reaches the end.

Choosing an Implementation

// if top initialized to -1
void push(int x) {
    stack[] = x;
}

Practical Application: Function Calls

The CPU itself uses a stack to manage function calls. When main() calls sum(), the current state of main is pushed onto the Hardware Stack. When sum finishes, it is popped, and execution returns to main.