Stacks: LIFO, push/pop and a bounded array

What you will learn

A stack stores a sequence but allows insertion and removal at only one end, called the top. You will distinguish the stack's logical contents from its backing array, trace successful and failed operations, and implement a capacity-three integer stack without dynamic allocation.

Prerequisites: ordinary C int variables, assignment, comparisons, if, functions and return, fixed-size arrays and zero-based indexing. For int a[3], valid indices are 0, 1 and 2. If you studied “Recursion: base case and call stack,” you have met the last-called/first-returned idea. That is useful context, but implementing recursion is not required here. Structures and the limited file-scope syntax used below are explained here.

This is one foundation lesson for GATE CS preparation, not a full data-structures course. Applications such as expression evaluation, recursion implementation, multiple independent stacks, resizing, linked storage and concurrent access are outside its scope.

One end and a precise analogy

Think of a narrow holder of plates where you can add or remove only the top plate. Placing 4, then -1, then 7 puts 7 on top. Removing plates yields 7, then -1, then 4. This rule is LIFO: last in, first out, meaning the most recently inserted element that has not already been removed comes out next. A later push may become the next pop, even if older items remain.

The holder has room for exactly three plates. Trying to add a fourth fails; trying to remove from an empty holder also fails. This analogy describes access order and capacity. It does not imply that C arrays move vertically, that popped bytes are erased, or that every real stack has capacity three.

push(x) adds x at the top if space exists. pop() removes and reports the top if an element exists. A top inspection without removal is often called peek, but we do not implement it here. Stack order depends on arrival order, not numerical size: a negative value can be on top of a positive one.

Representation and explicit bounds

Our program manages exactly one stack using data[3] and used.

• Capacity is always 3: three allocated int slots, indexed 0 through 2.
• used counts live elements, so the invariant is 0 <= used <= 3. An invariant is a fact true initially and preserved by every allowed operation.
• Live contents, written bottom to top, are data[0] through data[used - 1] when used > 0.
• The top index is used - 1 only when nonempty. When empty, there is no top element.
• When not full, index used is the next insertion position. At full capacity used == 3, it is not a valid array index and must not be accessed.
• Unused slots are not logical elements. They can contain initial zeroes or stale values left by earlier pops.

The initial stack is empty, even though all three backing slots are initialized to zero. Callers must not directly alter used or the backing array; use only the shown push/pop operations after initialization. Calls happen one at a time, with no concurrent access. The program is not a validator for arbitrary corrupted state. Every stored value may be any representable C int, including -1, 0, INT_MIN and INT_MAX; the operations copy payloads without adding to them. INT_MIN and INT_MAX name the implementation's smallest and largest int values in <limits.h>, used in the separate validation program. We do not assume a particular bit width. Only the small counter is incremented/decremented, within the established bounds.

Separate success from a stored value

push returns status 1 on success and 0 on full-stack failure. Its return is not the inserted value. For pop, a single integer return with -1 meaning “empty” would be ambiguous: -1 is a valid stored item. We instead return a structure with two fields:

• ok: 1 for success, 0 for empty-stack failure;
• value: the removed item, meaningful only when ok == 1.

Our failed pop initializes value to 0, but this is only a placeholder. It does not mean the stack contained 0. Always check ok before using the payload. Returning a structure avoids pointer/output-parameter syntax in this first implementation.

Complete C11 program

Predict the output before reading the trace. Every state-changing call is a separate statement before printing, so the output does not depend on the order in which C evaluates function arguments.

#include <stdio.h>

static int data[3] = {0, 0, 0};
static int used = 0;

struct PopResult {
    int ok;
    int value;
};

int push(int value) {
    if (used == 3) {
        return 0;
    }
    data[used] = value;
    used = used + 1;
    return 1;
}

struct PopResult pop(void) {
    struct PopResult result = {0, 0};
    if (used == 0) {
        return result;
    }
    used = used - 1;
    result.ok = 1;
    result.value = data[used];
    return result;
}

int main(void) {
    struct PopResult result;
    int status;
    result = pop();
    printf("empty: %d %d\n", result.ok, used);
    status = push(4);
    printf("push 4: %d %d\n", status, used);
    status = push(-1);
    printf("push -1: %d %d\n", status, used);
    status = push(7);
    printf("push 7: %d %d\n", status, used);
    status = push(9);
    printf("full: %d %d\n", status, used);
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    status = push(2);
    printf("push 2: %d %d\n", status, used);
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    result = pop();
    printf("empty again: %d %d\n", result.ok, used);
    return 0;
}

Syntax used by this program

#include <stdio.h> supplies the declaration for printf. %d prints one int; the values following the format string supply the placeholders from left to right. \n starts a new output line. Quotation marks delimit text.

Declarations before all functions have file scope: these functions can refer to the same data and used objects. Here static gives those names internal linkage, keeping them within this source file; file-scope objects also live throughout program execution. There is one shared stack, not a fresh array per operation. This deliberately small design is not an interface for creating many independent stacks.

struct PopResult { ... }; defines a structure type, a record with two named int fields. The semicolon after the closing brace is required. struct PopResult result = {0, 0}; creates a local record and initializes ok, then value, in declaration order. result.ok and result.value select its fields using the dot operator. A function declared struct PopResult pop(void) returns such a record by value; void in its parameter list means it takes no arguments. return result; copies the result value to the caller; it does not expose a local variable after its lifetime ends. Assigning result = pop(); stores the returned record in the caller's variable. The caller's result and pop's local result are separate objects despite having the same name.

int main(void) is the program's entry point with no parameters; its final return 0 indicates normal completion. = assigns; == compares for equality. Braces group statements; an executed return exits its function immediately. data[used] selects an array element using the current counter as the index. The program uses explicit used = used + 1 and used = used - 1, avoiding pre/post-increment notation. result in main is assigned a complete returned record before any of its fields are read; status is likewise assigned before printing.

Worked trace 1: success and both failures

Square brackets below describe logical contents from bottom to top, not every backing slot.

Exact program output:

empty: 0 0
push 4: 1 1
push -1: 1 2
push 7: 1 3
full: 0 3
pop: 7 2
pop: -1 1
push 2: 1 2
pop: 2 1
pop: 4 0
empty again: 0 0

The removed sequence is 7, -1, 2, 4. The failed push never inserts 9. The successful pop of -1 has ok == 1, so it is not an empty-stack signal.

Worked trace 2: storage is not membership

After successful pushes of 4, -1 and 7, backing storage is [4, -1, 7] and used is 3. Pop first decrements used to 2, then reads data[2], returning 7. Storage remains [4, -1, 7]; the logical stack is now [4, -1]. No shifting or clearing occurs. A second pop makes used 1 and returns data[1] == -1. Now push(2) writes index 1 and makes used 2: storage is [4, 2, 7] but live contents are [4, 2]. The stale 7 at index 2 is not the top. This is why we track the count instead of searching for a special “empty” payload value.

Why each access is safe, and why order matters

Initially used == 0, satisfying the invariant. A full push returns before changing either storage or count. Otherwise the invariant gives 0 <= used <= 2; data[used] is valid. After writing, increasing the count gives 1 <= used <= 3. The old elements keep their order and the new value becomes the last live element.

An empty pop returns before any array access or counter change. Otherwise old used lies from 1 through 3. Decrementing first gives an index from 0 through 2, precisely the old top index. Reading that slot returns the last live element, and the new live prefix excludes it. The counter remains within bounds. Both failure paths leave the entire backing array and used unchanged. The returned result record is an output, not part of stored stack state.

Do not read data[used] before decrementing on pop: it is outside the live stack, and when full it is outside the array. Do not decrement an empty count or write before checking full. C performs no automatic array bounds checking. We reason about these faulty alternatives without executing invalid accesses.

Each push/pop performs a bounded number of tests, assignments and one possible array access, so each has O(1) worst-case time in this fixed-array model. This means the work does not grow with the number of currently stored items; it does not promise a particular number of CPU cycles. This implementation always reserves three integer slots plus a counter; for an analogous fixed capacity C, backing storage is O(C) and operations remain O(1), assuming the counter can represent C. Dynamic resizing is a different implementation and is not being analyzed here.

Key box

• LIFO selects the latest still-present insertion, not the largest value or earliest insertion.
• used is a count. Nonempty top index is used - 1; next insertion index is used only when not full.
• Empty: used == 0; full: used == 3.
• Push checks full before writing. Pop checks empty before decrementing or reading.
• Failed operations preserve storage and count.
• Pop success and payload are separate; -1 and 0 are ordinary possible values.
• Removing an item changes logical membership; it need not erase the old bytes.

Try it first: two short trace exercises

Exercise 1: empty, one element, empty again

Start empty. Run push(0), pop(), pop(). Before checking, write the count after every step and each operation's status; report a removed value only on success.

Worked answer: push(0) returns 1 and changes used from 0 to 1; contents are [0]. The first pop returns {1, 0} and changes used to 0. It successfully removes the stored zero. The second pop returns {0, 0}, leaves used at 0 and removes nothing. Backing storage is [0, 0, 0] throughout, but logical membership changes. This shows why counting zero-valued slots cannot determine whether the stack is empty.

Exercise 2: failed push, then successful pop

Start empty. Run push(5), push(-1), push(6), push(9), pop(), push(2). Predict the failed operation, the removed value, final used, and final bottom-to-top contents.

Worked answer: the first three pushes succeed, producing [5, -1, 6] with used == 3. push(9) returns 0 and changes nothing. Pop therefore returns {1, 6}, not 9, and leaves [5, -1] with count 2. push(2) now succeeds by reusing index 2. The final stack is [5, -1, 2], used == 3. Failure did not consume a slot or replace a value; a successful pop made room for the later push.

Before moving on

Draw the bottom-to-top sequence after every operation, including failed ones. If you return the oldest value, revisit LIFO. If you use index 3, separate capacity, count and top index. If you treat -1 as failure, check the status field. If a stale value seems to reappear, mark the live prefix selected by used.

Source and scope note

This original offline foundation continues the reviewed local recursion teaching context, especially separate call state and bounded array prefixes. It makes no fresh syllabus verification or exam-year assignment. The program uses C11 as a teaching choice. Its six original single-choice exercises are not official previous-year questions, a full mock or evidence of complete course coverage. No content has been published or imported into a CMS.

Six original practice questions

Choose exactly one option per question. Use the shown capacity-three implementation.

Question 1

Starting empty, perform push(6), push(-1), pop(), push(8), pop(), pop(). All pushes fit. Which values do the three successful pops return, in order?

A. 6, -1, 8 B. -1, 8, 6 C. 8, -1, 6 D. -1, 6, 8

Question 2

Capacity is 3. Starting empty, push(2), push(5), push(-1), then push(9). What does the fourth push return and what is the resulting logical stack, bottom to top?

A. 1; [5, -1, 9] B. 0; [2, 5, 9] C. 0; [2, 5, -1] D. 1; [2, 5, -1, 9]

Question 3

In the shown implementation used == 2. Which statement is correct?

A. The top is at index 2 and the next push writes index 3. B. The top is at index 1 and the next successful push writes index 2. C. The top is at index 0 because there are two elements. D. The stack is full because index 2 is its largest valid index.

Question 4

Start empty, successfully push(-1), then call pop twice. Which pair of returned records (ok, value) matches the exact shown code?

A. (0, -1), (0, -1) B. (1, -1), (1, 0) C. (1, 0), (0, -1) D. (1, -1), (0, 0)

Question 5

Start empty and perform push(3), push(4), pop(), push(8). What are the entire backing array data[0..2], used, and the top value in the exact shown implementation?

A. [3, 8, 0]; used=2; top=8 B. [3, 4, 8]; used=3; top=8 C. [8, 3, 0]; used=2; top=3 D. [3, 4, 0]; used=2; top=4

Question 6

Assume the invariant 0 <= used <= 3 before pop. Which reasoning establishes safe array access for every allowed state?

A. Read data[used] first, then check empty; an array automatically checks its indices. B. Always decrement first, even if empty; a negative index represents no element. C. Return immediately when used==0; otherwise decrement a count from 1..3 to 0..2, then read that index. D. Read data[used-1] even when used==0; the returned status will cancel that read.

Answers and option feedback

1: B

A is incorrect. It removes the earliest arrival first; after the first two pushes the top is -1, not 6.

B is correct. Contents evolve [] → [6] → [6,-1] → [6] → [6,8] → [6] → []; the removed values are -1, 8, 6.

C is incorrect. 8 has not been pushed when the first pop occurs. You cannot reverse all future insertions as a batch.

D is incorrect. After push(8), 8 is above 6, so the second pop must remove 8.

2: C

A is incorrect. Full push does not discard the oldest element or report success.

B is incorrect. Failure must not overwrite the current top -1 with 9.

C is correct. After three successes used is 3. The full guard returns 0 before any write; count and all slots stay unchanged.

D is incorrect. The array holds at most three elements. The guard prevents inserting a fourth element.

3: B

A is incorrect. It confuses a count with a top index and would insert beyond the array.

B is correct. Two live elements occupy indices 0 and 1. Thus top is used-1=1, and unused slot 2 accepts the next push.

C is incorrect. Index 0 is the bottom; with two elements index 1 is the top.

D is incorrect. used=2 means two occupied slots, not all three. Full requires used=3.

4: D

A is incorrect. -1 is an admitted payload; its successful removal must have ok=1. The failed record is initialized to (0,0), not (0,-1).

B is incorrect. After the first removal the stack is empty; the second ok is 0. A placeholder zero is not a successfully removed element.

C is incorrect. The successful payload is -1, not 0. On failure the code leaves the initialized record (0,0).

D is correct. First pop changes used from 1 to 0 and returns (1,-1). Second pop returns its initial (0,0) without changing the stack; its value field is not a payload.

5: A

A is correct. After two pushes storage is [3,4,0] and used=2. Pop sets used=1 and returns 4 without erasing. Push(8) overwrites slot 1 and sets used=2; top is data[1]=8.

B is incorrect. Pop reduced the live count. The next push reuses slot 1 rather than appending at slot 2.

C is incorrect. Push does not shift the old bottom 3; it remains at index 0.

D is incorrect. Push(8) succeeds because space exists, so it must replace the stale 4 in slot 1.

6: C

A is incorrect. C provides no automatic bounds check, and at full capacity data[3] is out of bounds. At smaller counts this is not the live top either.

B is incorrect. Decrementing zero gives -1, outside the valid index range and outside the count invariant. A negative index is not an empty marker.

C is correct. The early return prevents all empty-case reads. A nonempty old count is 1, 2 or 3; after subtraction the index is 0, 1 or 2, the old top.

D is incorrect. Empty used gives index -1. A later status cannot undo an invalid access that already occurred.