A stack is a rigorously defined abstract data type characterized by its strict Last-In-First-Out discipline and single access point called the top, and it supports two fundamental mutating operations—push to insert a new item at the top and pop to remove and return the most recently inserted item that has not yet been removed—along with auxiliary observations like peek to inspect without removal, isEmpty to check emptiness, and isFull in bounded representations; operationally, a stack’s correctness is captured by the LIFO invariant that the temporal order of pushes is precisely reversed by the order of pops, while its computational model maps neatly onto runtime call stacks in programming language implementations, where compilers automatically push function parameters, return addresses, and local activation records onto a contiguous or linked memory region and later pop them during returns and unwinding; algorithmically, push and pop both execute in constant amortized time O(1) in either array-backed or linked-node-backed representations, with overflow and underflow as well-defined boundary conditions signaled when the structure is full or empty, respectively; semantically, a stack is especially suitable for problems requiring nested, reversible context like recursion, expression evaluation, and backtracking, and conceptually it is commonly explained by the cafeteria-plate analogy in which the last plate placed on a vertical stack is the first one you can take off, matching the LIFO behavior that guides both high-level algorithm design and the low-level mechanics of activation records in languages like C that use conventions such as cdecl with right-to-left parameter pushing and caller- or callee-responsible stack cleanup.

What is push and pop operation of stack? Write the algorithm for push and pop operation.

This article presents a concise yet technically accurate path from definition to implementation for the core operations on a stack, namely push and pop, and then connects these operations to how real compilers manage the function call stack during ordinary and recursive function calls; to keep the discussion both practical and verifiable, you will find step-by-step algorithms for array-based and linked-list-based stacks, code examples that you can execute or translate as needed, a carefully curated walkthrough of a function-call example that shows precisely what gets pushed and popped (parameters, return address, and local variables), a quick-crust summary for fast readers, a clear table of time complexity, and detailed bullet lists of advantages, disadvantages, and applications that highlight when and why a LIFO structure is the right tool for the job; along the way we will clarify important calling-convention details such as right-to-left parameter pushing and who clears the stack in the common cdecl convention, as well as emphasize defensive handling of overflow and underflow, which are the canonical edge conditions for bounded and empty stacks; finally, since recursion relies fundamentally on stacks, we will explain how recursive calls allocate fresh parameter sets and local storage on each invocation and why a correct base case is essential to prevent unbounded growth and eventual stack exhaustion, which in practice manifests as a runtime stack overflow error.

Quick Crust Summary (TL;DR)

• Stack: A LIFO data structure with a single accessible end called the top.
• Push: Insert an element at the top. In arrays: increment top, write value. In linked lists: allocate node, link it before head, move head.
• Pop: Remove and return the element at the top. In arrays: read at top, decrement top. In linked lists: read head, advance head, free node.
• Overflow/Underflow: Overflow if array-backed stack is full; underflow if any stack is empty.
• Time complexity: Push, pop, and peek are O(1); space is O(n).
• Function call stacks: Compilers push parameters (typically right-to-left), the return address, and local variables; they pop them on return. With cdecl, the caller usually cleans parameters.
• Recursion: Each call gets its own activation record on the stack; ensure a base case to avoid stack overflow.
• Applications: Expression evaluation, undo/redo, DFS/backtracking, syntax parsing, and managing nested function calls.

If you only needed the essence: push adds to the top, pop removes from the top—both in O(1); arrays are simple and cache-friendly but bounded, linked lists are flexible and grow dynamically; in compiled languages, these same mechanics power function calls, returns, and recursion by pushing parameters, return addresses, and locals, then popping them when control unwinds.

What Is a Stack, Push, and Pop? A Technical Definition

• Stack: An abstract data type and storage discipline that supports access solely at one end, the top, with a strict LIFO policy: the last element pushed is the first to be popped. Implementation can be bounded contiguous (array) or unbounded linked (singly linked nodes).
• Push(x): A state-transforming operation that writes x to the new top position, provided that the representation invariant (capacity not exceeded for array; allocation success for list) holds; otherwise signals overflow (array) or allocation failure (list).
• Pop(): A state-transforming operation that removes and returns the element at the current top, provided the stack is not empty; otherwise signals underflow.
• Top/Peek(): A read-only observation of the current top element without state change.
• In runtime systems: Compilers manage a call stack where each function activation record (frame) contains pushed parameters, a return address, saved registers, and local variables. On return, these are popped to restore the previous context.
• Analogy: A stack of plates: the last plate put on is the first to be taken off, exactly mirroring LIFO semantics.

Algorithms for Push and Pop: Why Two Implementations Matter

• Array-backed stacks provide constant-time indexing and contiguous storage, which is cache-friendly and simple; however, they are bounded by capacity and must detect overflow when full. They use an integer top index that starts at -1 (empty), increments before write on push, and decrements after read on pop.
• Linked-list-backed stacks grow dynamically and avoid overflow until memory exhaustion; they maintain a reference head (top), and push/pop update head by inserting or removing the first node. They must handle allocation failure and take care to free nodes (in manual-memory languages).
• Both achieve O(1) push and pop by only touching the top/head. Boundary checks—isFull and isEmpty—are mandatory to preserve invariants and avoid undefined behavior.
• For portability and correctness, define clear error semantics: return codes, sentinels, or exceptions for overflow and underflow.
• In practice, either representation integrates seamlessly with algorithmic needs like expression evaluation or call-simulation, but the choice affects memory behavior, failure modes, and resizing strategies.

Array-Based Stack: Push/Pop Algorithms and Code

• Representation: int[] a with fixed capacity N; integer top initialized to -1.
• Push(x) steps:
  1. Check if top == N – 1; if true, report overflow and abort/return error.
  2. Increment top by 1.
  3. Assign a[top] = x.
  4. Return success.
• Pop() steps:
  1. Check if top == -1; if true, report underflow and abort/return error.
  2. Read x = a[top].
  3. Decrement top by 1.
  4. Return x.

// Array-backed stack with overflow/underflow checks (O(1) push/pop)
class IntArrayStack {
    private final int[] a;
    private int top = -1; // empty

    IntArrayStack(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.a = new int[capacity];
    }

    public boolean isEmpty() { return top == -1; }
    public boolean isFull()  { return top == a.length - 1; }

    // PUSH algorithm
    public boolean push(int x) {
        if (isFull()) return false;      // overflow
        a[++top] = x;                    // increment top, then write
        return true;
    }

    // POP algorithm
    public Integer pop() {
        if (isEmpty()) return null;      // underflow
        return a[top--];                 // read then decrement top
    }

    public Integer peek() {
        return isEmpty() ? null : a[top];
    }
}

Linked-List-Based Stack: Push/Pop Algorithms and Code

• Representation: Singly linked nodes; head points to top; each node holds data and next.
• Push(x) steps:
  1. Allocate a new node n; if allocation fails, report memory error.
  2. Set n.data = x.
  3. Set n.next = head.
  4. Set head = n.
  5. Return success.
• Pop() steps:
  1. If head == null, report underflow.
  2. Let n = head and x = n.data.
  3. Set head = head.next.
  4. (Optional in GC languages) Null out n.next; in manual-memory languages, free n.
  5. Return x.

// Linked-list-backed stack grows dynamically; no fixed capacity
class IntListStack {
    private static final class Node {
        int data;
        Node next;
        Node(int d, Node nx) { data = d; next = nx; }
    }

    private Node head = null; // top of stack

    public boolean isEmpty() { return head == null; }

    // PUSH algorithm
    public void push(int x) {
        head = new Node(x, head); // allocate and prepend
    }

    // POP algorithm
    public Integer pop() {
        if (isEmpty()) return null; // underflow
        int val = head.data;
        head = head.next;           // remove first node
        return val;
    }

    public Integer peek() {
        return isEmpty() ? null : head.data;
    }
}

How Push/Pop Power Function Calls: A Step-by-Step Walkthrough

• Consider this program. The compiler uses a call stack to manage the transfer of control and data. It automatically pushes function parameters, the return address, and local variables, and later pops them as control returns. The parameter push order is typically right-to-left under the standard cdecl calling convention.

// C-like example showing what the compiler pushes/pops on the call stack
int add(int i, int j) {
    int sum;
    sum = i + j;
    return sum;
}

int main() {
    int a = 5, b = 2, c;
    c = add(a, b);
    printf("sum = %d", c);
    return 0;
}

• Step-by-step stack activity:
  1. Before call: main has locals a=5, b=2, c (uninitialized).
  2. Call site setup: The compiler pushes b then a (right-to-left) as actual parameters.
  3. Return address push: The address of the next instruction (the printf line) is pushed onto the stack.
  4. Transfer control: CPU jumps to add.
  5. Parameter binding: In add, the pushed values are accessed as i=5 and j=2.
  6. Local allocation: Local variable sum is reserved (conceptually pushed/included) in the current activation record.
  7. Computation: sum = i + j = 7.
  8. Return: The value 7 is prepared as the return value; local sum is popped/released as the frame is torn down.
  9. Pop return address: The saved address is popped, and control transfers back to the printf in main.
  10. Caller cleanup (cdecl): main pops the two pushed parameters (a and b) to restore the stack pointer.
  11. Print: printf consumes c=7 and displays “sum = 7”.
• Key points:
  • The compiler emits the push/pop code; you do not explicitly write it.
  • Right-to-left parameter pushing is standard; caller usually cleans parameters in cdecl.
  • This same mechanism scales to recursion: each call has its own pushed parameters, locals, and return address, ensuring “fresh” state per invocation and correct unwinding.

Recursion and the Stack: Fresh Frames, Base Cases, and Safety

• In recursive functions, each invocation creates a new activation record on the stack, containing pushed parameters, the return address, and any local variables used within that invocation. Because these are pushed per call, each invocation works with a fresh set of parameters, even though the source code reuses the same function definition. When a base case returns without making a further recursive call, the unwinding begins: the current frame is popped, returning control to the previous invocation, which can then continue its computation using the returned value. This continues until the original caller receives the final result. If a recursive function lacks a proper base case or the base case is unreachable, each call will push another frame indefinitely, rapidly filling the stack and causing a stack overflow at runtime. A practical development tip is to instrument recursion with print statements to trace entry/exit and argument values, so you can verify that the base case is hit and that the depth behaves as expected during testing. Conceptually, this execution mirrors the LIFO model: the last recursive call made is the first to return, making stacks a natural fit for recursive algorithms such as factorial, depth-first search, and expression evaluation.

Time Complexity and Space Characteristics

• Push and pop are constant-time because they only adjust or reference the top (array index) or the head (linked node). Space grows linearly with the number of elements. In array-backed stacks, capacity is fixed unless you perform explicit resizing; in linked-list-backed stacks, capacity is effectively bounded by available memory.

Advantages, Disadvantages, and Applications

• Advantages:
  • Simple, predictable O(1) operations: push, pop, and peek touch only the top/head.
  • Natural mapping to function call stacks, including recursion and nested calls.
  • Great for problems with nested scopes or reversible context (e.g., parentheses matching, backtracking).
  • Array-backed stacks are cache-friendly and minimal-overhead; linked stacks are dynamically sized.
• Disadvantages:
  • Array-backed stacks can overflow if capacity is exceeded (unless resized with extra cost).
  • Linked stacks incur pointer overhead and extra allocations; potential fragmentation.
  • Restricted access (top-only) makes random access or arbitrary deletions inefficient/impossible without reorganization.
• Applications:
  • Recursion and runtime call stacks: parameters, return addresses, locals.
  • Expression evaluation and syntax parsing (operators/operands, parentheses matching).
  • Backtracking and DFS in graphs and combinatorial search.
  • Undo/Redo mechanisms and browser navigation history.
  • Evaluating postfix/prefix expressions and converting infix expressions.

Calling Conventions, Parameter Order, and Stack Cleanup

• Under the common cdecl calling convention, actual arguments are typically pushed right-to-left, ensuring that the first parameter appears at the highest address in the callee’s frame. The return address is pushed so that control can resume exactly after the call instruction. Local variables are laid out within the activation record, and on function return, the callee tears down its frame; importantly, the caller often performs parameter cleanup (popping the arguments), which explains why different conventions can alter who is responsible for adjusting the stack pointer. Some other conventions have the callee clean up the parameters instead. While these details are handled by the compiler and ABI, understanding them clarifies why you see consistent push/pop patterns in disassembly and why mismatched declarations can corrupt the stack. The essence remains stack-based and LIFO: the last thing pushed (e.g., the most recent parameter or temporary) is the first thing popped as control returns and the frame is unwound. This mirrors exactly the conceptual stack operations we implement in data structures, reinforcing the value of the push/pop mental model for both high-level programming and low-level execution.