Stack ADT; push/pop/peek; array implementation; overflow and underflow

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What does an abstract data type describe? from Lesson 3.1
• With a static variable inside a recursive function, how must you trace it? from Lesson 2.1.4
• In what order do function calls return? from Lesson 1.3.3

1 · The Hook

🎣

In a canteen, clean plates are stacked: a new plate goes on top, and you always take the top plate. Your browser’s Back button, the Undo command of a text editor, and the call stack from Lesson 1.3.3 all work the same way. That behaviour is important enough to get its own data type.

2 · Predict First

🤔

Starting empty: push A, push B, pop, push C, push D, pop, pop, push E, pop, pop. In what order do the items come out? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

B D C E A. Each pop takes whatever is on top at that moment.

The stack ADT

A stack is a collection where items are added and removed at one end only, the top: LIFO, last in first out.

Every operation is O(1).

Array implementation

Keep the items in an array and an index top of the current top item. Empty: top == −1. Push: st[++top] = x. Pop: return st[top--]. Full: top == MAX − 1.

#define MAX 4
int st[MAX];
int top = -1;

int push(int x)
{
    if (top == MAX - 1) { printf("overflow "); return 0; }
    st[++top] = x;
    return 1;
}

int pop(void)
{
    if (top == -1) { printf("underflow "); return -1; }
    return st[top--];
}

int main(void)
{
    push(10); push(20); push(30);
    printf("%d ", pop());
    push(40); push(50); push(60);
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    pop();
    printf("\n");
    return 0;
}

Output

30 overflow 50 40 20 10 underflow

Overflow and underflow

Overflow: pushing onto a full stack (no room in the array). Underflow: popping (or peeking) an empty stack. A correct implementation checks both and reports them instead of writing outside the array.

Why stacks matter

Whenever work must be undone or finished in reverse order of starting, a stack fits: function calls (the call stack), matching brackets, evaluating expressions (next lesson), backtracking and undo.

4 · Visual

After push 10, 20, 30, pop (30), push 40, 50: top is 50. The next push (60) overflows a stack of size 4.

The same stack in 3D: the array grows upward and top marks the highest filled slot.

operation   stack (bottom -> top)   top   output
push 10     10                       0
push 20     10 20                    1
push 30     10 20 30                 2
pop         10 20                    1     30
push 40     10 20 40                 2
push 50     10 20 40 50              3
push 60     (full)                   3     overflow
pop x4      ...                     -1     50 40 20 10
pop         (empty)                 -1     underflow

Trace of the program above.

5 · Worked Examples

Example 1 Easy

Starting with an empty stack: push 1, push 2, push 3, pop, push 4, pop, pop. What is popped, in order, and what is left?

Solution

Popped: 3, 4, 2. Left: 1.

Example 2 Medium

What does this print?

#define MAX 4
int st[MAX];
int top = -1;

int push(int x)
{
    if (top == MAX - 1) { printf("overflow "); return 0; }
    st[++top] = x;
    return 1;
}

int pop(void)
{
    if (top == -1) { printf("underflow "); return -1; }
    return st[top--];
}

int main(void)
{
    push(10); push(20); push(30);
    printf("%d ", pop());
    push(40); push(50); push(60);
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    pop();
    printf("\n");
    return 0;
}

Solution

See the trace table: 30 is popped, then the push of 60 overflows, then 50 40 20 10 are popped and the last pop underflows.

Output

30 overflow 50 40 20 10 underflow

Example 3 GATE

A stack of capacity 5 starts empty. The sequence is push ×4, pop ×2, push ×4, pop ×1. Does an overflow occur, and how many items remain?

Solution

After push×4 and pop×2: 2 items. Push ×4 → 3, 4, 5, then the fourth push finds the stack full: overflow (that item is rejected). Then pop ×1: 4 items remain.

6 · GATE Traps

⚠️

• top == −1 means empty in the usual array version; top == MAX − 1 means full.
• pop on an empty stack is underflow, push on a full stack is overflow.
• peek does not remove the item.
• Do not put two pops in one printf call: the order of evaluating the arguments is unspecified.
• All stack operations are O(1); searching inside a stack is not a stack operation.

8 · Memory Hook

🧠

“Plates in a canteen.” On top, off the top. Nobody pulls a plate from the middle.

9 · Connect the Dots

Lesson 1.3.3 used a stack for function calls; now it is a general data type with an array behind it. Stacks shine when things must be matched or undone in reverse order. Next lesson answers: how does a stack check brackets, and how does it let a computer evaluate an expression like a + b * c without worrying about precedence?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markOrder

Push P, Q, R; pop; push S; pop; pop. What is popped, in order?

• (A) R Q S
• (B) S R Q
• (C) R S Q
• (D) P Q R

Q2MCQ2 marksOutput

What does this print?

#define MAX 4
int st[MAX];
int top = -1;

int push(int x)
{
    if (top == MAX - 1) { printf("overflow "); return 0; }
    st[++top] = x;
    return 1;
}

int pop(void)
{
    if (top == -1) { printf("underflow "); return -1; }
    return st[top--];
}

int main(void)
{
    push(10); push(20); push(30);
    printf("%d ", pop());
    push(40); push(50); push(60);
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    pop();
    printf("\n");
    return 0;
}

• (A) 30 60 50 40 20
• (B) 30 overflow 60 50 40 20
• (C) 30 overflow 50 40 20 10 underflow
• (D) 30 50 40 20 10

Q3NAT1 markIndex

In an array stack with top starting at −1, after 7 pushes and 3 pops, what is top?

Numerical answer: ________

Q4MSQ1 markStack facts

Which are true for a stack?

• (A) popping an empty stack is underflow
• (B) peek returns the top without removing it
• (C) the first item pushed is the first popped
• (D) push and pop take O(1)

Q5NAT2 marksCapacity

A stack of capacity 6 starts empty. Operations: push ×5, pop ×3, push ×5. How many pushes fail with overflow?

Numerical answer: ________

11 · Rule Card

• Stack = LIFO: push, pop, peek, isEmpty, isFull — all O(1).
• Array version: top = −1 empty; st[++top] = x; return st[top--]; full when top == MAX − 1.
• Overflow: push when full; underflow: pop/peek when empty.
• Uses: call stack, undo, bracket matching, expression evaluation, backtracking.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

stack ADTLIFOtoppeekisEmpty / isFullstack overflow (full)underflow

13 · Answer Vault