A stack is like a stack of plates: you can only add or remove plates from the top. The last plate you put on is the first one you take off — Last In, First Out (LIFO).

Stack Operations

• push(item) — Add an item to the top
• pop() — Remove and return the top item
• peek()/top() — View the top item without removing it
• is_empty() — Check if the stack has no items

Practice 1

1. Draw the stack after: push(5), push(3), pop(), push(7), pop(), push(9)
2. What does peek() return after these operations?

Implementing a Stack in Python

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()
        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

Practice 2

1. Use a stack to reverse a string: push each character, then pop them all.
2. Implement a bracket-checker: use a stack to verify that brackets in a string like "({[]})" are balanced.

A queue is like a line at a supermarket: the first person in line is served first. First In, First Out (FIFO).

Queue Operations

• enqueue(item) — Add an item to the back of the queue
• dequeue() — Remove and return the front item
• front() — View the front item without removing it
• is_empty() — Check if the queue has no items

🔷 Linear Queue — Array Implementation

In a linear queue, we use a fixed-size array with two pointers: front (pointing to the first element) and rear (pointing to the next empty slot).

• Enqueue(x): items[rear] = x; rear++ — add at the rear
• Dequeue(): x = items[front]; items[front] = null; front++ — remove from the front

🔄 Circular Queue — Array Implementation

A circular queue solves the wasted-space problem by wrapping around: when rear reaches the end, it goes back to index 0 if there's space. We leave one slot empty to distinguish "full" from "empty".

• Enqueue(x): items[rear] = x; rear = (rear + 1) % size
• Dequeue(): x = items[front]; items[front] = null; front = (front + 1) % size
• is_empty(): front == rear
• is_full(): (rear + 1) % size == front

Practice 1

1. Show the queue after: enqueue(3), enqueue(7), dequeue(), enqueue(5), dequeue()
2. What's the difference between a stack and a queue?

Implementing a Queue in Python

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        return self._items.popleft()
    def front(self):
        return self._items[0]
    def is_empty(self):
        return len(self._items) == 0

Practice 2

1. Simulate a print queue: users submit print jobs, printer processes them in order.
2. Implement a circular queue using a fixed-size array (advanced challenge).