Stacks: Stacks as ADT

Definition

A stack as an Abstract Data Type (ADT) is a linear collection in which insertion and deletion of elements occur only at one end called the top. The stack ADT specifies a set of operations and their behavior, such as:

push

: insert an element onto the top

pop

: remove the top element

peek/top

: view the top element without removing it

isEmpty

: check whether the stack contains no elements

isFull

: check whether the stack has reached its maximum capacity, if implemented with a fixed-size structure

The ADT defines the logical model of the stack, not the physical storage. In other words, a stack can be implemented using an array, linked list, or other mechanisms, but its external behavior remains the same.

A stack is therefore not just a container of values; it is a carefully defined interface with strict rules of access. Only the top element is directly accessible, which ensures the LIFO order of operation.

Main Content

1. Stack as an Abstract Data Type

A stack ADT describes what operations are available and how they behave, independent of implementation details.
The main property of a stack ADT is restricted access: elements can only be inserted and deleted from one end, the top.

A stack ADT is called an abstract data type because it abstracts away the internal mechanics. For example, when a user performs push(10), they only care that the number 10 is placed at the top of the stack. They do not need to know whether the stack is backed by an array, a linked list, or some other structure.

This abstraction is highly valuable in software design. It helps programmers reason about problems more clearly and allows different implementations to be swapped without changing the code that uses the stack.

Example of stack behavior:

Bottom -> [ 10 ] [ 20 ] [ 30 ] <- Top

If pop() is called, only 30 is removed because it is the topmost element.

The stack ADT usually includes these standard operations:

push(x) to add x
pop() to remove and return the top item
top() or peek() to return the top item without removing it
isEmpty() to test whether the stack is empty
size() to determine the number of elements

Because the ADT is defined by behavior, not by storage, its correctness depends on following the LIFO rule consistently.

2. Fundamental Stack Operations

Push and pop

are the core operations of the stack.

Peek, isEmpty, and size

help manage and inspect the stack safely.

Push

push inserts a new element onto the top of the stack.

Example: If the stack currently contains:

Bottom -> [ A ] [ B ] <- Top

and push(C) is performed, the stack becomes:

Bottom -> [ A ] [ B ] [ C ] <- Top

Pop

pop removes the top element and returns it.

Using the same stack:

Bottom -> [ A ] [ B ] [ C ] <- Top

pop() removes C, leaving:

Bottom -> [ A ] [ B ] <- Top

If pop is attempted on an empty stack, it causes underflow.

Peek / Top

peek() or top() returns the top element without removing it.

For the stack:

Bottom -> [ A ] [ B ] [ C ] <- Top

peek() returns C, but the stack remains unchanged.

isEmpty

This operation checks whether there are any elements in the stack.

Returns true if the stack contains no elements
Returns false otherwise

size

This operation returns the number of elements currently stored in the stack.

These operations are generally designed to run in O(1) time, meaning they take constant time regardless of the number of elements.

3. Stack Behavior, Restrictions, and Implementation View

A stack allows access only at the top, making it simple and efficient.
Stacks can be implemented using different data structures, most commonly arrays and linked lists.

Restricted Access

A stack does not allow random access to middle elements the way arrays do. If an element is not at the top, it must first be removed indirectly by popping the elements above it.

This restricted access is what makes the structure behave like a stack. It enforces a disciplined order of use.

Implementation Independence

Because the stack is an ADT, it can be realized in multiple ways:

Array-based stack

Uses contiguous memory
Simple and efficient
May have fixed capacity unless dynamic resizing is used

Linked-list-based stack

Uses nodes connected by links
Can grow dynamically
Does not require contiguous memory

Regardless of implementation, the observable behavior must remain the same:

push adds to the top
pop removes from the top
peek reads the top
underflow occurs when popping from an empty stack

Example of Stack Usage in Real Life

A stack resembles a stack of plates:

You add a plate to the top
You remove a plate from the top
You do not remove a plate from the middle without disturbing the ones above it

This analogy helps explain why the structure is both intuitive and practical.

Working / Process

1. Initialize the stack

Create an empty stack.
Set the top position to empty or null depending on implementation.

2. Perform stack operations

Use push to insert elements.
Use pop to remove the top element.
Use peek to inspect the top element.
Check isEmpty before popping to avoid underflow.

3. Maintain LIFO order

Ensure the most recently pushed element is always the first one removed.
Update the top reference or top index after every insertion or deletion.
Continue until the stack becomes empty or the process ends.

Example process:

Start:   empty stack
push(5): [5]
push(8): [5, 8]
push(3): [5, 8, 3]
pop():   removes 3 -> [5, 8]
peek():  returns 8
pop():   removes 8 -> [5]

This process shows how the stack grows and shrinks only at one end.

Advantages / Applications

Simple and efficient structure

: Stack operations such as push and pop are typically very fast, often O(1).

Useful in recursion and function calls

: Program execution uses a call stack to store return addresses, local variables, and function contexts.

Wide range of applications

: Stacks are used in expression evaluation, syntax parsing, undo/redo systems, backtracking, browser navigation, and depth-first search.

Examples of applications:

Undo/Redo in editors

: The most recent action is the first one to be undone.

Browser history

: The last visited page is the first one to be returned to when using back.

Expression conversion and evaluation

: Infix, postfix, and prefix expressions often rely on stack processing.

Balanced parentheses checking

: Stacks help verify whether symbols are properly nested.

Backtracking algorithms

: Maze solving, path finding, and recursive search problems often use stack behavior.

The stack is especially valuable wherever the latest task, item, or state must be handled first.

Summary

A stack is a linear ADT that follows the LIFO rule.
Stack operations are restricted to one end called the top.
The stack ADT defines behavior, not internal representation.
Important terms to remember
Stack
Abstract Data Type (ADT)
LIFO
Push
Pop
Peek / Top
Underflow
Overflow
Top
Implementation