Loading lesson path
Concept visual
Start from A
A stack is a data structure that can hold many elements.
push() pop() peek() isEmpty()
Think of a stack like a pile of pancakes. In a pile of pancakes, the pancakes are both added and removed from the top. So when removing a pancake, it will always be the last pancake you added. This way of organizing elements is called LIFO: Last In First Out. Basic operations we can do on a stack are:
Adds a new element on the stack.
Removes and returns the top element from the stack.
Returns the top element on the stack. isEmpty: Checks if the stack is empty.
Finds the number of elements in the stack. Experiment with these basic operations in the stack animation above. Stacks can be implemented by using arrays or linked lists. Stacks can be used to implement undo mechanisms, to revert to previous states, to create algorithms for depth-first search in graphs, or for backtracking. Stacks are often mentioned together with Queues, which is a similar data structure described on the next page.
To better understand the benefits with using arrays or linked lists to implement stacks, you should check out this page that explains how arrays and linked lists are stored in memory. This is how it looks like when we use an array as a stack: [
]
push() pop() peek() isEmpty()
Reasons to implement stacks using arrays:
Array elements do not hold the next elements address like linked list nodes do.
Using arrays to implement stacks require less code than using linked lists, and for this reason it is typically easier to understand as well. A reason for not using arrays to implement stacks:
An array occupies a fixed part of the memory. This means that it could take up more memory than needed, or if the array fills up, it cannot hold more elements.
When using arrays in Python for this tutorial, we are really using the Python 'list' data type, but for the scope of this tutorial the 'list' data type can be used in the same way as an array. Learn more about Python lists here. Since Python lists has good support for functionality needed to implement stacks, we start with creating a stack and do stack operations with just a few lines like this:
stack = []
# Push stack.append('A') stack.append('B') stack.append('C')
print("Stack: ", stack)Formula
# Pop element = stack.pop()print("Pop: ", element)Formula
# Peek topElement = stack[- 1]print("Peek: ", topElement)Formula
# isEmpty isEmpty = not bool(stack)print("isEmpty: ", isEmpty)# Size print("Size: ",len(stack))But to explicitly create a data structure for stacks, with basic operations, we should create a stack class instead. This way of creating stacks in Python is also more similar to how stacks can be created in other programming languages like C and Java.
class Stack:
def __init__(self):
self.stack = []def push(self, element):
self.stack.append(element)def pop(self):
if self.isEmpty():
return "Stack is empty"
return self.stack.pop()def peek(self):
if self.isEmpty():
return "Stack is empty"
return self.stack[-1]def isEmpty(self):
return len(self.stack) == 0def size(self):
return len(self.stack)Formula
# Create a stack myStack = Stack()myStack.push('A') myStack.push('B') myStack.push('C')
print("Stack: ", myStack.stack)print("Pop: ", myStack.pop())print("Peek: ", myStack.peek())print("isEmpty: ", myStack.isEmpty())print("Size: ", myStack.size())A reason for using linked lists to implement stacks:
The stack can grow and shrink dynamically, unlike with arrays. Reasons for not using linked lists to implement stacks:
Each stack element must contain the address to the next element (the next linked list node).
The code might be harder to read and write for some because it is longer and more complex. This is how a stack can be implemented using a linked list.
class Node:
def __init__(self, value):Formula
self.value = value self.next = Noneclass Stack:
def __init__(self):Formula
self.head = None self.size = 0def push(self, value):Formula
new_node = Node(value)
if self.head:
new_node.next = self.head self.head = new_node self.size += 1def pop(self):
if self.isEmpty():
return "Stack is empty"
popped_node = self.head self.head = self.head.next self.size -= 1 return popped_node.valuedef peek(self):
if self.isEmpty():
return "Stack is empty"
return self.head.valuedef isEmpty(self):
return self.size == 0def stackSize(self):
return self.sizeFormula
myStack = Stack()myStack.push('A') myStack.push('B') myStack.push('C')
print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize())The image below represents a "Stack" data structure.
method on the Stack above, what is returned? Submit Answer »