Lesson 1

Exploring Stacks with Python Lists

Introduction

Greetings! Today, we're drawing back the curtains on Stacks in Python, a crucial data structure. A stack is like a pile of dishes: you add a dish to the top (Last In) and take it from the top (First Out). This Last-In, First-Out (LIFO) principle exemplifies the stack. Python executes stacks effortlessly using Lists. This lesson will illuminate the stack data structure, operations, and their Python applications. Are you ready to start?

Understanding Stack: A Data Structure on the Rise

A stack is an elongated storehouse permitting Push (addition) and Pop (removal) operations. It's akin to a stack of plates in a cafeteria where plates are added (pushed) and removed (popped) from the top. No plate can be taken from the middle or the bottom, exemplifying a Last-In, First-Out (LIFO) operation.

Utilizing Lists as Stacks in Python

To create a stack, Python employs a built-in data structure known as a List. For the Push operation, we use append(), which adds an element at the list's end. For the Pop operation, there's the pop() function that removes the last element, simulating the removal of the 'top' element in a stack. Here's how it looks:

Python
1stack = [] # A new empty stack 2 3# Push operations 4stack.append('John') 5stack.append('Mary') 6stack.append('Steve') 7 8stack.pop() # Pop operation removes 'Steve' 9print(stack) # Outputs: ['John', 'Mary']

In the example provided, we push 'John', 'Mary', and 'Steve' into the stack and then pop 'Steve' from the stack.

Advanced Stack Operations

Stacks operations go beyond merely push and pop. For example, to verify if a stack is empty, we can use the len() function. If it returns 0, that means the stack is empty. Conversely, if it returns a nonzero value, we can infer the stack is not empty. To peek at the top element of the stack without popping it, merely indexing with -1 is handy.

Here's an example:

Python
1stack.append('Sam') 2print(stack[-1]) # Outputs: 'Sam'

In this example, 'Sam' is added (pushed), and then the topmost stack element, which is 'Sam', is peeked.

Practical Stack Applications: Reversing a String

Practical applications of stacks in Python are plentiful. Here is one of them - reversing a string.

We will push all characters into a stack and then pop them out to get a reversed string!

Python
1def reverse_string(input_string): 2 stack = list(input_string) 3 4 reversed_string = '' 5 while len(stack) > 0: 6 reversed_string += stack.pop() 7 return reversed_string 8 9print(reverse_string('HELLO')) # Outputs: OLLEH
Practical Stack Applications: Checking Balance of Parentheses

A stack can be utilized to verify if parentheses in an expression are well-matched, i.e. every bracket has a corresponding pair. For example, parentheses in string "()[{}]" are well-matched, while in strings "([]()", ")()[]{}", "([)]", and "[{})" they are not.

Let's break down the solution into simple steps:

We start by creating a dictionary that maps each closing bracket to its corresponding opening bracket and an empty stack. Then, we iterate over each character paren in the string paren_string:

  • If paren is an opening bracket, it gets appended to the stack.
  • If paren is a closing bracket and the top element in the stack is the corresponding opening bracket, we remove the top element from the stack.
  • If neither of the above conditions is met, we return False.

Finally, if the stack is empty (all opening brackets had matching closing brackets), we return True. If there are some unmatched opening brackets left, we return False.

Python
1def is_paren_balanced(paren_string): 2 stack = [] 3 is_balanced = True 4 index = 0 5 opening_paren = {')': '(', ']' : '[', '}': '{'} # a matching opening parenthesis for every closing one 6 # Traversing all string characters 7 while index < len(paren_string) and is_balanced: 8 paren = paren_string[index] 9 if paren in "([{": 10 # We met an opening parenthesis, just putting it on stack 11 stack.append(paren) 12 else: 13 # We met a closing parenthesis 14 if not stack: 15 # The parenthesis is closing, but there are no items in the stack 16 is_balanced = False 17 else: 18 if stack[-1] != opening_paren[paren]: 19 # The parenthesis on top of the stack doesn't match 20 is_balanced = False 21 else: 22 stack.pop() 23 index += 1 24 if stack: 25 # If after traversing all characters, there is something left, it's bad 26 is_balanced = False 27 return is_balanced 28 29print(is_paren_balanced("(())")) # Outputs: True 30print(is_paren_balanced("({[)}")) # Outputs: False
Lesson Summary and Steps Ahead

Kudos to you! Having covered the stack data structure, operations, and their Python applications is a commendable feat. Next up, you'll encounter practice exercises that will solidify your newly acquired knowledge. Dive into them and master Stacks in Python!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.