The Self-Taught Computer Scientist

Data Structures
114
When to Use Stacks
Pushing and popping elements from a stack are all O(1). While stacks are efficient for adding and 
removing data, they are not as efficient for operations that require you to access the entire stack 
(Figure 11.2). For example, suppose you needed to print the contents of a stack. One solution is to 
print each object as you pop it off the stack. Printing each element as it comes off your stack is O(
n). 
However, it also produces a list of objects in reverse order. Your stack will also be empty because you’ve 
popped all the items off of it. Another solution is to pop each element off the original stack as you 
append them to a temporary stack. Then you can print each element as you pop it off the temporary 
stack and append it back to the original stack. However, this solution requires more resources because 
you have to store all your data in a temporary stack. This solution is also O(2*
n): twice as long as it 
takes to print the items in an array.
Data 
Structure
Time Complexity
Average
Worst
Access
Search
Insertion Deletion
Access
Search
Insertion Deletion
Array
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Linked 
List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Hash 
Table
N/A
O(1)
O(1)
O(1)
N/A
O(n)
O(n)
O(n)
Binary 
Search 
Tree
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
O(n)
O(n)
O(n)
Figure 11.2: Stack operation run times