How to Implement a Stack in Python

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

peek

Stack

Node

Our Stack will have two fields -

self.top

self.size

self.top

self.head

self.tail

Stack

self.top

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

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

new_node

self.top

new_node.next_node = self.top

new_node

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

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

pop

pop

self.top

peek

self.top

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

First Challenge: Reverse a string​

Implement a method,

reverse(s)

s

Second Challenge: Evaluate a postfix string​

Implement a method,

eval_postfix(postfix_string)

postfix_string

'+', '-', '*', '/'

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!