Python Stack

Hello there! Ever wondered how your browser’s back button works? Or how your text editor’s undo function operates? The secret lies in a data structure known as a “stack”. Today, we’re diving into the world of Python Stack. So, buckle up and let’s get started!

In the digital realm, a stack is like a stack of pancakes. You can only interact with the topmost pancake (or data element). This principle is known as Last-In-First-Out (LIFO). In Python, we can implement this concept in a straightforward and efficient manner. But how? Let’s find out!

Understanding the Concept of Stack in Python

In the world of data structures, a stack is like a stack of pancakes. You can only interact with the topmost pancake (or data element). This principle is known as Last-In-First-Out (LIFO). In Python, we can implement this concept in a straightforward and efficient manner. But how? Let’s find out!

A stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called the top of the stack. The bottom of the stack is significant as it represents the order in which elements were added, then the order in which elements will be removed is based on the reverse of that order.

Implementing a Stack in Python

Python, being the versatile language it is, provides several ways to implement a stack. You can use a list, collections.deque, or queue.LifoQueue. Each has its own advantages and use cases. But for simplicity, we’ll focus on the list implementation.

Basic Stack Implementation using Lists

In the list implementation, the append() method can be used to “push” an item onto the stack, and the pop() method can be used to “pop” an item off the stack. For instance, consider the following example:

# Using a list as a stack
stack = []

# Pushing items onto the stack
stack.append("A")
stack.append("B")
stack.append("C")

print(stack)  # Output: ['A', 'B', 'C']

# Popping items off the stack
top_item = stack.pop()
print(top_item)  # Output: 'C'
print(stack)     # Output: ['A', 'B']

In this example, the list stack starts empty. We then push three items onto it in the order A, B, C. When we pop an item off the stack, ‘C’ is the first to be removed, demonstrating the LIFO behavior of the stack.

Implementing a Stack using a Class

We can utilize class to implement stack. In this method,

• We define a class named Stack.
• The __init__ method initializes an empty list called items. This list will be used to store the elements of the stack.

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

With this, we’ve created a Stack class with an empty list. This list will hold our stack items. Now, let’s add some operations!

Python Stack Operations

A stack has four main principle operations: push and pop

1. Push: which adds an element to the collection.
2. Pop: which removes the most recently added element that was not yet removed.

A stack has two other main operations: peek, and size.

Push

Push adds an element to the top of the stack. In Python, we use the list’s append method for this.

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

The push method takes an item as an argument and appends it to the end of the items list. This simulates pushing an element onto the stack.

Pop

Pop removes the topmost element. Python’s list makes this easy with the pop method.

    def pop(self):
        return self.items.pop()

The pop method removes and returns the last item from the items list.

Peek

Peek returns the topmost element without removing it. Here’s how we do it:

def peek(self):
    return self.items[-1]

The peek method returns the top item of the stack without removing it.

size

Finally, size returns the number of items in the stack. Python’s len function comes in handy here.

def size(self):
  return len(self.items)

The size method returns the number of items in the stack by returning the length of the items list.

Complete implementation using a class

So now we utilize all methods to complete the stack class and use it.

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

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

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def size(self):
        return len(self.items)

# Using the Stack class
s = Stack()
s.push(10)
s.push(20)
print(s.peek())  # Output: 20
print(s.pop())   # Output: 20
print(s.size())  # Output: 1

And voila! We’ve implemented a stack in Python!

Brief explanations of the code:

• We create an instance of the Stack class named s.
• We push two integers, 10 and 20, onto the stack using the push method.
• We then use the peek method to view the top item of the stack, which is 20.
• Next, we use the pop method to remove and return the top item of the stack, which is again 20.
• Finally, we use the size method to get the number of items in the stack, which is now 1 since we’ve popped one item off.

Practical Examples of Using Stack in Python

Stacks are everywhere in programming. They’re used in function call operations, backtracking algorithms, and even in simple tasks like checking for balanced parentheses in an expression. The possibilities are endless!

Here are two practical examples for using a stack in Python:

1. Reversing a String

A stack can be used to reverse a string. You push each character of the string onto the stack and then pop them off, which effectively reverses the order.

Code:

def reverse_string(s):
    stack = []
    for char in s:
        stack.append(char)

    reversed_string = ''
    while stack:
        reversed_string += stack.pop()

    return reversed_string

input_string = "HELLO"
print(reverse_string(input_string))

Explanation:

• We initialize an empty list stack to represent our stack.
• For each character in the input string s, we “push” it onto the stack using the append method.
• We then initialize an empty string reversed_string to build our reversed string.
• While there are still characters in our stack, we “pop” the top character off the stack and add it to reversed_string.
• Finally, we return the reversed string.

2. Checking for Balanced Parentheses

A common use for a stack is to check if a given expression has balanced parentheses. For instance, the expression "(a + b)" has balanced parentheses, but the expression "(a + b" or "a + b))" does not.

Code:

def is_balanced(expression):
    stack = []
    for char in expression:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()

    return len(stack) == 0

expr1 = "(a + b)"
expr2 = "(a + b"
print(is_balanced(expr1))
print(is_balanced(expr2))

Explanation:

• We start with an empty stack.
• We iterate through each character in the expression.
• If the character is an opening parenthesis (, we “push” it onto the stack.
• If it’s a closing parenthesis ), we check if the stack is empty (meaning there’s no matching opening parenthesis). If it’s empty, we immediately return False. Otherwise, we “pop” the top element from the stack.
• At the end of the loop, if the stack is empty (i.e., length of stack is 0), it means all opening parentheses had a matching closing parenthesis, so we return True. Otherwise, we return False.

These examples demonstrate how stacks can be useful in various applications, especially where last-in-first-out (LIFO) behavior is desired.

Conclusion

And that’s a wrap on Python stacks! They’re a powerful tool in a programmer’s arsenal. So, next time you hit the back button on your browser, remember there’s a stack working behind the scenes! Keep exploring and keep coding!

Frequently Asked Questions (FAQ)

Related tutorials

• Python Data Structures Overview
• Python Lists
• Python Tuples
• Python Sets
• Python Dictionaries
• Python Strings
• Python Arrays
• Python Stack
• Python Queue
• Python Linked List
• Python Trees
• Python Heaps
• Python Hashing
• Python Graphs
• Python Matrix
• Python Algorithms
• Python Recursion
• Python Time Complexity