Queue implemented using two stacks in Swift

Question

I need your expert opinion! In fact, for a Leetcode Problem, I had to code a queue using 2 stacks. It's shown just below and functions well.

It is a pretty simple code with peek, pop, push, etc. functions, quite classic. But this code does not please me completely since I coalesce the optionals with a default value, taken out of my hat, to avoid forced unwrapping.

Do you see a more professional way to write this?

class MyQueue {

private var stack1: [Int]
private var stack2: [Int]
private var front: Int?

init() {
  stack1 = []
  stack2 = []
}

func push(_ x: Int) {
  if stack1.isEmpty {
    front = x
  }
  stack1.append(x)
}

func pop() -> Int {
  if stack2.isEmpty {
    while !stack1.isEmpty {
      stack2.append(stack1.popLast() ?? -1)
    }
  }
  return stack2.popLast() ?? -1
}

func peek() -> Int {
  if !stack2.isEmpty {
    return stack2.last ?? -1
  }

  return front ?? -1
}

func empty() -> Bool {
  return stack1.isEmpty && stack2.isEmpty
    }
}

Answer 1

Don't use “magic” values (in your case: -1) to indicate the absence of a value. Swift has the Optional type exactly for that purpose. The queue methods should be declared as

func push(_ x: Int)
func pop() -> Int?
func peek() -> Int?
func empty() -> Bool

and nil is returned if the queue is empty.

There is nothing special about the Int type here. It is simple to make the queue type generic

class MyQueue<Element> {

    func push(_ x: Element)
    func pop() -> Element?
    func peek() -> Element?
    func empty() -> Bool
}

and now you can use it with arbitrary types. For example

let queue = MyQueue<String>()
queue.push("foo")

There is no need for a dedicated front element, and the code becomes simpler without it.

Moving the elements from the first to the second stack in func pop() can be simplified to

while let elem = stack1.popLast() {
    stack2.append(elem)
}

with a single test instead of two per iteration. Or even simpler:

stack2 = stack1.reversed()
stack1.removeAll()

(If your queues become really large then you might want to check which of the above methods is faster.)

If a function body consists of a single expression then the return keyword can be omitted.

Putting it all together, we get

class MyQueue<Element> {
    
    private var stack1: [Element]
    private var stack2: [Element]
    
    init() {
        stack1 = []
        stack2 = []
    }
    
    func push(_ x: Element) {
        stack1.append(x)
    }
    
    func pop() -> Element? {
        if stack2.isEmpty {
            stack2 = stack1.reversed()
            stack1.removeAll()
        }
        return stack2.popLast()
    }
    
    func peek() -> Element? {
        stack2.last ?? stack1.first
    }
    
    func empty() -> Bool {
        stack1.isEmpty && stack2.isEmpty
    }
}

which is shorter and simpler.

Finally, naming:

• I had to inspect the code in order to understand that what you have implemented is a “first in, first out” queue. This would be more obvious to a user of your code (or to you in one year) with a more specific class name, such as FIFO or FIFOQueue.

• Typical names for adding something to a FIFO and retrieving it are enqueue and dequeue.

• Swift collection types typically use “isEmpty” as the name of a property which indicates whether the collection contains elements or not:

  var isEmpty: Bool {
      stack1.isEmpty && stack2.isEmpty
  }