What is a Queue?
A Queue is an abstract data type that serves as an ordered collection of elements.
A simple queue typically has several operations:
push(item)
- adds an item to thetail
pop()
- removes and returns an item from thehead
These operations make a queue a FIFO (First In, First Out) data structure.
Implementation
There are two ways to implement a queue.
The first and simplest (but less efficient) way is by using an array and basic operations:
struct Queue {
private(set) var queue: [Int]
init(queue: [Int] = []) {
self.queue = queue
}
mutating func push(_ item: Int) {
self.queue.insert(item, at: 0)
}
mutating func pop() -> Int? {
return self.queue.popLast()
}
func peek() -> Int? {
return self.queue.last
}
}
The second, more efficient way is by using a linked list, which allows push
and pop
operations in O(1) time.
final class Node {
private(set) var val: Int
var next: Node?
init(
val: Int,
next: Node? = nil
) {
self.val = val
self.next = next
}
}
final class LinkedListQueue {
private(set) var head: Node?
private(set) var tail: Node?
func push(_ item: Int) {
let newNode = Node(val: item)
if head == nil {
self.head = newNode
self.tail = newNode
return
}
self.tail?.next = newNode
self.tail = newNode
}
func pop() -> Int? {
if head == nil {
return nil
}
let tmp = self.head
self.head = tmp?.next
if self.head == nil {
self.tail = nil
}
return tmp?.val
}
}
Time/Space Complexity using a Linked List Queue
Operation | Average | Worst Case |
---|---|---|
Insert | O(1) | O(1) |
Delete | O(1) | O(1) |
Space Complexity: O(n) for both average and worst case.