Stacks
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. A
stack can hold many elements, and the last element added is the first one to be removed.
Example:
Think of it like a stack of pancakes - you can only add or remove pancakes from the top.
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.
Operations:
Basic operations we can do on a stack are:
Push: Adds a new element on the stack.
Pop: Removes and returns the top element from the stack.
Peek: Returns the top element on the stack.
isEmpty: Checks if the stack is empty.
Size: Finds the number of elements in the stack.
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.
Stack Implementation using Arrays
Reasons to implement stacks using arrays:
Memory Efficient: Array elements do not hold the next elements address like linked list
nodes do.
Easier to implement and understand: 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:
Fixed size: 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.
Stack Implementation using Linked Lists
A reason for using linked lists to implement stacks:
Dynamic size: The stack can grow and shrink dynamically, unlike with arrays.
Reasons for not using linked lists to implement stacks:
Extra memory: Each stack element must contain the address to the next element (the
next linked list node).
Readability: The code might be harder to read and write for some because it is longer
and more complex.
Code implementation:
This is how a stack can be implemented using a linked list.
class Node:
def __init__(self, value):
[Link] = value
[Link] = None
class Stack:
def __init__(self):
[Link] = None
[Link] = 0
def push(self, value):
new_node = Node(value)
if [Link]:
new_node.next = [Link]
[Link] = new_node
[Link] += 1
def pop(self):
if [Link]():
return "Stack is empty"
popped_node = [Link]
[Link] = [Link]
[Link] -= 1
return popped_node.value
def peek(self):
if [Link]():
return "Stack is empty"
return [Link]
def isEmpty(self):
return [Link] == 0
def stackSize(self):
return [Link]
def traverseAndPrint(self):
currentNode = [Link]
while currentNode:
print([Link], end=" -> ")
currentNode = [Link]
print()
myStack = Stack()
[Link]('A')
[Link]('B')
[Link]('C')
print("LinkedList: ", end="")
[Link]()
print("Peek: ", [Link]())
print("Pop: ", [Link]())
print("LinkedList after Pop: ", end="")
[Link]()
print("isEmpty: ", [Link]())
print("Size: ", [Link]())
Output: