Stack Abstract Data Type (ADT)
.png)
Definition
A Stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. This means the last element inserted (pushed) into the stack is the first element to be removed (popped) from it. A stack is modeled conceptually as a collection of elements accessible only at one end, called the "top" of the stack. Real-world analogies include a pile of plates or a stack of books, where elements can only be added or removed from the top.
Key Properties
-
LIFO Order: The most recently added element is the first to be removed.
-
Single Access Point: Both insertion and removal operations occur at the "top."
-
Homogeneous Elements: All elements are of the same type.
-
Dynamic/Static Size: Can be implemented with a fixed or dynamic size.
Fundamental Stack Operations
| Operation | Description |
|---|---|
| push(x) | Inserts the element x onto the top of the stack. |
| pop() | Removes and returns the element at the top of the stack. |
| top()/peek() | Returns (without removing) the element at the top of the stack. |
| isEmpty() | Checks whether the stack contains any elements. |
| isFull() | Checks if the stack has reached its capacity (mainly for array-based stacks) |
| size() | Returns the current number of elements in the stack. |
| create() | Initializes a new, empty stack instance. |
| destroy() | Deletes all elements of the stack, freeing resources. |
Example
Suppose you perform the following operations on an empty stack:
-
push(10)
-
push(20)
-
pop() — returns 20
-
push(30)
-
top() — returns 30
At each step, only the topmost element can be accessed or modified.
Stack Implementation Strategies
-
Array-Based: Uses a fixed-size array with a pointer (or index) to the top element. Simple and efficient for known, limited stack sizes, but constrained by the array's maximum capacity.
-
Linked List-Based: Each element is a node with a value and a reference to the next node. Allows dynamic resizing and is only limited by system memory. No "isFull()" unless implementing a max size.
Error Conditions
-
Stack Overflow: Attempting to push onto a full stack (for array-based implementations).
-
Stack Underflow: Attempting to pop or access the top of an empty stack.
Real-World Applications
-
Undo Mechanisms: Stacks keep track of actions for undo/redo functionality in software (e.g., text editors).
-
Function Call Stacks: Compilers/interpreters manage function calling and returns using stacks.
-
Expression Evaluation: In calculators, stacks evaluate arithmetic expressions and manage operator precedence.
-
Balancing Symbols: Used to validate properly nested expressions in code or text (e.g., parentheses, brackets).
Summary Table
| Property | Value |
|---|---|
| Order | LIFO (Last-In, First-Out) |
| Access Point | Top only |
| Common Operations | push, pop, top/peek, isEmpty, isFull, size, create, destroy |
| Implementations | Array, Linked List |
| Applications | Undo/redo, function calls, expression evaluation, balancing symbols |
Join the conversation