The Stack Data Structure
Overview
- A stack is a collection data type that is best visualized as a “tower” of elements.
- It can be described as LIFO (Last in, First out).
- Differs from queues in how objects are removed (in stacks, the last entry is removed).
Stack Operations
There are four basic operations1 that can be done on a stack:
- push(): adds an element to the top of the stack. * Depending on your implementation of stack, you may need to check if the stack is not full first.
- pop(): removes an element from the top of the stack if the stack is not empty.
- peek(): Return the top element of the stack, but don’t remove it.
- isEmpty(): return TRUE if the stack is empty and FALSE otherwise.
When to Use Stacks
- When LIFO processing order matters.
- When data needs to be processed immediately after being added to the stack.
- Keeping track of changes in a file. For example, in Microsoft Word.
- Edits are stored as entries in a stack for easy retrieval (just pop the stack)
Time Complexity
| Operation | Time Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
Practice Problems
Check out HackerEarth’s Basics of Stacks page for more practice problems.
- Given a word (string), print the word backwards