# Building a Linked Stack: Part 3

*This is the third article in a multi-part series on the
stack data structure.
This series defines what a stack is and what it does, then implements a
link-based stack*

Earlier, we learned
about nodes and the top node and we also implemented the `is_empty`

and `push`

methods. In the next article we'll finish implementing our `LinkedStack`

class
by implementing the pop and peek methods.

## What We Have So Far

So far, we've implemented the `is_empty`

and `push`

methods. Before we get
going it's a good idea to take a step back and see the big picture. Let's take
a look at what we have at the moment

```
class LinkedStack(StackInterface):
"""Defines a link-based stack"""
def __init__(self):
self.top = None
def is_empty(self):
"""Determines if the stack is empty"""
return self.top is None
def push(self, entry):
"""Adds a new entry to the top of the stack"""
node = Node(data=entry)
if self.is_empty():
self.top = node
else:
node.next = self.top
self.top = node
return True
```

### The Pop Method

Now, we're going to implement the `pop`

method. The specifications from
the first article
show that we need to obey the following behavior

`(new Stack()).pop() = False`

`(a_stack.push(item)).pop() = True`

This means that if we try to pop an item off of a stack, then `pop`

should
return `False`

if the stack is empty and `True`

otherwise. Pretty
straightforward.

To get this behavior, we should first check if the stack is empty and
immediately return `False`

if it is.

```
def pop(self):
"""Removes the top of the stack"""
if self.is_empty():
return False
```

If the stack *isn't* empty, then we need to remove the first item. A way that
we can do that is to advance the reference to the top node and then return
`True`

.

```
self.top = self.top.next
return True
```

Putting this together results in

```
def pop(self):
"""Removes the top of the stack"""
if self.is_empty():
return False
self.top = self.top.next
return True
```

Personally, I'm ok with having more than one `return`

in a function. However,
I'm a firm believer in making sure that one's code tells an easy-to-follow
story (just think of the person that has to read your code next is a homicidal
maniac who is triggered by unclear code) and I think that we can tell the `pop`

story a little better.

```
def pop(self):
"""Removes the top of the stack"""
can_pop = not self.is_empty()
if can_pop:
# Advance the top of the stack to the next node
self.top = self.top.next
return can_pop
```

I believe that the above will give me a slightly longer life.

### The Peek Method

Now, we're going to implement the `peek`

method. The specifications from
the first article
show that we need to obey the following behavior

`(new Stack()).peek() = error`

`(a_stack.push(item)).peek() = item`

This means that if we try to peek at an item of a stack, then `peek`

should
raise an error if the stack is empty and return the item (without modifying the
stack!) otherwise. Pretty straightforward, but it will require us to create our
own exception.

The documentation
states that when creating user-defined exceptions we should derive from the
`Exception`

class, so that's what we're going to do. We're going to go with a
meaningful name, otherwise we may not live very long.

```
# exception.py
class EmptyException(Exception):
"""Exception that's raised when a data structure is empty"""
```

That's it! Notice how we didn't have to import any modules. Now, let's start
working on `peek`

. Just like `pop`

, we need to see if the stack is empty, and
if it is, raise an `EmptyException`

.

```
def peek(self):
"""Returns the top of the stack"""
if self.top is None:
raise EmptyException("Stack is empty")
return self.top.data
```

Notice how we're returning the item with `self.top.data`

instead of using
`self.top`

. The first bit returns the item while the second returns the node,
which is *not* what we want to do.

### Some Python Bits

Since we're using Python, there's something that we can do to make *using* our
code a little easier. We can implement the
`__repr__`

dunder method.
which will

compute the “official” string representation of an object.

This is nice to have when using the REPL, which we'll be using later.

```
def __repr__(self):
nodes = []
curr = self.top
while curr:
nodes.append(repr(curr))
curr = curr.next
return '[' + ', '.join(nodes) + ']'
```

### Putting it All Together

Our complete implementation of the linked stack is as follows

```
# interface.py
import abc
class StackInterface(abc.ABC):
"""An abstract base class that defines a stack"""
@abc.abstractmethod
def is_empty(self):
"""Determines if the stack is empty"""
@abc.abstractmethod
def peek(self):
"""Returns the top of the stack"""
@abc.abstractmethod
def pop(self):
"""Removes the top of the stack"""
@abc.abstractmethod
def push(self, entry):
"""Adds data to the top of the stack"""
@abc.abstractmethod
def push(self, entry):
"""Adds a new entry to the top of the stack"""
# stack.py
from exception import EmptyException
from interface import StackInterface
from node import Node
class LinkedStack(StackInterface):
"""Defines a link-based stack"""
def __init__(self):
self.top = None
def is_empty(self):
"""Determines if the stack is empty"""
return self.top is None
def peek(self):
"""Returns the top of the stack"""
if self.is_empty():
raise EmptyException("Stack is empty")
return self.top.data
def pop(self):
"""Removes the top of the stack"""
can_pop = not self.is_empty()
if can_pop:
# Advance the top of the stack to the next node
self.top = self.top.next
return can_pop
def push(self, entry):
"""Adds a new entry to the top of the stack"""
node = Node(data=entry)
if not self.top:
self.top = node
else:
node.next = self.top
self.top = node
return True
def __repr__(self):
nodes = []
curr = self.top
while curr:
nodes.append(repr(curr))
curr = curr.next
return '[' + ', '.join(nodes) + ']'
# node.py
class Node:
"""A node in a chain"""
def __init__(self, next=None, data=None):
self.next = next
self.data = data
def __repr__(self):
return repr(self.data)
# exception.py
class EmptyException(Exception):
"""Exception that's raised when a data structure is empty"""
```

## Using the Stack

Let's play around with the stack a little using the REPL (I prefer IPython). We can make sure we've met our specifications. As a recap, here they are

`(new Stack()).isEmpty() = True`

`(new Stack()).pop() = False`

`(new Stack()).peek() = error`

`(a_stack.push(item)).isEmpty() = False`

`(a_stack.push(item)).peek() = item`

`(a_stack.push(item)).pop() = True`

So, now let's fire up that REPL and test out our shiny stack.

```
In [1]: stack = LinkedStack()
In [2]: stack.is_empty()
Out[2]: True
In [3]: stack.pop()
Out[3]: False
In [4]: stack.peek()
---------------------------------------------------------------------------
EmptyException Traceback (most recent call last)
<ipython-input-7-1e84c3c721a3> in <module>
----> 1 stack.peek()
<ipython-input-4-6a54ea098db0> in peek(self)
11 """Returns the top of the stack"""
12 if self.is_empt():
---> 13 raise EmptyException("Stack is empty")
14
15 return self.top.data
EmptyException: Stack is empty
In [5]: stack.pop()
Out[5]: False
In [6]: stack.push(1)
Out[6]: True
In [7]: stack.is_empty()
Out[7]: False
In [7]: stack.push(2)
Out[7]: True
In [8]: stack.peek()
Out[8]: 2
In [9]: stack.pop()
Out[9]: True
In [10]: stack.peek()
Out[1]: 1
```

We can see that our stack implements the specifications and works quite nicely. Although this may not be the best (e.g., most efficient) implementation, it does implement the specifications and in a manner that is clear and tells a nice story (i.e., we won't get killed with this code, hopefully).

## Conclusion

In this article, we learned about nodes and the top node and we also
implemented the `is_empty`

and `push`

methods. In the next article we'll finish
implementing our `LinkedStack`

class by implementing the pop and peek methods.