Stack: Last In, First Out (LIFO)

01 What is a Stack?

In precise computer science terminology:

Its overarching law of operation is:

Meaning: The element that enters last is unconditionally the element that gets removed first.

02 The Restaurant Plate Stacking Analogy

Consider a kitchen staff washing plates and stacking them upright:

By forbidding access from the bottom or middle, the system remains completely stable and predictable.

03 Primary Stack Operations

Three primary methods govern all interactions with a stack:

04 How Push Works

Watch how pushing three numbers step-by-step builds the vertical structure:

Every newly pushed element covers the preceding element and claims the role of Top.

05 How Pop Works

With 30 currently at the Top, successive pop() invocations produce:

06 The Peek Operation

Programs frequently need to inspect what is on top of the stack without mutating its state:

07 The Universal Stack Interface

Every standard stack implementation provides these four core methods:

08 Is a Stack a Dedicated Physical Memory Type?

A crucial distinction must be made here.

As a data structure, a Stack is an Abstract Data Type (ADT). It is not a special piece of hardware; it is purely a behavioral contract. You can implement a stack on top of an Array, or on top of a Linked List.

Meanwhile, the operating system and CPU possess a physical memory region known as the Call Stack. It is called a "stack" precisely because it operates according to this exact LIFO discipline!

09 Building a Stack with an Array

The end of an array serves as the ideal, high-speed Top:

class ArrayStack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)      # O(1) append at array tail

    def pop(self):
        if not self.isEmpty():
            return self.items.pop()  # O(1) removal from array tail
        raise IndexError("Stack Underflow")

    def peek(self):
        return self.items[-1] if not self.isEmpty() else None

    def isEmpty(self):
        return len(self.items) == 0
        

Because appending and popping at the end of an array requires zero element shifting, operations run in blazing-fast $O(1)$ time!

10 Building a Stack with a Linked List

If we designate the Linked List's Head as our Top:

Pushing a new element 40 simply prepends it before Head:

And popping shifts Head to Head.next. Both operations execute in constant $O(1)$ time without requiring predefined capacity limits.

11 The Sacred Rule: Restricted Access

A stack's strength comes from its strict constraints:

This intentional restriction safeguards system state: no intermediate data can be corrupted or extracted out of order.

12 Browser Navigation & The Back Button

As you surf the web, pages you visit are placed sequentially onto a history stack:

Inside the browser's navigation engine, the history stack looks like this:

When you click the Back button, the browser pops GitHub off the stack and returns you directly to Wikipedia.

13 Text Editor Undo / Redo Mechanisms

Every edit action in VS Code or word processors pushes a discrete command onto an Undo stack:

Pressing Ctrl + Z pops the most recent action ("Add '!'") and reverts it. The LIFO rule allows applications to retrace steps backward in exact reverse chronological order.

14 Function Calls & The Operating System Call Stack

Here is the most profound application of stacks in all of computing: how CPUs execute code:

As functions call one another, the runtime pushes activation records onto the Call Stack:

When validate() finishes, its frame is popped first. Control returns seamlessly to login(), and finally back to main(). Without the stack discipline, nested subroutine calls would be impossible to manage.

15 What Actually Lives Inside a Stack Frame?

A Stack Frame (or Activation Record) is a rich execution capsule containing:

The instant the function returns, the entire frame is popped, instantly releasing all local variable memory!

16 What is a Stack Overflow?

The OS call stack has a strictly bounded size (typically 1 MB to 8 MB).

If a recursive function lacks a valid base termination condition and repeatedly calls itself:

Each recursion pushes a new frame. Eventually, the allotted stack memory is exhausted, and the program crashes catastrophically:

17 What is a Stack Underflow?

Conversely, if a program attempts to call pop() or peek() on an already Empty stack, this error condition is called Stack Underflow.

Robust software guards against underflow by always verifying isEmpty() prior to popping.

18 Are Stacks Always Unlimited in Size?

Capacity depends entirely on the backing data structure:

19 Time Complexity of Stack Operations

In any well-designed stack implementation, every fundamental operation runs in rapid constant time:

20 Where Are Stacks Actually Used?

Stacks are far from academic curiosities; they drive foundational software systems:

21 Stack vs. Array — The Core Difference

Are stacks and arrays just different words for the same thing?

22 Stack vs. Linked List

A Linked List is a general-purpose traversable chain: you can insert in the middle, search arbitrary nodes, or iterate through.

A Stack restricts the linked list by sealing all entry and exit doors except the front head node, transforming it into a high-speed LIFO conduit.

23 The Core Engineering Trade-off

The trade-off is clean and stark:

24 Remember the Stack as a Narrative

The entire character of a stack captured in two simple lines:

The entry order and exit order are exact inverses—that is the rhythm of LIFO.

25 Seven Golden Principles of Stacks

26 Next Destination: Where the Earliest Arrival Takes Priority!

Our linear data structure journey has revealed three distinct architectures:

But what if serving the newest item first causes total chaos? Think of an airport check-in desk, a printer document spooler, or a bank counter. In those systems, fairness demands:

“Whoever arrived first must be served first — First In, First Out (FIFO)!”

That fair waiting line is the: Queue. In our next lesson, we will see how queues are constructed and why they power asynchronous system architectures worldwide.