5. Stack Challenges

Written by Kelvin Lau

A stack is a simple data structure with a surprisingly large amount of applications. Open the starter project to begin. In it, you’ll find the following challenges.

Challenge 1: Reverse an Array

Create a function that uses a stack to print the contents of an array in reversed order.

Challenge 2: Balance the parentheses

Check for balanced parentheses. Given a string, check if there are ( and ) characters, and return true if the parentheses in the string are balanced. For example:

// 1
h((e))llo(world)() // balanced parentheses

// 2
(hello world // unbalanced parentheses

Solutions

Solution to Challenge 1

One of the prime use cases for stacks is to facilitate backtracking. If you push a sequence of values into the stack, sequentially popping the stack will give you the values in reverse order.

func printInReverse<T>(_ array: [T]) {
  var stack = Stack<T>()

  for value in array {
    stack.push(value)
  }

  while let value = stack.pop() {
    print(value)
  }
}

The time complexity of pushing the nodes into the stack is O(n). The time complexity of popping the stack to print the values is also O(n). Overall, the time complexity of this algorithm is O(n).

Since you’re allocating a container (the stack) inside the function, you also incur a O(n) space complexity cost.

Note: The way you should reverse an array in production code is to call the reversed() method that the standard library provides. For Array, this method is O(1) in time and space. This is because it is lazy and only creates a reversed view into the original collection. If you traverse the items and print out all of the elements, it predictably makes it O(n) in time while remaining O(1) in space.

Solution to Challenge 2

To check if there are balanced parentheses in the string, you need to go through each character of the string. When you encounter an opening parentheses, you will push that into a stack. Vice-versa, if you encounter a closing parentheses, you should pop the stack.

Here’s what the code looks like:

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

  for character in string {
    if character == "(" {
      stack.push(character)
    } else if character == ")" {
      if stack.isEmpty {
        return false
      } else {
        stack.pop()
      }
    }
  }
  return stack.isEmpty
}

The time complexity of this algorithm is O(n), where n is the number of characters in the string. This algorithm also incurs an O(n) space complexity cost due to the usage of the Stack data structure.