4. Stack Data Structure

Written by Kelvin Lau

Stacks are everywhere. Here are some common examples of things you would stack:

• pancakes
• books
• paper
• cash

The stack data structure is identical, in concept, to a physical stack of objects. When you add an item to a stack, you place it on top of the stack. When you remove an item from a stack, you always remove the top-most item.

Stack operations

Stacks are useful, and also exceedingly simple. The main goal of building a stack is to enforce how you access your data. If you had a tough time with the linked list concepts, you’ll be glad to know that stacks are comparatively trivial.

There are only two essential operations for a stack:

• push: Adding an element to the top of the stack.
• pop: Removing the top element of the stack.

This means that you can only add or remove elements from one side of the data structure. In computer science, a stack is known as a LIFO (last-in first-out) data structure. Elements that are pushed in last are the first ones to be popped out.

Stacks are used prominently in all disciplines of programming. To list a few:

• iOS uses the navigation stack to push and pop view controllers into and out of view.
• Memory allocation uses stacks at the architectural level. Memory for local variables is also managed using a stack.
• Search and conquer algorithms, such as finding a path out of a maze, use stacks to facilitate backtracking.

Implementation

Open up the starter playground for this chapter. In the Sources folder of your playground, create a file named Stack.swift. Inside the file, write the following:

public struct Stack<Element> {

  private var storage: [Element] = []

  public init() { }
}

extension Stack: CustomStringConvertible {

  public var description: String {
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

Here, you’ve defined the backing storage of your Stack. Choosing the right storage type for your stack is important. The array is an obvious choice, since it offers constant time insertions and deletions at one end via append and popLast. Usage of these two operations will facilitate the LIFO nature of stacks.

For the fancy chain of function calls in CustomStringConvertible, you are doing three things:

1. Creating an array that maps the elements to String via storage.map { "\($0)" }.
2. Creating a new array that reverses the previous array using reversed().
3. Flattening out the array into a string by using joined(separator:). You separate the elements of the array using the newline character "\n".

This will allow you to customize a human-readable representation of the Stack that you’ll be using.

push and pop operations

Add the following two operations to your Stack:

public mutating func push(_ element: Element) {
  storage.append(element)
}

@discardableResult
public mutating func pop() -> Element? {
  storage.popLast()
}

Fairly straightforward! In the playground page, write the following:

example(of: "using a stack") {
  var stack = Stack<Int>()
  stack.push(1)
  stack.push(2)
  stack.push(3)
  stack.push(4)

  print(stack)
  
  if let poppedElement = stack.pop() {
    assert(4 == poppedElement)
    print("Popped: \(poppedElement)")
  }
}

You should see the following output:

---Example of using a stack---
----top----
4
3
2
1
-----------
Popped: 4

push and pop both have a O(1) time complexity.

Non-essential operations

There are a couple of nice-to-have operations that make a stack easier to use. In Stack.swift, add the following to Stack:

public func peek() -> Element? {
 storage.last
}

public var isEmpty: Bool {
  peek() == nil
}

peek is an operation that is often attributed to the stack interface. The idea of peek is to look at the top element of the stack without mutating its contents.

Less is more

You may have wondered if you could adopt the Swift collection protocols for the stack. A stack’s purpose is to limit the number of ways to access your data, and adopting protocols such as Collection would go against this goal by exposing all the elements via iterators and the subscript. In this case, less is more!

You might want to take an existing array and convert it to a stack so that the access order is guaranteed. Of course it would be possible to loop through the array elements and push each element.

However, since you can write an initializer that just sets the underlying private storage. Add the following to your stack implementation:

public init(_ elements: [Element]) {
  storage = elements
}

Now, add this example to the main playground:

example(of: "initializing a stack from an array") {
  let array = ["A", "B", "C", "D"]
  var stack = Stack(array)
  print(stack)
  stack.pop()
}

This code creates a stack of strings and pops the top element “D.” Notice that the Swift compiler can type infer the element type from the array so you can use Stack instead of the more verbose Stack<String>.

You can go a step further and make your stack initializable from an array literal. Add this to your stack implementation:

extension Stack: ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: Element...) {
    storage = elements
  }
}

Now go back to the main playground page and add:

example(of: "initializing a stack from an array literal") {
  var stack: Stack = [1.0, 2.0, 3.0, 4.0]
  print(stack)
  stack.pop()
}

This creates a stack of Doubles and pops the top value 4.0. Again, type inference saves you from having to type the more verbose Stack<Double>.

Stacks are crucial to problems that search trees and graphs. Imagine finding your way through a maze. Each time you come to a decision point of left, right or straight, you can push all possible decisions onto your stack. When you hit a dead end, simply backtrack by popping from the stack and continuing until you escape or hit another dead end.

Key points

• A stack is a LIFO, last-in first-out, data structure.
• Despite being so simple, the stack is a key data structure for many problems.
• The only two essential operations for the stack are the push method for adding elements and the pop method for removing elements.