How to Implement a Stack in Python

June 23, 2017

Stack of rocks

There's no other data structure like the Stack. In only a few minutes, you can have a fully working implementation that can be used to solve a wide variety of problems. Stacks are useful for anything from reversing a string to language processing applications - not to mention the fact that many programming languages (and probably your operating system) rely on a Stack to function.

Click here for the full Stack source code. Also, here is the test code.

An Analogy

The Stack data structure is well-named - it very much resembles a stack of papers, or a tower of blocks, or any pile of objects where all adding and removing occurs at the top of the pile. Just think - you can't remove a quarter in the middle of a stack of coins without knocking the whole thing over!

For our purposes, imagine you have a long, thin cardboard box. Your box can hold many different objects, but you can only interact with the contents of your box through the top. This box is your Stack. If you (gently!) slide a green plate into the box, it will rest at the bottom, still visible and accessible from someone looking in. After this, if you add an orange plate to your box, you will only have access to the orange plate. To get to the green plate, you need to first reach in and remove the orange plate. Keep this analogy in your mind as we move forward.

Setup

Our Stack will have three operations -

push
,
pop
, and
peek
. Before we get to the nitty gritty of their implementation, though, we need to setup the class for the
Stack
, as well as a
Node
class to hold whatever we put in our Stack. The Node that we create for our Stack will be identical to the Node we made for our LinkedList in the last post.

Our Stack will have two fields -

self.top
, which is the item on the top of the Stack, and
self.size
. The field
self.top
is similar to
self.head
or
self.tail
in a LinkedList. What makes it special is that it is the only Node accessible to the user of the
Stack
. All other nodes are hidden until that
self.top
Node is removed.

class Node(object):
def __init__(self, d):
self.data = d
self.next_node = None
class Stack(object):
def __init__(self):
self.top = None
self.size = 0

Push it

When you

push
something onto your Stack, you place it on top. This is akin to sliding a plate into your long box. The plate you add becomes the new top plate, and all the ones underneath become inaccessible.

The first step to making this work is creating a Node object to hold the data you're holding. Then, tie this

new_node
to the Node referenced by the Stack's
self.top
variable:
new_node.next_node = self.top
. Now, set your
new_node
as the new top of the Stack.

def push(self, d):
new_node = Node(d)
if self.top:
new_node.next_node = self.top
self.top = new_node
self.size += 1

The nodes are linked together exactly like a Singly Linked List. The only differences are the operations used to manipulate the data.

Take a peek

What happens when you need to look at what's in your Stack? You just peek down inside, that's all! The method

peek
is used to access the top data entry in a Stack without changing the Stack itself. It's not destructive - after all, it's just a harmless peek!

def peek(self):
return self.top.data

Pop it

Now, let's get serious. We need to completely remove something from our stack and look at it. We want to do something with it, and more importantly, we want whatever is below it to become the new

self.top
so that we can access it, too. When we
pop
something from the stack, we pull an object out, removing it from the stack. More specifically, the
pop
method returns
self.top
just like
peek
, but it also removes whatever Node is located at
self.top
, changing it to reference the next Node down.

def pop(self):
result = self.top.data
self.top = self.top.next_node
self.size -= 1
return result

Challenges

Let's put this knowledge to use! I have two programming challenges to try. If you get stuck, I'll give you a link to my solutions.

Each challenge should use the stack we just built, so either put your functions in the same source file as your stack, or create a challenges source file in the same directory and write

from stack import Stack
at the top.

First Challenge: Reverse a string

Implement a method,

reverse(s)
, which uses our Stack to reverse the input string
s
. For hints about completing this challenge, check out the video at the top of the article.

Second Challenge: Evaluate a postfix string

Implement a method,

eval_postfix(postfix_string)
, which returns a number representing the value of the input
postfix_string
. A Stack makes this much easier. Assume that the input has no spaces - each character in the string is a number or one of the following operator characters:
'+', '-', '*', '/'

Hint: Push all operands. When you find an operator, pop twice, calculate based on the operator, and push the result.

Another hint: When you're finished, the only thing in the stack will be the answer. Pop and return this.

Solutions

Don't peek! I hope you tried your best! Anyway, here are my solutions to the challenges.

Full Code and Testing

That's all there is to it! Part of the beauty of a Stack is its simplicity.

If you want to see all of the code for our finished Stack, check out the source on Github. I also wrote a few tests, which cover some of the important functionality of our Stack (though I can't guarantee 100% coverage!). Thanks for reading!