In this lesson, you'll explore stacks, queues, and linked lists – fundamental data structures in computer science. You'll learn their concepts, operations, and real-world use cases, then implement them in Python using VS Code. By the end, you'll build a simple undo system project using a stack.

By the end of this lesson, you will be able to:

• Explain stacks, queues, and linked lists, including their operations.
• Implement these data structures in Python.
• Apply them to solve problems, like an undo feature.

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates: you add (push) to the top and remove (pop) from the top. This means the most recently added item is the first one to be removed, making it ideal for situations where you need to access the latest elements first.

Key operations:

• Push: Add an item to the top.
• Pop: Remove and return the top item.
• Peek: View the top item without removing it.
• Is Empty: Check if the stack is empty.

Use cases: Undo/redo in editors (last action undone first), function call stacks in programming, or browser history (back button pops the last page).

Stacks can be implemented using lists in Python, with O(1) time for push and pop, meaning these operations are very fast regardless of the stack's size.

Now that you understand the concept of a stack, let's implement one in Python. A Stack class is like a blueprint or template that defines how a stack should work. It encapsulates the data (like the list of items) and the methods (functions) that operate on that data, such as pushing and popping items. This allows you to create multiple stack objects, each managing its own set of items independently. We'll create a Stack class using a Python list as the underlying storage, which is efficient for this purpose because appending and popping from the end of a list are fast operations.

First, create a new folder called 'DataStructures' and inside it, create a file named 'my_stack.py'.

class Stack:
    def __init__(self):
        # Initializes the stack with an empty list to store items
        self.items = []

    def push(self, item):
        # Adds an item to the top of the stack
        self.items.append(item)

    def pop(self):
        # Removes and returns the top item if the stack is not empty
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        # Returns the top item without removing it, if the stack is not empty
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        # Checks if the stack is empty
        return len(self.items) == 0

    def size(self):
        # Returns the number of items in the stack
        return len(self.items)

To test your Stack class and ensure all methods work correctly, add the following code at the end of the file. This creates a stack, checks if it's empty and its size, pushes two numbers, checks size and peeks, pops one (which should be the last one added, following LIFO), peeks at the remaining top item, checks size again, and finally checks if it's empty.

if __name__ == "__main__":
    s = Stack()
    print(s.is_empty())  # Should print True
    print(s.size())      # Should print 0
    s.push(1)
    s.push(2)
    print(s.size())      # Should print 2
    print(s.peek())      # Should print 2
    print(s.pop())       # Should print 2
    print(s.peek())      # Should print 1
    print(s.size())      # Should print 1
    print(s.is_empty())  # Should print False

Stacks are perfect for undo systems because they follow the Last In, First Out (LIFO) principle. This means the most recent action or change is the first one you can undo, just like in a real text editor where pressing 'undo' reverses your last edit. In this step, we'll build a simple simulation of a text editor's undo feature. We'll create a class that tracks the history of text changes using a stack, allowing us to add new text (like typing) and then undo those changes step by step. This will help you see how stacks can be applied in real-world scenarios.

Create a new file named 'undo_system.py'. This file will contain the UndoSystem class, which uses the Stack class from 'structures.py'. Add the following complete code to 'undo_system.py' (make sure to comment out any previous if __name__ == "__main__" block in 'my_stack.py' if it's interfering):

from my_stack import Stack

class UndoSystem:
    def __init__(self):
        self.history = Stack()  # Creates a stack to store previous text states
        self.current_text = ""  # Starts with empty text

    def edit(self, new_text):
        self.history.push(self.current_text)  # Pushes the current text to the stack before changing it
        self.current_text += new_text  # Appends the new text to the current text
        print(f"Current text: {self.current_text}")  # Prints the updated text

    def undo(self):
        if not self.history.is_empty():  # Checks if there's something to undo
            self.current_text = self.history.pop()  # Pops the last saved text and sets it as current
            print(f"Undo: Current text: {self.current_text}")  # Prints the restored text
        else:
            print("Nothing to undo")  # Message if the stack is empty

if __name__ == "__main__":
    editor = UndoSystem()  # Creates an instance of UndoSystem
    editor.edit("Hello")  # Adds "Hello", prints: Current text: Hello
    editor.edit(", World")  # Adds ", World", prints: Current text: Hello, World
    editor.undo()  # Undoes the last edit, reverts to "Hello", prints: Undo: Current text: Hello
    editor.edit(" Everyone!")  # Adds " Everyone!", prints: Current text: Hello Everyone!
    editor.undo()  # Undoes again, reverts to "Hello", prints: Undo: Current text: Hello 
    editor.undo()  # Undoes again, reverts to "", prints: Undo: Current text:  

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Think of a queue at a shop: the first person in line is served first. In programming, this means the item that has been in the queue the longest is the one that gets processed first, ensuring fairness and order. This is different from a stack, where the newest item is processed first.

Key operations:

• Enqueue: Add an item to the back.
• Dequeue: Remove and return the front item.
• Peek: View the front item without removing it.
• Is Empty: Check if the queue is empty.

Use cases: Task scheduling (e.g., print jobs), breadth-first search in graphs, or handling requests in servers (first come, first served).

Queues can be implemented using lists or collections.deque for efficiency (O(1) for enqueue and dequeue).