Past exam question: 2063 Baishakh (Regular / Back), Q2(b)
Open in the Padhaiko appQuestion
Discuss the implementation of stack array.
Solution
Array Implementation of Stack ADT: A stack of integers is stored in a fixed-size array items[MAX] alongside an integer top initialized to -1 (empty stack):
#define MAX 100
typedef struct {
int items[MAX];
int top;
} Stack;
void init(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
int isFull(Stack *s) { return s->top == MAX - 1; }
void push(Stack *s, int x) {
if (isFull(s)) { printf("Overflow\n"); return; }
s->items[++(s->top)] = x;
}
int pop(Stack *s) {
if (isEmpty(s)) { printf("Underflow\n"); return -1; }
return s->items[(s->top)--];
}
All operations (isEmpty, isFull, push, pop, peek) execute in time.
Answer:
An array stack pairs items[MAX] with an integer index top = -1, incrementing top on push (overflow at MAX - 1) and decrementing top on pop (underflow at -1) in time.