The Self-Taught Computer Scientist

Push
Pop
Figure 11.1: Data can be pushed on a stack or popped from it.

---

Chapter 11 Stacks
115
Stacks are one of the most frequently used data structures in computing. Computer scientists use 
stacks to implement breadth- first search algorithms to search for data in trees and graphs (which you 
will learn about in later chapters). The run- time systems for languages like Python and Java use a 
stack internally to handle function calls. Compilers use stacks to parse expressions, especially when 
you have expressions that use nested pairs of parentheses, like in standard arithmetic expressions, or 
nested pairs of brackets or braces. Computer scientists also use stacks in the backtracking algorithms 
you find in machine learning and other artificial intelligence areas. Because adding and removing 
elements from a stack are both O(1), they are an excellent choice whenever you are adding and 
removing data elements often. For example, programs that need an “undo” mechanism often use a 
stack or two to handle both “undo” and “redo.” Web browsers, for instance, often use two stacks to 
move backward and forward through your browsing history. Because accessing every element in a 
stack is O(
n), they are not the best choice for algorithms that need to access every piece of data in a 
data collection continually.
Creating a Stack
As you have learned, there are a few ways to use a stack in Python. One way is to create a 
Stack
class 
and manage its data internally using an array:
class Stack:
def __init__(self):
self.items = []
def push(self, data):
self.items.append(data)
def pop(self):
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return len(self.items) == 0
def peek(self):
return self.items[− 1]
Inside your 
Stack
class’s 
__init__
method, you define an instance variable called 
items
and set it 
to an empty list. This list is where you will keep track of the items in your stack.
class Stack:
def __init__(self):
self.items = []

---