iOS Interview - Using Stack to Solve Data Structure and Algorithm Problems in Swift

April 17, 2024 • 3 min read • #swift, #interview, #leetcode

Stacks are a fundamental data structure used in computer science to store and retrieve elements in a Last-In-First-Out (LIFO) manner. They play a crucial role in solving various data structure and algorithm problems. In this blog post, we will explore the stack pattern in Swift and see how it can be used to solve problems efficiently.

Understanding the Stack Pattern

A stack is an abstract data type that follows the LIFO principle. It consists of a collection of elements and supports two main operations:

Push: Adds an element to the top of the stack.
Pop: Removes the top element from the stack.

In addition to these, there are a few other useful operations:

Peek: Return the top element without removing it.
isEmpty: Check if the stack is empty.

Implementing a Stack in Swift

Swift provides a built-in Array data structure that can be used to implement a simple stack. However, for more control and customizability, you can create a custom Stack class. Here’s a simple Swift implementation:

class Stack<T> {
    private var elements: [T] = []

    func push(_ item: T) {
        elements.append(item)
    }

    func pop() -> T? {
        guard !isEmpty() else { return nil }
        return elements.removeLast()
    }

    func peek() -> T? {
        return elements.last
    }

    func isEmpty() -> Bool {
        return elements.isEmpty
    }
}

Example

Reverse a String: Reverse the characters of a given string.

func reverseString(_ s: String) -> String {
    var stack = Stack<Character>()
    for char in s {
        stack.push(char)
    }

    var reversed = ""
    while !stack.isEmpty() {
        reversed.append(stack.pop()!)
    }

    return reversed
}

print(reverseString("abcd")) // dcba

Problems

20. Valid Parentheses

Leetcode: 20. Valid Parentheses

func isValid(_ s: String) -> Bool {
    var stack = Stack<Character>()

    for char in s {
        if char == "(" || char == "{" || char == "[" {
            stack.push(char)
        } else if let topChar = stack.peek(), isValidPair(topChar: topChar, currentChar: char) {
            stack.pop()
        } else {
            return false
        }
    }

    return stack.isEmpty()
}

func isValidPair(topChar: Character, currentChar: Character) -> Bool {
    switch (topChar, currentChar) {
    case ( "(", ")" ), ( "{", "}" ), ( "[", "]" ):
        return true
    default:
        return false
    }
}


print(isValid("()")) // true
print(isValid("()[]{}")) // true
print(isValid("(]")) // true