DSA Stacks

What is a Stack?

A stack is a data collection where the most recently added element is the first to be removed. Imagine a stack of books; you place a new book on top, and when you take one off, you remove the topmost book first.

The two primary actions performed on a stack are:

• Push: Place a new element on the uppermost layer of the stack.
• Pop: Take out the element currently sitting at the top.

Additionally, you often need to:

• Peek: View the topmost item without altering the stack.
• IsEmpty: Determine whether the stack contains any entries.

How a stack operates:

When you push a value, it goes directly on top of everything already there. When you pop, you take off the element that is currently on the top, leaving the rest untouched underneath. The stack grows and shrinks only from one end.

Example

class Stack:     
       def __init__(self):         
              self.items = []          

       def push(self, item):         
              self.items.append(item)          

       def pop(self):         
              if not self.is_empty():             
                    return self.items.pop()         
              else:             
                    return None          

       def peek(self):         
             if not self.is_empty():             
                   return self.items[-1]         
             return None          

       def is_empty(self):         
              return len(self.items) == 0  

# Usage 
stack = Stack() 
stack.push(5) 
stack.push(10) 
stack.push(15)  

print(stack.peek())  # Output: 15  

print(stack.pop())   # Output: 15 
print(stack.pop())   # Output: 10 
print(stack.peek())  # Output: 5 

Advantages of stacks

• Simplifies handling tasks that must be reversed or undone.
• Stacks can be built effortlessly using either arrays or pointer-based node structures.
• Controls access to the most recent item effectively.

Limitations to consider

• Stacks give access solely to the top element, with no way to reach items beneath it directly.
• If implemented using arrays, stacks can exceed their capacity and trigger an overflow.
• Not suited when you need to access elements in the middle.

Common uses for stacks

• Managing function calls and recursion in programming.
• Evaluating expressions, especially with operators and parentheses.
• Supporting undo/redo functionality in applications.
• Traversing trees or graphs using depth-first search.