Introduction to Stack

Imagine a stack of plates in a kitchen. Whenever you add a new plate, you place it on the top. When you need a plate, you also take it from the top. You never remove a plate from the middle because every plate above it blocks your access.

A Stack works in the same way. The last item placed on the top is the first item removed. This order is called Last In, First Out (LIFO). LIFO is the main idea behind every Stack operation.

Stacks support many familiar tasks such as undo actions, browser history, function calls, recursion, expression evaluation, backtracking, and depth-first search.

What is a Stack?

A Stack is a linear data structure that stores elements in Last-In-First-Out (LIFO) order. The most recently added element is removed first.

The word linear means that the elements form a sequence. However, a Stack does not allow direct access to every position in the sequence. All important actions happen at one end called the top.

Core Rules

A Stack follows three simple rules:

• New elements are always added at the top.

• Only the top element can be removed or accessed.

• The last element to go in is the first element to come out.

Since only the top is accessible, reaching a middle element requires removing everything above it.

A Simple Stack View

Suppose 10, 20, and 30 are added in the same order. The value 30 is the newest element, so 30 becomes the top and leaves first.

The removal order is 30 -> 20 -> 10.

Basic Terminology

• Element or item: A value stored in the Stack.

• Top: The end used to add, remove, or read an element.

• Bottom: The oldest end of the Stack.

• Size: The current number of elements in the Stack.

• Capacity: The maximum number of elements that a fixed-size Stack can hold.

• Empty Stack: A Stack containing no elements.

Stack Operations

A Stack has a small set of operations. Each operation keeps the focus on the top.

Push

Push adds a new element to the top. If the Stack contains 10 and 20 from bottom to top, pushing 30 places 30 above 20 and makes 30 the new top.

Pop

Pop removes the top element. Many Stack interfaces also return the removed value. If the Stack contains 10, 20, and 30, a pop removes 30 and makes 20 the new top.

Peek or Top

Peek reads the top element without removing it. If the top value is 30, peek returns or shows 30 while the Stack remains unchanged. Pop changes the Stack but peek does not.

isEmpty

isEmpty checks whether the Stack contains zero elements. The result is true for an empty Stack and false when at least one stored element remains.

Size

Size returns the current number of stored elements. After three successful pushes and one pop, the size is 2.

isFull

isFull checks whether a fixed-size Stack has reached its capacity. A Stack with capacity 5 is full when its size becomes 5. Dynamic Stacks usually do not need this operation because their storage can grow.

Search

Search looks for a value in the Stack. Search is not a core Stack operation because a deeper element cannot be reached directly from the top.

Traversal

Traversal visits every element in the Stack. A traversal normally starts at the top and continues toward the bottom without changing the LIFO rule.

Stack Overflow and Underflow

Stack Overflow

Stack overflow happens when a push is attempted but no space is available. A fixed-size Stack overflows after reaching its capacity. The program call stack can also overflow when recursion becomes too deep or never stops.

Stack Underflow

Stack underflow happens when pop or peek is attempted on an empty Stack. Different interfaces may return a special result or raise an error. Checking isEmpty before reading or removing the top helps prevent underflow.

Dry Run of Stack Operations

Types of Stack

Fixed-Size Stack

A fixed-size Stack has a capacity decided before use. A fixed array is a common storage choice. The design is simple and memory use is predictable. However, no new element can be pushed after the Stack becomes full. A large capacity can also leave unused spaces when only a few elements are stored.

Dynamic Stack

A dynamic Stack grows when more elements are added. A resizable array or a linked list can support dynamic growth. A resizable array creates a larger storage block and copies the old elements when the current block becomes full. A linked list creates one new node for each pushed element. Available system memory still sets a practical limit.

Different Implementations of Stacks

The Stack rules describe the required behavior. Arrays and linked lists provide two common ways to store the elements while preserving the same LIFO order.

Array Implementation

An array-based Stack stores elements next to one another in memory. A position called top identifies the newest element. A fixed array has a set capacity while a dynamic array can grow by creating a larger array and copying the existing elements.

• Push: Store the new element after the current top and move the top position forward. Time Complexity is O(1) when free capacity is available. A dynamic-array resize takes O(N) for that push, so push is amortized O(1) across many operations.

• Pop: Remove the element at the top and move the top position backward. Time Complexity is O(1).

• Peek or Top: Read the element at the top position without changing the Stack. Time Complexity is O(1).

• isEmpty: Check whether the size is zero or the top position is -1. Time Complexity is O(1).

• Size: Return the stored count or calculate top + 1. Time Complexity is O(1).

• isFull: Compare the current size with the capacity of a fixed array. Time Complexity is O(1). A dynamic array usually does not expose isFull.

• Search: Check elements until the required value is found or the Stack ends. Time Complexity is O(N) in the worst case.

• Traversal: Visit every stored element from top to bottom or bottom to top. Time Complexity is O(N).

• Space: Storing N elements requires O(N) space. A dynamic array may also keep some unused capacity for future pushes.

Linked-List Implementation

A linked-list Stack stores every element in a separate node. Each node keeps a value and a link to the next node. The head node is normally treated as the top, so push and pop happen at the front of the list.

• Push: Create a new node and connect the new node before the current top. Time Complexity is O(1).

• Pop: Remove the top node and move the top reference to the next node. Time Complexity is O(1).

• Peek or Top: Read the value stored in the top node without changing any link. Time Complexity is O(1).

• isEmpty: Check whether the top reference is empty. Time Complexity is O(1).

• Size: Return a count updated during every push and pop. Time Complexity is O(1) when a count is maintained.

• isFull: A linked-list Stack normally has no fixed capacity, so isFull is usually not provided. No standard Time Complexity applies to an operation that the implementation does not offer. A push can fail only when new memory cannot be allocated.

• Search: Follow node links until the required value is found or the list ends. Time Complexity is O(N) in the worst case.

• Traversal: Follow every node link from the top to the bottom. Time Complexity is O(N).

• Space: Storing N elements requires O(N) space. Every node also stores an extra link.

Array Stack vs Linked-List Stack

Why is a Stack an Abstract Data Type?

An Abstract Data Type (ADT) describes what a structure must do without deciding how the data must be stored. For a Stack, the required behavior includes LIFO order and top-based operations such as push, pop, and peek.

An array-based Stack and a linked-list Stack store elements differently. Both are still Stacks because both follow the same rules. The Stack is the ADT while the array and linked list are implementation choices.

Advantages and Disadvantages

Advantages

• Push, pop, and peek work directly at the top.

• The small set of rules is easy to understand.

• LIFO order naturally fits recent-first tasks.

• Arrays and linked lists can support the same Stack behavior.

• Stack operations help organize nested work such as function calls.

Disadvantages

• Only the top element is directly available.

• Searching for a deeper element can take O(N) time.

• A fixed-size Stack can become full.

• Pop or peek on an empty Stack can cause underflow.

• A linked-list Stack stores an extra link in every node.

• A Stack is unsuitable for frequent middle access.

Applications of Stack

• Function calls and recursion: The newest active function finishes before the older function calls below it.

• Undo and redo: The most recent action is reversed first. Redo is often managed with a second Stack.

• Browser history: The Back action returns to the most recently visited earlier page.

• Balanced brackets: The latest unmatched opening bracket must be matched first.

• Expression evaluation: Operators and values are held until the correct processing order becomes clear.

• Backtracking: The latest saved choice is restored first when a path fails.

• Depth-first search: The newest discovered path is explored before an older path.

• Reversing data: Values pushed in one order come out in the reverse order.

Common Beginner Mistakes

• Confusing pop with peek. Pop removes the top value while peek leaves the Stack unchanged.

• Forgetting to check for an empty Stack before pop or peek.

• Adding and removing elements from different ends and accidentally creating Queue-like behavior.

• Treating direct middle access as a normal Stack operation.

• Calling every dynamic-array push worst-case O(1). A resize can take O(N) while the amortized cost remains O(1).

• Assuming a dynamic Stack can grow forever even though available memory creates a limit.

Summary

A Stack stores elements in Last-In-First-Out order. Push adds at the top, pop removes from the top, and peek reads the top without removing anything. Fixed-size and dynamic Stacks describe capacity behavior. Arrays and linked lists provide different implementations of the same Stack ADT.