The Self-Taught Computer Scientist

Data Structures
116
Next, you define your stack’s 
push
method. You use Python’s built- in 
append
method to add a new 
piece of data to the end of 
items
:
def push(self, data):
self.items.append(data)
Your stack’s next method is 
pop
. Inside 
pop
, you use Python’s built- in 
pop
method to return the 
most recently added item in your stack:
def pop(self):
return self.items.pop()
The next method in your 
Stack
class is called 
size
, and it uses the 
len
method to return the length 
of your stack:
def size(self):
return len(self.items)
Your method 
is_empty
checks whether your stack is empty:
def is_empty(self):
return len(self.items) == 0
Finally, your last method is called 
peek
and returns the last item in your stack.
def peek(self):
return self.items[− 1]
You can also implement a 
Stack
class by using a linked list internally. Here’s how to create a simple 
stack (with just push and pop) using a linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, data):
node = Node(data)
if self.head is None:
self.head = node
else:
node.next = self.head

---

Chapter 11 Stacks
117
self.head = node
def pop(self):
if self.head is None:
raise IndexError('pop from empty stack')
poppednode = self.head
self.head = self.head.next
return poppednode.data
First, you define a node class to represent the nodes in your stack’s internal linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
Inside your 
Stack
class, you define an instance variable for your linked list’s head:
class Stack:
def __init__(self):
self.head = None
Next, you define a method called 
push
. Inside 
push
, you create a new node. If your linked list 
doesn’t have a head, you assign it to the new node. Otherwise, you make this node the head of your 
linked list.
def push(self, data):
node = Node(data)
if self.head is None:
self.head = node
else:
node.next = self.head
self.head = node
Then, you define a method called 
pop
:
def pop(self):
if self.head is None:
raise IndexError('pop from empty stack')
poppednode = self.head
self.head = self.head.next
return poppednode.data
If someone tries to pop from your stack when it’s empty, you raise an exception:
if self.head is None:
raise IndexError('pop from empty stack')

---