Stack as an Abstract Data Type (ADT)
A stack is an Abstract Data Type (ADT) that organizes elements based on the Last-In, First-Out
(LIFO) principle. In this structure, the element that is most recently added is always the first one to
be removed. This behavior is similar to a stack of plates in the real world—new plates are placed on
top, and removal also happens from the top.
Abstraction in ADT
Being an ADT, the stack specifies what operations can be performed (push, pop, peek, etc.), but it
does not define how these operations are carried out internally.
The user of the stack only interacts with its operations and behavior, without worrying about
whether the stack is implemented using an array, a linked list, or any other structure.
This separation between behavior and implementation is what makes an ADT powerful and
reusable in different contexts.
Implementation Possibilities
• Array-based stack: Uses a fixed-size array and an index to track the top. Simple but has limited
capacity unless resizing is added.
• Linked-list based stack: Each element is stored in a node, with the top pointer referring to the
most recent node. It grows dynamically until memory runs out.
Key characteristics and operations of a stack ADT include:
• LIFO Principle: Elements are added and removed only from one end, referred to as the "top" of
the stack.
• Push: An operation to add an element to the top of the stack.
• Pop: An operation to remove the element from the top of the stack.
• Peek/Top: An operation to view the element at the top of the stack without removing it.
• IsEmpty: An operation to check if the stack contains any elements.
• IsFull (for array-based implementations): An operation to check if the stack has reached its
maximum capacity.
Detailed Operations Explanation
Push Operation
Definition: Push means inserting (adding) an element onto the top of the stack.
Theory: Since a stack follows LIFO, the new element always goes on top. In arrays, the top index is
increased and the element stored. In linked lists, a new node is created and linked as the new top.
Errors: Causes stack overflow if the stack is already full (array implementation).
Pop Operation
Definition: Removes the element currently at the top of the stack.
Theory: Only the most recent element can be removed. In arrays, the value at top is returned and
index decreased. In linked lists, the head node is detached.
Errors: Causes stack underflow if the stack is empty.
Peek / Top Operation
Definition: Returns the element at the top without removing it.
Theory: Useful for checking the next removable element.
Errors: Invalid if the stack is empty.
IsEmpty Operation
Definition: Checks if the stack has zero elements.
Theory: In arrays, true if top == -1. In linked lists, true if top pointer is null.
Errors: None.
IsFull Operation
Definition: Checks whether the stack has reached maximum capacity.
Theory: Applies only to arrays. True if top == capacity - 1.
Errors: Not applicable for linked lists.
Time and Space Complexity
Operation Array (fixed) Array (resizable) Linked list
Push O(1) Amortized O(1) O(1)
Pop O(1) O(1) O(1)
Peek O(1) O(1) O(1)
IsEmpty / IsFull O(1) O(1) IsFull N/A
Space per element O(1) O(1) O(1) + pointer