QUESTION 01

What is the stack access rule?

2 marks

Answer

A stack follows last-in, first-out: the most recently inserted remaining value is removed first. All ordinary updates occur at its top.

Explain the stack ADT and array-based push, pop and peek.

5 marks

Answer in brief

A stack supports push, pop and peek at one end called top.

Array representation

Use an array of capacity CAP and an integer top initialised to -1. Empty means top == -1. Full means top == CAP - 1. Valid stored elements occupy indices 0 through top.

Algorithms

push(x): reject a full stack; otherwise increment top and store x.
pop: reject an empty stack; otherwise return a[top] and decrement top.
peek: reject an empty stack; otherwise read a[top] without removing it.

Failure handling

Overflow means a push cannot be accommodated by the chosen representation. Underflow means removal or reading was requested from an empty stack. Use a status result and a separate output parameter instead of a special data value that could also be a legitimate stored item.

Applications

Stacks support undo histories, nested calls, expression processing and backtracking. Their access order is different from a queue’s arrival-order rule. A stack is not automatically sorted by value.

Complexity

A bounded array push, pop or peek needs a fixed number of tests and assignments, so each is O(1). Storage for capacity c is O(c). Traversing or printing all n elements is O(n). The complete program demonstrates successful operations; accompanying checks also exercise empty and full cases.

Diagram or flowchart

CodeBhavya illustration of stack — Explain the stack ADT and array-based push, pop and peek. · Download diagram

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define CAP 6
struct Stack { int values[CAP]; int top; };
int push(struct Stack *s, int value)
{
    if (s->top == CAP - 1) { return 0; }
    s->values[++s->top] = value; return 1;
}
int pop(struct Stack *s, int *out)
{
    if (s->top < 0) { return 0; }
    *out = s->values[s->top--]; return 1;
}
int peek(const struct Stack *s, int *out)
{
    if (s->top < 0) { return 0; }
    *out = s->values[s->top]; return 1;
}

int main(void)
{
    struct Stack s = {{0}, -1};
    int value;
    if (!push(&s, 10) || !push(&s, 20)) { puts("Full"); return 1; }
    if (pop(&s, &value)) { printf("Popped = %d\n", value); }
    if (peek(&s, &value)) { printf("Top = %d\n", value); }
    return 0;
}

Sample input and output

The example uses values in the code.

Output

Popped = 20
Top = 10