Stack Concept and Push/Pop Operations | Data Structures

A Stack is a linear Abstract Data Type governed by a strict ordering principle: Last-In, First-Out (LIFO). The last element added to the stack is the first element to be removed.

The Cafeteria Tray Analogy

Think of a spring-loaded tray dispenser in a cafeteria:

Clean trays are placed on the top of the stack (Push).
Customers take trays from the top of the stack (Pop).
You cannot remove a tray from the bottom without removing every tray above it.

           +-------+
Push(30) ->|  30   | -> Top of Stack
           +-------+
           |  20   |
           +-------+
           |  10   |
           +-------+

Core Stack Operations

All core stack operations execute in O(1) constant time:

Operation	Description	Time Complexity
`push(element)`	Inserts an element onto the top of the stack	`O(1)`
`pop()`	Removes and returns the top element	`O(1)`
`peek()`	Inspects the top element without removing it	`O(1)`
`isEmpty()`	Checks whether the stack has zero elements	`O(1)`
`size()`	Returns the number of elements in the stack	`O(1)`

Implementation 1: Array-Backed Stack

An array-backed stack maintains a pointer variable topIndex:

class ArrayStack<T>(private val capacity: Int = 100) {
    private val storage = arrayOfNulls<Any>(capacity)
    private var top = -1

    fun push(item: T) {
        check(top < capacity - 1) { "Stack Overflow" }
        storage[++top] = item
    }

    @Suppress("UNCHECKED_CAST")
    fun pop(): T {
        check(top >= 0) { "Stack Underflow" }
        val item = storage[top] as T
        storage[top--] = null // Prevent memory leak in managed runtimes!
        return item
    }

    @Suppress("UNCHECKED_CAST")
    fun peek(): T {
        check(top >= 0) { "Stack is empty" }
        return storage[top] as T
    }

    fun isEmpty(): Boolean = top == -1
}

Implementation 2: Linked-List Stack

A linked-list stack inserts and removes nodes exclusively at the head:

class LinkedStack<T> {
    private class Node<T>(val data: T, val next: Node<T>?)
    private var top: Node<T>? = null

    fun push(item: T) {
        top = Node(item, top) // Prepend to head
    }

    fun pop(): T {
        val node = top ?: throw NoSuchElementException("Stack is empty")
        top = node.next
        return node.data
    }

    fun peek(): T = top?.data ?: throw NoSuchElementException("Stack is empty")
    fun isEmpty(): Boolean = top == null
}

Summary

Stacks follow LIFO (Last-In, First-Out).
All primary operations (push, pop, peek) operate in strict O(1) constant time.
Can be implemented efficiently with dynamic arrays or singly linked lists.