What a stack is
A stack is a collection with one rule: the last element added is the first one removed. This order is called LIFO, for last in, first out. A pile of plates works the same way. You add a plate on top, and you take a plate from the top. The plate at the bottom waits the longest.
A stack supports a few operations:
- push adds an element on top;
- pop removes the top element and gives it back;
- peek looks at the top element without removing it;
- isEmpty tells whether the stack has no elements.
Each of these takes constant time on average, no matter how many elements the stack holds. That is the reason stacks appear in so many interview problems: whenever the most recent unfinished thing is the one to deal with next, a stack fits. Matching brackets, undoing actions, evaluating expressions and finding the next greater value in an array all work this way.
A stack with a Swift array
Swift's standard library has no separate stack type. An Array already does the job, as long as you only work at its end. Appending to the end of an array is fast, and so is removing the last element. Working at the front of an array is slow, because every other element has to shift, so the end of the array is the top of the stack.
var stack: [Int] = []
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)
print(stack.last as Any)
print(stack.removeLast())
print(stack)
[10, 20, 30]
Optional(30)
30
[10, 20]
The mapping to stack operations:
| Stack operation | Swift array |
|---|---|
| push | stack.append(x) |
| pop | stack.removeLast() or stack.popLast() |
| peek | stack.last |
| isEmpty | stack.isEmpty |
| size | stack.count |
The array must be a var, since pushing and popping change it. An empty one is written [Int]() or, with a type annotation, var stack: [Int] = [].
Two ways to pop
The two pop methods differ in what happens when the stack is empty:
removeLast()returns the element itself, not an optional. If the array is empty, the program crashes.popLast()returns an optional: the element, ornilif the array is empty.
var stack = [10, 20]
print(stack.popLast() as Any)
print(stack.popLast() as Any)
print(stack.popLast() as Any)
print(stack.isEmpty, stack.count)
Optional(20)
Optional(10)
nil
true 0
Likewise, last is an optional, nil for an empty array. In the lessons you will often see removeLast() used after an explicit if stack.isEmpty check, which is a clear way to say that the pop is safe at that point. Where you can't rule out an empty stack, popLast() or an if let avoids the crash:
var chars: [Character] = []
for ch in "abc" {
chars.append(ch)
}
var reversed = ""
while let c = chars.popLast() {
reversed.append(c)
}
print(reversed)
cba
Here the loop runs as long as popLast() gives a value. The letters come out in the reverse of the order they went in, which is the LIFO rule at work.
Wrapping it in a struct
You can hide the array behind a small generic type so the code reads like a stack:
struct Stack<Element> {
private var items: [Element] = []
var isEmpty: Bool { items.isEmpty }
var count: Int { items.count }
var top: Element? { items.last }
mutating func push(_ x: Element) { items.append(x) }
mutating func pop() -> Element? { items.popLast() }
}
var s = Stack<String>()
s.push("a")
s.push("b")
print(s.top as Any, s.count)
print(s.pop() as Any, s.pop() as Any, s.pop() as Any)
Optional("b") 2
Optional("b") Optional("a") nil
Because Stack is a struct, the methods that change it are marked mutating, and a stack must be declared with var. For short interview solutions, a plain array is usually enough.
Gotchas in Swift
- Value semantics. Arrays and structs are copied on assignment. After
var b = a, pushing ontobdoesn't affecta. Passing a stack to a function that needs to change it requires aninoutparameter. - Index versus top. The top is at index
stack.count - 1. Readingstack[stack.count - 1]on an empty array crashes, so checkisEmptyfirst or uselast. - Optional values.
lastandpopLast()return optionals. Comparing the unwrapped value directly needs!,if letor??. Usestack.last!only right after an emptiness check, as the loop condition of a typical stack solution does. - Stacking indices. Many problems push positions instead of values, because the position gives both the index and, through the array, the value. A stack of
Intindices is common. - Using the front.
insert(x, at: 0)andremoveFirst()take time proportional to the array's length, so keep the top at the end.
How you will use stacks in this chapter
In the lessons that follow, the stack stores things that wait for something to happen. In the bracket problem, it holds opening brackets until their closing partner arrives. In the next greater element problem, it holds indices whose answer isn't known yet. In both, the loop pops from the stack while a condition holds, and then pushes the current item. Because every element is pushed once and popped at most once, the whole loop is linear.
Key takeaways
- A stack is last in, first out: push and pop at the same end.
- In Swift, an array used at its end is a stack:
append,removeLastorpopLast,last,isEmpty. removeLast()crashes on an empty array, whilepopLast()givesnil.- Declare the stack with
var, and useinoutto let a function change it. - Each push and pop takes constant time on average, so a loop that pushes and pops each element once is
O(n).
