The stack is a wonderfully simple data structure which despite its simplicity makes many powerful algorithms possible.
Some of the uses for a stack data structure in software development are:
- The Depth-First Search Algorithm
- Reverse Polish Notation for evaluating arithmetic expressions
- Syntax parsing for compilers and interpreters
- Storing function call frames inside the CPU
- Matching parentheses/braces in IDEs
- Reversing the order of data
- Recursion
- Undo/redo operation in word processors and browsers
- Low-level/assembly programming
Stacks are a very important data structure in programming and Computer Science. Think of a stack of plates. The top plate is the only easy access point, whether you want to add a new plate or remove an existing one… This leads to to the idea of a Last In First Out data structure.
A stack is a LIFO data structure – last in, first out.
You will see in this article how this essential property is useful.
The fundamental operations associated with the stack data structure are:
push(item)– push item to the top of the stackpop()– Remove & return the top item
There are other methods too, which we will look at later, but push and pop are the essential, signature methods of a stack.
We use the term top to refer to the “access point” of the stack – i.e. the place where we either add or remove items. This is purely a conceptual tool though. In practice a stack is likely to be implemented using an array or list, both of which tend to be thought of a horizontal. It is an implementation detail as to whether the left- or right-hand end of a list/array is used as the top.
A Simple, Practical Implementation of a Stack in Python.
If you are more concerned about using a stack than in the details of its implementation, you can just go ahead and use a Python list, just being careful to only add or remove items from one end. An example is give below.
my_stack = []
my_stack.append("A")
my_stack.append("B")
my_stack.append("C")
print("stack contents:", my_stack)
while len(my_stack) > 0:
print(my_stack.pop())
What do you expect the output to be?
A couple of points about the above code:
- We use a Python list as the basis for our stack
- The top of the stack is the right-hand end of the list
- The
pop()list operation does two things: it removes the item at the top of the stack, AND returns it.
As a side note, do you think this version using for instead of while would work in the same way?
my_stack = []
my_stack.append("A")
my_stack.append("B")
my_stack.append("C")
print("stack contents:", my_stack)
for item in my_stack:
print(my_stack.pop())
A Python Class to Represent the Stack Data Structure
We are now going to write Python class to represent a stack for learning purposes, because the abstraction is helpful for gaining a deep understanding of how the data structure works, including using the appropriate terminology, such as push and pop. In practical situations, you might just use a list as described above. However, there is another reason to us a more detailed implementation such as a Python class. If your code needs a stack and you provide a list, there’s nothing stopping another programmer from calling insert, remove or other list functions that will affect the order of your stack! This fundamentally ruins the point of defining a stack, as it no longer functions the way it should.
Here is a Python class you can use for a stack, which abstracts the implementation details behind semantically named methods.
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
# return len(self.items) == 0
return not self.items
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
def __str__(self):
return str(self.items)
if __name__ == "__main__":
s = Stack()
print(s)
print(s.is_empty())
s.push(3)
print(s)
s.push(7)
s.push(5)
print(s)
print(s.pop())
print(s)
print(s.peek())
print(s.size())
Reversing a String Using a Stack in Python
One of the natural uses of a stack is to reverse data. You can see why if you get a bunch of plates, stack them on top of each other and then remove them one-by-one from the top. We are going to write a Python program to use this property of stacks to reverse the characters in a string.
Here’s a template for you to try to write this algorithm for yourself. You will only need the push and pop operations, but of course in the right place and with the right values. The goal is to reverse string and print the result. If you run this code in the same file as the Stack class from above, you will have access to that class. Otherwise you will need it import it using from stack import Stack.
string = "ymedacupmoC htiw nohtyP nraeL"
reversed_string = ""
s = Stack()
# Your solution here.
for char in string:
pass
while not s.is_empty():
pass
print(reversed_string)
Array Based Implementation of the Stack Data Structure
Depending on why you are learning about stacks (for example it may be as part of a course such as A Level Computer Science in the UK), you may need to know how to implement a stack inside of an array, as opposed to using a dynamic data structure such as a Python list which resizes to fit your requirements. This can be done in different ways which entail varying levels of complexity and provide varying levels of pedagogical value depending on the context.
A common approach used by A Level exam boards is demonstrated by the code below. This approach involves keeping track of the position of the top and bottom of the stack using external “pointers” (not actual pointers as in C for example, but variables containing the index positions.
# Simple array-based implementation of a stack in Python
import random
NULL = -1
# create space for indices 0-5 (6 slots)
stack = [None] * 6
TOSP = NULL # Top of stack pointer
BOSP = 0 # Bottom of stack pointer
def print_stack(stack):
"""
Outputs the contents of the stack with bigger indices at top.
"""
for i in range(len(stack) - 1, -1, -1): # careful with second argument
if i == TOSP:
print(stack[i], "<---", "TOSP:", TOSP)
else:
print(stack[i])
print()
def push(item):
"""
Pushes an item onto the stack.
"""
global TOSP # Chill it's OK here
if TOSP < 5:
TOSP += 1
stack[TOSP] = item
else:
print("Stack is full")
print_stack(stack)
def pop2():
"""
Pops an item from the stack. Named to avoid conflict with built-in method.
"""
global TOSP, BOSP
if TOSP >= BOSP:
TOSP -= 1
print_stack(stack)
else:
print("The stack is empty.")
print("TOSP:", TOSP, "BOSP:", BOSP)
return stack[TOSP]
# Add some items to stack
print("Pushing to stack")
print("#################")
print()
for i in range(1, 9):
push(random.randint(1, 99))
# Separator
print("Popping from stack")
print("##################")
print()
# Remove items from stack
for i in range(1, 8):
pop2()
A Really Complex Implementation of a Stack in Python
If you are a fan of complexity for complexity’s sake and/or your exam board has decided that you should do it this way, there is another approach which involves storing the pointer to the next position inside the array as a data attribute, alongside the data “cargo”. I will post an example of this for reference, but with the caveat that I don’t believe it is a suitable approach for students at A Level and certainly doesn’t help them with understanding the abstract part of the topic called Abstract Data Types. There is some commentary on the pedagogical issues with this approach on the CS Educators Stack Exchange site.
# NullPointer should be set to -1 if using array element with index 0
NULLPOINTER = -1
#Declare record type to store data and pointer
class Node:
def __init__(self):
self.Data = ""
self.Pointer = NULLPOINTER
def InitialiseStack():
Stack = [Node() for i in range(8)]
TopOfStack = NULLPOINTER # set start pointer
FreeListPtr = 0 # set starting position of free ist
for Index in range(7):
Stack[Index].Pointer = Index + 1
Stack[7].Pointer = NULLPOINTER # last node of free list
return (Stack, TopOfStack, FreeListPtr)
def Push(Stack, TopOfStack, FreeListPtr, NewItem):
if FreeListPtr != NULLPOINTER:
# there is space in the array
# take node from free list and store data item
NewNodePtr = FreeListPtr
Stack[NewNodePtr].Data = NewItem
FreeListPtr = Stack[FreeListPtr].Pointer
# insert new node at top of stack
Stack[NewNodePtr].Pointer = TopOfStack
TopOfStack = NewNodePtr
else:
print("no space for more data")
return (Stack, TopOfStack, FreeListPtr)
def Pop(Stack, TopOfStack, FreeListPtr):
if TopOfStack == NULLPOINTER:
print("no data on stack")
Value = ""
else:
Value = Stack[TopOfStack].Data
ThisNodePtr = TopOfStack
TopOfStack = Stack[TopOfStack].Pointer
Stack[ThisNodePtr].Pointer = FreeListPtr
FreeListPtr = ThisNodePtr
return (Stack, TopOfStack, FreeListPtr, Value)
def OutputAllNodes(Stack, TopOfStack) :
CurrentNodePtr = TopOfStack # start at beginning of list
if TopOfStack == NULLPOINTER :
print("No data on stack")
while CurrentNodePtr != NULLPOINTER : # while not end of list
print(CurrentNodePtr, " ",Stack[CurrentNodePtr].Data)
# follow the pointer to the next node
CurrentNodePtr = Stack[CurrentNodePtr].Pointer
Stack, TopOfStack, FreeListPtr = InitialiseStack()
Stack, TopOfStack, FreeListPtr = Push(Stack, TopOfStack,
FreeListPtr, "first item")
Stack, TopOfStack, FreeListPtr = Push(Stack, TopOfStack,
FreeListPtr, "second item")
Stack, TopOfStack, FreeListPtr = Push(Stack, TopOfStack,
FreeListPtr, "third item")
Stack, TopOfStack, FreeListPtr, value = Pop(Stack, TopOfStack, FreeListPtr)
print(value)
OutputAllNodes(Stack, TopOfStack)
This has been an introduction to the stack data structure in Python. I hope you found it helpful. Any questions or comments, please put them in the comments section below and I will try to address them.
Happy computing!