Stacks and Queues: Why Swift Has No Stack Type

When you start studying data structures, the first two siblings you meet are the stack and the queue.

The concepts take five minutes. But Swift raises a question: the standard library has Array, Dictionary, and Set, yet no Stack or Queue type. This article explains why and how to work without them.

The performance landmine (removeFirst()) that appears when arrays imitate queues is a common cause of timeouts in coding tests, so we cover it separately.

The stack here is a data structure, not a memory-allocation area. The naming distinction continues in Memory Stack vs Heap, while the next step—queues with priorities—is covered in Heap and Priority Queue.

---

The Concept Is Just Plates and a Line

A stack is LIFO (Last In, First Out). The last item added comes out first. Think of a plate pile: push onto the top and pop from the top. Removing from the middle is cheating.

A queue is FIFO (First In, First Out). The first item added comes out first. Think of a checkout line: enqueue at the back and dequeue from the front.

There are only two operations for each.

	Push	Pop	Peek
Stack	push	pop	peek(top)
Queue	enqueue	dequeue	front

Why does this matter? Because this simple rule underpins many parts of iOS development.

• Call stack: function calls and returns are exactly push/pop. The crash caused by deep recursion is not called stack overflow for no reason.
• UINavigationController: pushViewController / popViewController — screen transitions are literally a stack.
• Undo: commands are pushed onto a stack and reversed in order.
• GCD (Grand Central Dispatch)’s DispatchQueue: it is a queue by name and nature. Tasks in a serial queue run in insertion order.
• BFS/DFS: using a queue for graph traversal gives BFS (Breadth-First Search); using a stack gives DFS (Depth-First Search). Choosing the data structure means choosing the algorithm.

---

Why Swift Has No Stack

The short answer: Array is already a perfect stack.

var stack: [Int] = []
stack.append(3)      // push — O(1)
stack.append(7)
let top = stack.last // peek — O(1)
let popped = stack.popLast() // pop — O(1), When empty nil

Adding and removing at an array’s end are O(1) operations—more precisely, amortized O(1), since expansion costs occur only when the internal buffer fills. A separate type would merely wrap Array, so the standard library chose not to add one.

If you want the intent to be explicit, a thin wrapper is conventional.

struct Stack<Element> {
    private var storage: [Element] = []
    var isEmpty: Bool { storage.isEmpty }
    var top: Element? { storage.last }
    mutating func push(_ element: Element) { storage.append(element) }
    mutating func pop() -> Element? { storage.popLast() }
}

It blocks subscript, enforcing the stack rule of “no middle access” through the type.

---

Building a Queue with an Array Is a Trap

A queue built with the same logic as a stack looks like this.

var queue: [Int] = []
queue.append(1)              // enqueue — O(1), No problem
let first = queue.removeFirst() // dequeue — O(n), Here's the trap

removeFirst() removes the first element and ** shifts every remaining element forward by one.** With 100,000 elements, one dequeue causes 100,000 moves. Repeating this thousands of times in an algorithm such as BFS makes the whole operation O(n²), causing a coding-test timeout.

There are three solutions.

1. Advance the front by index (the coding-test standard)

var queue: [Int] = []
var head = 0
// enqueue
queue.append(5)
// dequeue
let value = queue[head]
head += 1

Move only the read position instead of removing elements. dequeue becomes O(1). The used prefix remains allocated, but this is almost always sufficient in coding tests.

2. Build a queue with two stacks (a classic interview question)

Push incoming items onto the in stack. When removing, if out is empty, transfer all items from in in reverse order, then pop. Each item moves at most twice, giving amortized O(1). This is also the standard answer to “implement a queue with stacks.”

3. Deque from swift-collections (the production answer)

Apple’s swift-collections package provides Deque, which uses a ring buffer, so insertion and removal at both ends are O(1).

import DequeModule

var queue: Deque<Int> = []
queue.append(1)            // enqueue
let v = queue.popFirst()   // dequeue — O(1)

Its API is almost identical to Array, so migration is inexpensive. When you need a queue in production, use this instead of writing one yourself.

---

How to Choose Between Them

When in doubt, ask one question: “Should I process the newest item first, or the oldest item first?”

• Undo, matching parentheses, backtracking visited paths, depth-first search → newest first → stack
• Work queues, event handling, printer output, breadth-first search → arrival order → queue

Matching parentheses is a classic stack use case. Push opening parentheses; pop on closing ones and verify the pair. If the stack is empty at the end, the expression is valid. Compilers check braces by the same principle.

---

Summary

• Stack means LIFO; queue means FIFO—plates and checkout lines are the whole concept.
• Call stacks, navigation stacks, and undo use stacks; DispatchQueue, event handling, and BFS use queues. They are already everywhere in iOS development.
• Swift has no Stack type because Array’s append/popLast is already an O(1) stack.
• When an array implements a queue, removeFirst() is O(n)—a common cause of coding-test timeouts.
• The solutions are a head index, two stacks, or, in production, Deque from swift-collections.
• The choice between stack and queue comes down to one question: newest first or arrival order first?

Next, we will cover their extensions—heaps and priority queues—and the hash table behind Dictionary.