Stack data structure
Imagine you have to do the dishes and you put one plate on top of the other.
The stack data structure works in that way. In the beginning the stack is empty (no plates). The first plate is put onto the stack and now the stack has one plate. There comes another plate which is put on top of the first one. Now you have two plates but you need to put them in the kitchen cabinet. You remove the last plate (the second one) from the stack and put it in the cabinet. You do the same for the other plate (the first one). This is how things work when we talk about the stack data structure. This data structure permits only two operations:
- Push - pushes elements onto the stack
- Pop - removes elements from the stack
This is a “Last In First Out” memory, because the first stored elements are the last to be removed.
I’ll show you my implementation (Python) using linked lists.
class Stack: def __init__(self): self.top = None def push(self, obj): node = StackNode(obj) if self.top is not None: node.next = self.top self.top = node else: self.top = node def pop(self): if self.top is None: return None node = self.top self.top = self.top.next return node.item class StackNode: def __init__(self, item): self.item = item self.next = None
When the stack object is created, the top property is set to None because the stack is empty.
When one object is pushed onto the stack, we create a new node and check if the stack is empty. If it is, we initialize the stack with that node (self.top = node). If it’s not, we set the next property of the node to the top-most node already on the stack and update the top of the stack to the new node.
When we pop a node from the stack we have to check if the stack is empty. If it is, we return nothing. If it’s not, we put the self.top node into a variable node, update the top of the stack to the next node, and return the object that is contained in the node.
stack = Stack() # creates the stack object stack.push('Plate1') stack.push('Plate') #then we pop them print stack.pop() # Plate2 print stack.pop() # Plate1
I hope it’s clear.