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 AnalogyThe 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.
SetupOur Stack will have three operations -
,
, and
. Before we get to the nitty gritty of their implementation, though, we need to setup the class for the
, as well as a
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 -
, which is the item on the top of the Stack, and
. The field
is similar to
or
in a LinkedList. What makes it special is that it is the only Node accessible to the user of the
. All other nodes are hidden until that
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 itWhen you
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
to the Node referenced by the Stack's
variable:
. Now, set your
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 peekWhat happens when you need to look at what's in your Stack? You just peek down inside, that's all! The method
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 itNow, 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
so that we can access it, too. When we
something from the stack, we pull an object out, removing it from the stack. More specifically, the
method returns
just like
, but it also removes whatever Node is located at
, 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
ChallengesLet'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
at the top.
First Challenge: Reverse a stringImplement a method,
, which uses our Stack to reverse the input string
. For hints about completing this challenge, check out the video at the top of the article.
Second Challenge: Evaluate a postfix stringImplement a method,
, which returns a number representing the value of the input
. 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.
SolutionsDon't peek! I hope you tried your best! Anyway, here are my solutions to the challenges.
Full Code and TestingThat'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!