iOS, Stack and Queue

✍️ Note

Some codes and contents are sourced from Udemy. This post is for personal notes where I summarize the original contents to grasp the key concepts (🎨 some images I draw it)

Introduction

You may think Stack and Queue is very basic structure and It’s very easy. Yes that’s true but utilizing them together is bit tricky. That’s why I summarized these data structure. (As I mentioned earlier, all the contents are sourced from Udemy lecture, I rewrite sample code in Swift)

Stack

A stack is a data structure to hold elements such that the last element you add to the stack is the first one you access

LIFO: Last In First Out

Always focused on the end of the stack, called the POP

Push – Push an element to the top of a stack

Pop – Pop an element from the top of a stack

Peek – Peet at the top element of a stack (Don’t remove an element!) You access the top element in the stack without actually changing the data structure

Other operations which are useful

IsEmpty, IsFull, Size

Exception case

When you try to pop from an empty stack -> throw an exception

Push into a full stack -> throw an exception, Yes It is stack overflow!

Summary

The most common operations on a stack involve pushing and popping elements from the top.

The operations are confined to one end of the stack

A linked list lends itself perfectly to build a stack

Performance and Complexity

Push and Pop (Using Linked List or Array) is O(1)

isEmpty, isFull also O(1)

check size -> O(1)

Space Complexity

O(N)

Where can stacks be used?

Implementing undo in an application

Implementing the back button on the web browser

Holding the memory for recursive calls in a programming language

Translating infix notation (a+b) for expressions to postfix (ab+)

programming languages converts infix to postfix

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463684#overview

Example 1. Use a Single Linked List

//A Single Element in the linked list
class Element<T> {
    var data: T
    var next: Element?
    
    init(data: T, next: Element?) {
        self.data = data
        self.next = next
    }
}

enum StackError: Error {
    //Pushing into a full stack
    case stackOverflow
    //Popping from or peeking into an empty stack
    case stackUnderflow
}

class Stack<T> {
    private let maxSize: Int
    //Topmost element in the stack
    private var top: Element<T>?
    //Track the size of the stack at every push, pop
    //This means the stack size operation can be constant time
    private var size = 0
    
    init(maxSize: Int) {
        self.maxSize = maxSize
    }
    
    func push(data: T) throws {
        if size == maxSize {
            throw StackError.stackOverflow
        }
        //Create a new element to hold the data and point top to it. Make sure you increment the size of the stack
        var newElement = Element(data: data, next: top)
        top = newElement
        size += 1
    }
    
    func pop() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        guard let topElement = top else {
            throw StackError.stackUnderflow
        }
        let data = topElement.data
        //Remove the top element from the stack and return it's data
        top = topElement.next
        size -= 1
        return data
    }
    
    func peek() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        guard let topElement = top else {
            throw StackError.stackUnderflow
        }
        //Just return the data of the top element, do not remove it
        return topElement.data
    }
    
    var isEmpty: Bool {
        size == 0
    }
    
    var isFull: Bool {
        size == maxSize
    }
}

Example 2. Use an Array (It’s more simple, In swift array can increased the size at runtime)

Growing the Size of an Array

Every array reserves a specific amount of memory to hold its contents. When you add elements to an array and that array begins to exceed its reserved capacity, the array allocates a larger region of memory and copies its elements into the new storage. The new storage is a multiple of the old storage’s size. This exponential growth strategy means that appending an element happens in constant time, averaging the performance of many append operations. Append operations that trigger reallocation have a performance cost, but they occur less and less often as the array grows larger.

If you know approximately how many elements you will need to store, use the reserveCapacity(_:)method before appending to the array to avoid intermediate reallocations. Use the capacity and countproperties to determine how many more elements the array can store without allocating larger storage.

For arrays of most Element types, this storage is a contiguous block of memory. For arrays with an Element type that is a class or @objc protocol type, this storage can be a contiguous block of memory or an instance of NSArray. Because any arbitrary subclass of NSArray can become an Array, there are no guarantees about representation or efficiency in this case.
https://developer.apple.com/documentation/swift/array

enum StackError: Error {
    //Pushing into a full stack
    case stackOverflow
    //Popping from or peeking into an empty stack
    case stackUnderflow
}

class Stack<T> {
    private let maxSize: Int
    private(set) var array = Array<T>()
    //Topmost element in the stack
    private var top: T?
    //Track the size of the stack at every push, pop
    //This means the stack size operation can be constant time
    private var size = 0
    
    init(maxSize: Int) {
        self.maxSize = maxSize
    }
    
    func push(data: T) throws {
        if size == maxSize {
            throw StackError.stackOverflow
        }
        array.append(data)
        top = data
        size += 1
    }
    
    func pop() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        //Remove the top element from the stack and return it's data
        let topElement = array.removeLast()
        top = array.last
        size -= 1
        return topElement
    }
    
    func peek() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        guard let topElement = top else {
            throw StackError.stackUnderflow
        }
        //Just return the data of the top element, do not remove it
        return topElement
    }
    
    var isEmpty: Bool {
        size == 0
    }
    
    var isFull: Bool {
        size == maxSize
    }
}

let stack = Stack<Int>(maxSize: 10)

try? stack.push(data: 1)
try? stack.push(data: 2)
try? stack.push(data: 3)

try? stack.pop()
try? stack.pop()
try? stack.pop()

Exercise 1. Match parenthesis in an expression

Check whether an expression has well-formed parenthesis I.E The opening and the closing brackets match

Use a Stack to store the opening brackets each time you encounter one

For every closing bracket compare to the last element pushed onto the stack
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463688#overview

Example

(ABC){DEF}[XYZ(LMN)] -> Match
(ABC{DEF}[XYZ(LMN)] -> Mismatch
(ABC){DEF}[XYZ(LMN)]} -> Mismatch

//Key is closed brackets, value is open brackets
var brackets = [")": "(", "]": "[", "}": "{"]
var openBrackets = Set(brackets.values)

print(openBrackets)
func matchingParenthesis(input: String) -> Bool {
    let stack = Stack<String>(maxSize: input.count)
    var inputStringArray = input.compactMap { String($0)}
    for c in inputStringArray {
        if openBrackets.contains(c) {
            try? stack.push(data: c)
        }
        //Check close bracket
        if brackets.keys.contains(c) {
            //Pop open brackets
            let poppedValue = try? stack.pop()
            //Check Is poppedValue openBracket or not
            if poppedValue != brackets[c] {
                return false
            }
        }
    }
    return stack.isEmpty
}

matchingParenthesis(input: "(ABC){DEF}[XYZ(LMN)]")
matchingParenthesis(input: "(ABC{DEF}[XYZ(LMN)]")
matchingParenthesis(input: "(ABC){DEF}[XYZ(LMN)]}")

Exercise 2. Find the minimum element in a stack in constant time

Keep track of the minimum element for each element pushed on to the stack

Have 2 stacks, one to hold the actual elements, and another to hold the minimum element corresponding to every element added to the stack

When each element is pushed onto the stack compare it with the last minimum element and push both the main stack and the minimum element stack together

Do the same when popping an element from the stack
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463690#overview

func findMinValue(input: [Int]) -> Int? {
    let stack = Stack<Int>(maxSize: input.count)
    let minStack = Stack<Int>(maxSize: input.count)
    
    for n in input {
        try? stack.push(data: n)
        if minStack.isEmpty == true {
            try? minStack.push(data: n)
        }
        else {
            if let peekMinValue = try? minStack.peek() {
                //Compare peekValue from MinStack and current value in input
                let currentMinValue = n < peekMinValue ? n : peekMinValue
                try? minStack.push(data: currentMinValue)
            }
        }
    }
    return try? minStack.peek()
}

findMinValue(input: [4, 5, 3, 2, 9])

Or you can create a MinimumStack class like below

enum StackError: Error {
    //Pushing into a full stack
    case stackOverflow
    //Popping from or peeking into an empty stack
    case stackUnderflow
}

class Stack<T> {
    private let maxSize: Int
    private(set) var array = Array<T>()
    //Topmost element in the stack
    private var top: T?
    //Track the size of the stack at every push, pop
    //This means the stack size operation can be constant time
    private var size = 0
    
    init(maxSize: Int) {
        self.maxSize = maxSize
    }
    
    func push(data: T) throws {
        if size == maxSize {
            throw StackError.stackOverflow
        }
        array.append(data)
        top = data
        size += 1
    }
    
    func pop() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        //Remove the top element from the stack and return it's data
        let topElement = array.removeLast()
        top = array.last
        size -= 1
        return topElement
    }
    
    func peek() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        guard let topElement = top else {
            throw StackError.stackUnderflow
        }
        //Just return the data of the top element, do not remove it
        return topElement
    }
    
    var isEmpty: Bool {
        size == 0
    }
    
    var isFull: Bool {
        size == maxSize
    }
}


class MinimumStack<T: Comparable> {
    private let maxSize: Int
    private let stack: Stack<T>
    private let minimumStack: Stack<T>
    
    init(maxSize: Int) {
        self.maxSize = maxSize
        self.stack = Stack<T>(maxSize: maxSize)
        self.minimumStack = Stack<T>(maxSize: maxSize)
    }
    
    func push(data: T) throws {
        var min = data
        if !minimumStack.isEmpty {
            let peekMinValue = try minimumStack.peek()
            if min > peekMinValue {
                min = peekMinValue
            }
        }
        try stack.push(data: data)
        try minimumStack.push(data: min)
    }
    
    func pop() throws -> T {
        try minimumStack.pop()
        return try stack.pop()
    }
    
    func minimumValue() throws -> T {
        return try minimumStack.peek()
    }
}

let input = [4, 5, 3, 2, 9]
let minimumStack = MinimumStack<Int>(maxSize: input.count)
for n in input {
    try? minimumStack.push(data: n)
}
try? minimumStack.minimumValue()

Queue

A queue is a data structure where you add elements to the end of the queue and remove elements from the beginning of the queue

FIFO: First In First Out == LILO: List In Last Out

The operations on a Queue are performed at two ends, removal is at the beginning and addition is at the end of the Queue.

Operations

Enqueue

Adding a new element to the end of the queue is called

Enqueue an element from the queue

Dequeue

Removing an element from the beginning of a queue is called

Dequeue an element from the queue

Peek

Similar to a stack you might just want to see what the first element in a queue is without removing it

Peek at the first element in a queue

Offer

The queue implementation in Java has another useful method

Add to a queue if space is available

Edge case

What if you try to dequeue from an empty queue?

Or Enqueue into a full queue?

-> Throw an exception!

Underlying Data Structure

Linked List is commonly used

The most common operations on a queue involve enqueuing and dequeuing elements

The operations are on both ends of the queue

A linked list with a pointer to head and the tail works well

A common data structure used is a circular queue with pointers to the head and to the tail

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463696#overview

Enqueue

Dequeue

Exercise 1. Circular Queue

It can be implemented using an array where the last element wraps around to the first element

Implementation

Head = -1

A special value to denote an empty list

Tail

Always indicates last index

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463698#overview

Enqueue datas until It is full

Dequeue n items

enum QueueError: Error {
    case queueOverflow
    case queueUnderflow
}

class Queue {
    private let specialEmptyValue = -1
    private let size: Int
    private var items = Array<Int?>()
    
    
    //Initialize both the head and the tail indices to the special value
    private var headIndex: Int
    private var tailIndex: Int
    
    init(size: Int) {
        headIndex = specialEmptyValue
        tailIndex = specialEmptyValue
        self.size = size
        //Create an array with fixed size
        self.items = Array(repeating: nil, count: size)
    }
    
    //Enqueue doesn't affect headIndex except for empty case
    func enqueue(data: Int) throws {
        if isFull {
            throw QueueError.queueOverflow
        }
        //Get the next tail index and insert the new element there
        tailIndex = (tailIndex + 1) % items.count
        items[tailIndex] = data
        
        //This is the first element enqueued, set the head index to the tail index
        if headIndex == specialEmptyValue {
            headIndex = tailIndex
        }
    }
    
    func dequeue() throws -> Int {
        if isEmpty {
            throw QueueError.queueUnderflow
        }
        guard let firstElement = items[headIndex] else {
            throw QueueError.queueUnderflow
        }
        //Edge case - This element is the last item in a queue (It means there is only one item in a queue)
        if headIndex == tailIndex {
            headIndex = specialEmptyValue
        }
        else {
            headIndex = (headIndex + 1) % items.count
        }
        return firstElement
    }
    
    //Headindex is always set to special marker value when the queue is empty
    var isEmpty: Bool {
        headIndex == specialEmptyValue
    }
    
    //WHen the queue is full this means that the head index and tail index are right next to one another
    var isFull: Bool {
        let nextIndex = (tailIndex + 1) % items.count
        //Check whether the next position of the tail is the head index
        return nextIndex == headIndex
    }
}

The Queue – Performance and Complexity

Enqueuing and Dequeuing implemented in this way is O(1)

IsEmpty and IsFull is also O(1)

Space complexity is O(N)

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463698#overview

Exercise 2. Build a Queue with Two Stack

Where can a queue be used?

Customer service hotline, calls are assigned to representatives in the order that they are received

Queueing jobs to be printed

Any order processing systems like in e-commerce websites or bank transaction systems

Implement a Queue using two stacks

Forward Stack

It used to push the enqueued elements

Enqueue operations are always performed on the forward stack

Enqueue requires moving all elements to the forward stack and pushing the last element in I.E. The top

Reverse Stack

Holds the elements in reverse order from the forward stack

Dequeue operations are always performed on the reverse stack

Dequeue requires moving all elements to the reverse track and popping the last element in I.E the Top

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463700#overview

So It looks tricky. It has 2 stacks to implement Enqueue and Dequeue operation like a Queue.

enum StackError: Error {
    //Pushing into a full stack
    case stackOverflow
    //Popping from or peeking into an empty stack
    case stackUnderflow
}

class Stack<T> {
    private let maxSize: Int
    private(set) var array = Array<T>()
    //Topmost element in the stack
    private var top: T?
    //Track the size of the stack at every push, pop
    //This means the stack size operation can be constant time
    private var size = 0
    
    init(maxSize: Int) {
        self.maxSize = maxSize
    }
    
    func push(data: T) throws {
        if size == maxSize {
            throw StackError.stackOverflow
        }
        array.append(data)
        top = data
        size += 1
    }
    
    func pop() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        //Remove the top element from the stack and return it's data
        let topElement = array.removeLast()
        top = array.last
        size -= 1
        return topElement
    }
    
    func peek() throws -> T {
        if size == 0 {
            throw StackError.stackUnderflow
        }
        guard let topElement = top else {
            throw StackError.stackUnderflow
        }
        //Just return the data of the top element, do not remove it
        return topElement
    }
    
    var isEmpty: Bool {
        size == 0
    }
    
    var isFull: Bool {
        size == maxSize
    }
}

class QueueUsingTwoStack<T> {
    let forwardStack: Stack<T>
    let reverseStack: Stack<T>
    
    init(size: Int) {
        self.forwardStack = Stack<T>(maxSize: size)
        self.reverseStack =  Stack<T>(maxSize: size)
    }
    
    var isFull: Bool {
        forwardStack.isFull || reverseStack.isFull
    }
    
    var isEmpty: Bool {
        forwardStack.isEmpty && reverseStack.isEmpty
    }
    
    func enqueue(data: T) throws {
        if isFull {
            throw StackError.stackOverflow
        }
        if forwardStack.isEmpty {
            //Push all elements from the reverse stack to the forward stack, enqueue always happens on the forward stack
            while !reverseStack.isEmpty {
                let popedValue = try reverseStack.pop()
                try forwardStack.push(data: popedValue)
            }
        }
        //Finally do the enqueue - A push on the forward stack
        try forwardStack.push(data: data)
    }
    
    func dequeue() throws -> T {
        if isEmpty {
            throw StackError.stackUnderflow
        }
        if reverseStack.isEmpty {
            //Push all elements from the forward stack to the reverse stack, dequeue alwyas happens on the reverse stack
            while !forwardStack.isEmpty {
                let poppedValue = try forwardStack.pop()
                try reverseStack.push(data: poppedValue)
            }
        }
        //Finally do the dequeue - A pop on the reverse stack
        return try reverseStack.pop()
    }
}

let queue = QueueUsingTwoStack<Int>(size: 4)

try? queue.enqueue(data: 1)
try? queue.enqueue(data: 2)
try? queue.enqueue(data: 3)
try? queue.enqueue(data: 4)
queue.isFull

try? queue.dequeue()

Performance

All enqueues and then all dequeues are O(1) – If only one of these operations are performed

Notice that each element is pushed no more than twice

Once onto the forward stack to enqueue it and once onto the reverse stack just before dequeueing

Each element is popped no more than twice

Once to move to the reverse from the forward stack just before dequeuing and then to actually dequeue it

Time complexity is O(M) where M is the number of operations we perform on the queue.
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463700#overview

Shawn