Stacks & Queues

Overview

Stacks and queues are fundamental linear data structures that provide restricted access to elements. They are widely used in algorithms, system design, and real-world software applications such as parsers, task scheduling, and breadth/depth-first search.

In Swift, stacks and queues can be implemented using arrays or linked lists, depending on performance needs.

Stacks

A stack is a Last-In-First-Out (LIFO) structure. Think of it like a stack of plates: you add to the top and remove from the top.

Basic Operations

• push(_:) – Add to the top

• pop() – Remove from the top

• peek() – View the top element without removing it

Stack Implementation Using Array

struct Stack<T> {
	private var elements: [T] = []

	var isEmpty: Bool {
		return elements.isEmpty
	}

	var count: Int {
		return elements.count
	}

	mutating func push(_ value: T) {
		elements.append(value)
	}

	mutating func pop() -> T? {
		return elements.popLast()
	}

	func peek() -> T? {
		return elements.last
	}
}

Example Usage

var stack = Stack<Int>()
stack.push(10)
stack.push(20)
stack.pop()   // 20
stack.peek()  // 10

Queues

A queue is a First-In-First-Out (FIFO) structure. Like a line at a store, the first person to enter is the first to be served.

Basic Operations

• enqueue(_:) – Add to the rear

• dequeue() – Remove from the front

• peek() – View the front element without removing it

Queue Implementation Using Array

struct Queue<T> {
	private var elements: [T] = []

	var isEmpty: Bool {
		return elements.isEmpty
	}

	var count: Int {
		return elements.count
	}

	mutating func enqueue(_ value: T) {
		elements.append(value)
	}

	mutating func dequeue() -> T? {
		return isEmpty ? nil : elements.removeFirst()
	}

	func peek() -> T? {
		return elements.first
	}
}

Queue Implementation Using Two Stacks

struct EfficientQueue<T> {
	private var input: [T] = []
	private var output: [T] = []

	mutating func enqueue(_ value: T) {
		input.append(value)
	}

	mutating func dequeue() -> T? {
		if output.isEmpty {
			output = input.reversed()
			input.removeAll()
		}
		return output.popLast()
	}

	func peek() -> T? {
		return output.isEmpty ? input.first : output.last
	}

	var isEmpty: Bool {
		return input.isEmpty && output.isEmpty
	}
}

Performance Comparison

Use Cases

Stack

• Undo/redo operations

• Syntax parsing (e.g., balanced parentheses)

• Function call stack

• Depth-first search

Queue

• Task scheduling

• Breadth-first search

• Buffers (e.g., print/spool queue)

• Order processing systems

Best Practices

• Use struct for value semantics.

• Prefer specialized structures (like EfficientQueue) when performance matters.

• Ensure thread-safety in concurrent environments (e.g., with DispatchQueue or locks).

• Avoid removeFirst() on large arrays if performance is critical.

Conclusion

Stacks and queues are essential tools in a developer’s toolbox. While Swift’s array type can be used to implement both structures easily, it’s important to understand their time complexity and performance implications.

In the next chapter, we’ll dive into Trees, starting with binary trees and traversals, and explore how they are used in decision-making and hierarchical data modeling.