08_stacks_queues.md

STACKS & QUEUES

Stacks and queues are fundamental data structures that help organize data in a particular order. They are used in various scenarios, such as managing function calls, scheduling tasks, and implementing algorithms like depth-first search and breadth-first search.

How stacks work

A stack follows the Last-In-First-Out (LIFO) principle. The last item pushed onto the stack is the first one to be popped out. It's like a stack of plates - you can only add or remove plates from the top.

The main operations of a stack are:

• push: Add an item to the top of the stack
• pop: Remove the top item from the stack
• peek: Get the value of the top item without removing it

Implementing a stack

In Swift, we can implement a stack using a linked list or an array. Here's an example using a linked list:

class Node<T> {
    var value: T
    var next: Node<T>?
    
    init(value: T) {
        self.value = value
    }
}

class Stack<T> {
    private var top: Node<T>?
    
    func push(_ value: T) {
        let newNode = Node(value: value)
        newNode.next = top
        top = newNode
    }
    
    func pop() -> T? {
        guard let topNode = top else {
            return nil
        }
        top = topNode.next
        return topNode.value
    }
    
    func peek() -> T? {
        return top?.value
    }
    
    var isEmpty: Bool {
        return top == nil
    }
}

The time complexity of push, pop, and peek operations is O(1) as they only operate on the top element.

Alternatively, we can use Swift's built-in Array type as a stack:

var stack = [1, 2, 3, 4]
stack.append(5)           // push
let lastItem = stack.popLast()  // pop
let topItem = stack.last        // peek

How queues work

A queue follows the First-In-First-Out (FIFO) principle. The first item enqueued is the first one to be dequeued. It's like a line of people waiting for a service - the person who joins the line first gets served first.

The main operations of a queue are:

• enqueue: Add an item to the back of the queue
• dequeue: Remove the front item from the queue
• peek: Get the value of the front item without removing it

Implementing a queue

We can implement a queue using a linked list or an array. Here's an example using a linked list:

class Queue<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
    
    func enqueue(_ value: T) {
        let newNode = Node(value: value)
        guard let tailNode = tail else {
            head = newNode
            tail = newNode
            return
        }
        tailNode.next = newNode
        tail = newNode
    }
    
    func dequeue() -> T? {
        guard let headNode = head else {
            return nil
        }
        head = headNode.next
        if head == nil {
            tail = nil
        }
        return headNode.value
    }
    
    func peek() -> T? {
        return head?.value
    }
    
    var isEmpty: Bool {
        return head == nil
    }
}

The time complexity of enqueue, dequeue, and peek operations is O(1) as they only operate on the front or back of the queue.

Using Swift's Array as a queue:

var queue = [1, 2, 3, 4]
queue.append(5)           // enqueue
let firstItem = queue.removeFirst()  // dequeue
let frontItem = queue.first          // peek

Deque (double-ended queue)

A deque, short for double-ended queue, is a data structure that allows insertion and removal at both ends. It combines the features of a stack and a queue.

The main operations of a deque are:

• enqueueFront: Add an item to the front
• enqueueBack: Add an item to the back
• dequeueFront: Remove the front item
• dequeueBack: Remove the back item
• peekFront: Get the value of the front item
• peekBack: Get the value of the back item

Here's an implementation of a deque in Swift:

class Deque<T> {
    private var array = [T]()
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    var front: T? {
        return array.first
    }
    
    var back: T? {
        return array.last
    }
    
    func enqueueFront(_ element: T) {
        array.insert(element, at: 0)
    }
    
    func enqueueBack(_ element: T) {
        array.append(element)
    }
    
    func dequeueFront() -> T? {
        guard !isEmpty else {
            return nil
        }
        return array.removeFirst()
    }
    
    func dequeueBack() -> T? {
        guard !isEmpty else {
            return nil
        }
        return array.removeLast()
    }
}

Applications of stacks and queues

Stacks and queues are used in various algorithms and problems:

1. Task scheduling: Queues can be used to schedule tasks in a first-come, first-served order.

2. Undo/Redo functionality: Stacks can be used to implement undo and redo operations in text editors or graphic design software.

Practice problems

1. Implement a function to reverse a string using a stack.
2. Check if a given string has balanced parentheses using a stack.
3. Implement a queue using two stacks.
4. Given a binary tree, perform level-order traversal using a queue.