DSA Stacks
Stacks
A data structure with multiple elements that can be held is a stack.
=== EXAMPLE MUKAVU ====
Consider a stack as a pancake pile.
Pancakes are added to and taken off of the top of a pile of them. Thus, the final pancake you add will always be the one you remove. The term LIFO (Last In First Out) refers to this method of allocating items.
The fundamental tasks we can perform 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.
Try out these fundamental operations in the aforementioned stack animation.
Arrays and linked lists are two ways to implement stacks.
Stacks can be utilized to build depth-first search algorithms in graphs, implement undo mechanisms, and perform backtracking.
Stacks are frequently discussed in conjunction with Queues, another comparable data structure that is covered on the following page.
Stack Implementation using Arrays
Check out this page that describes how arrays and linked lists are maintained in memory to gain a better understanding of the advantages of using them to construct stacks.
When we utilize an array as a stack, it appears like this:
=== EXAMPLE MUKAVU ====
Reasons for employing arrays to implement stacks:
- Memory Efficient: Unlike linked list nodes, array elements do not store the address of the subsequent element.
- Simpler to implement and comprehend: Implementing stacks with arrays requires less code than with linked lists, and as a result, it’s usually simpler to comprehend as well.
One justification for not implementing stacks with arrays
- Fixed size: An array takes up a predetermined amount of memory. This implies that it might use more memory than is necessary or that it won’t be able to accommodate more elements if the array gets full.
Note: Although the Python ‘list’ data type is actually utilized for arrays in this tutorial, it can be used in the same manner as arrays for the purposes of this guide. Find out more about lists in Python here.
We begin by constructing a stack and perform stack operations with just a few lines, similar to this, because Python lists have decent support for the functionality required to develop stacks:
Example
Python:
stack = []
# Push
stack.append('A')
stack.append('B')
stack.append('C')
print("Stack: ", stack)
# Pop
element = stack.pop()
print("Pop: ", element)
# Peek
topElement = stack[-1]
print("Peek: ", topElement)
# isEmpty
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)
# Size
print("Size: ",len(stack))
However, we should establish a stack class in order to explicitly create a data structure for stacks that includes the fundamental operations. Python stack creation is also more akin to stack creation in other programming languages, such as C and Java.
Example
Python:
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) == 0
def size(self):
return len(self.stack)
# 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())
Stack Implementation using Linked Lists
One justification for implementing stacks using linked lists is:
- Dynamic size: Unlike arrays, the stack can expand and contract on a whim.
Reasons for not implementing stacks using linked lists:
- Additional memory: The address of the subsequent element (the subsequent linked list node) must be contained in every stack element.
- Readability: Because the code is longer and more complex, some people may find it more difficult to understand and write.
This is the linked list implementation of a stack.
Example
Python:
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.head = None
self.size = 0
def push(self, value):
new_node = Node(value)
if self.head:
new_node.next = self.head
self.head = new_node
self.size += 1
def pop(self):
if self.isEmpty():
return "Stack is empty"
popped_node = self.head
self.head = self.head.next
self.size -= 1
return popped_node.value
def peek(self):
if self.isEmpty():
return "Stack is empty"
return self.head.value
def isEmpty(self):
return self.size == 0
def stackSize(self):
return self.size
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())
