Skip to main content

Static vs dynamic implementation of stack

Short answer

A stack is a linear LIFO structure. Static implementation uses a fixed-size array with top index; overflow at MAX-1. Dynamic implementation uses a linked list with top pointing to head node; memory allocates/frees as needed, no fixed overflow but extra pointer per node.

Define Stack. How does static implementation and dynamic implementation of stack differ? Explain.

A stack is a linear data structure in which insertion (push) and deletion (pop) take place only at one end, called the top. The last element inserted is the first one removed, so it follows LIFO (Last In First Out).

Static (array) and dynamic (linked list) implementation

In static implementation the stack is stored in an array of fixed size declared at compile time. In dynamic implementation the stack is a linked list whose nodes are created with malloc when pushed and freed when popped; the pointer top points to the first node.

Static (array)Dynamic (linked list)
Fixed size, set at compile timeGrows and shrinks at run time
Overflow when top == MAX-1Overflow only when heap memory is exhausted
Memory may be wasted if stack is smallMemory used equals number of items (plus pointer per node)
No extra pointer fieldEach node needs an extra pointer
Contiguous memoryNodes scattered in memory
Simple and fastSlightly slower (allocation, pointer handling)
top is an integer indextop is a pointer to the top node

Static code

int s[MAX], top = -1;
void push(int x) { if (top == MAX-1) printf("Overflow"); else s[++top] = x; }
int  pop()       { return (top == -1) ? -1 : s[top--]; }

Dynamic code

struct node { int info; struct node *next; };
struct node *top = NULL;

void push(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    p->info = x;  p->next = top;  top = p;       /* insert at beginning */
}
int pop() {
    if (top == NULL) { printf("Underflow"); return -1; }
    struct node *p = top;  int x = p->info;
    top = top->next;  free(p);                   /* delete first node */
    return x;
}

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 2 questions →