Stack Data Structure

A stack is a data structure that stores items in a last in first out (LIFO) order.

A stack has 2 main functions:

Push - Add data to the stack
Pop - Access and remove (or pop) the last inserted item in the stack, also referred to as the top of the stack.

The operation known as peek returns the item at the top of the stack without removing it from the stack.

Stack Big O Overview

Operation	Time
Push	O(1)
Pop	O(1)
Peek	O(1)

Stack Implementation in Python

Under the hood, a stack is represented by a linked list.

The stack's push operation simply adds a node to the end of the linked list.

The stack's pop operation retrieves and removes the tail of the linked list.

Since items can be added and popped from the stack in constant time, Python's dynamic array can be used to represent a stack.

stack = []

stack.append('yellow')
stack.append('red')
stack.append('rose')
stack.append('green')

print('top of the stack: ', stack.pop())
print('peek the new top of the stack: ', stack[-1])

print('stack in its last in first out order: ')

while stack:
    print('item: ', stack.pop())

1stack = []
2
3stack.append('yellow')
4stack.append('red')
5stack.append('rose')
6stack.append('green')
7
8print('top of the stack: ', stack.pop())
9print('peek the new top of the stack: ', stack[-1])
10
11print('stack in its last in first out order: ')
12
13while stack:
14    print('item: ', stack.pop())
15

Stack Pros

Push on to the stack takes constant time.
Similarly, pop from the stack takes constant time.
Good for use cases such as tracking history, such as browser history or the function call stack itself.

Stack Cons

The main con with stack is that it's not useful for iterating through items in the stack. It's better to just use a regular array, or dynamic array.

5 Essential Stacks & Queues Coding Interview Problems

Master Stacks & Queues by trying the coding challenges below.

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.