Data structure learning – Queue

The interface definition

A queue is a linear data structure with first in first out FIFO. The main interface design is to remove data in the header and add data in the tail. Here are the interfaces that need to be implemented roughly:

protocol Queue {

    associatedtype Element
    
    var isEmpty: Bool { get }
    var peek: Element? { get }
    
    mutating func enqueue(_ element: Element) -> Bool
    mutating func dequeue() -> Element?
}
Copy the code

You can see that the interface that needs to be implemented is very similar to the stack data structure that was implemented earlier.

Since different ways of storing data may have different complexity to implement the same method, the following four different ways will be used to implement the comparison of queue data structures.

Use arrays to implement queues

Basic code

Struct QueueArray<T> {var array: [T] = []Copy the code

Implementation agreement

extension QueueArray: Queue { var isEmpty: Bool { array.isEmpty } var peek: T? { array.first } mutating func enqueue(_ element: T) -> Bool {array.append(element) return true} mutating func dequeue() -> T? { array.removeFirst() } }Copy the code

Complexity analysis

Implementing a queue using Swift’s built-in array data type is simple, nothing to say. The following describes the enqueue and dequeue complexity of arrays:

operation	On average	Worst case
enqueue	O(1)	O(n)
dequeue	O(n)	O(n)
Spatial complexity	O(n)	O(n)

The overall complexity of enQueue is O(1) because the data is added directly to the end of the array, and O(n) is the worst case because if the current array is full, we need to expand the new memory and copy all the previous data into the new memory. However, The Times of capacity expansion are relatively few, so the time complexity of enqueue is O(1).

Dequeue removes the head element of the array directly, which causes all the elements after the head element to move forward by 1 bit, so the time of dequeue is O(n).

Space complexity is the amount of memory that needs to be allocated is N.

Here is the test code:

    func queueTest() {
        var queue = QueueArray<String>()
        queue.enqueue("Tom")
        queue.enqueue("Jerry")
        queue.enqueue("Jack")
        print("list: \(queue)")
        queue.dequeue()
        print("after dequeue, list: \(queue)")
        print("peek list = \(String(describing: queue.peek))")
    }
Copy the code

Output:

list: QueueArray<String>(array: ["Tom", "Jerry", "Jack"])
after dequeue, list: QueueArray<String>(array: ["Jerry", "Jack"])
peek list = Optional("Jerry")
Copy the code

Implement queues using bidirectional linked lists

What is implemented in the linked list data structure is a one-way linked list, which is structured like this:

Bidirectional lists look like this:

A node in a one-way list has only a reference to the next node, whereas each node in a bidirectional list has a reference to the next node and a reference to the previous node.

Because the current need to achieve is a queue data structure, the following directly posted bidirectional linked list code implementation:

public class Node<T> { public var value: T public var next: Node<T>? Public var previous: Node<T>? Public init(value: T) {self.value = value}} Extension Node: CustomStringConvertible { public var description: String { String(describing: value) } } public class DoublyLinkedList<T> { private var head: Node<T>? private var tail: Node<T>? public init() { } public var isEmpty: Bool { head == nil } public var first: Node<T>? { head } public func append(_ value: T) { let newNode = Node(value: value) guard let tailNode = tail else { head = newNode tail = newNode return } newNode.previous = tailNode tailNode.next  = newNode tail = newNode } public func remove(_ node: Node<T>) -> T { let prev = node.previous let next = node.next if let prev = prev { prev.next = next } else { head = next  } next? .previous = prev if next == nil { tail = prev } node.previous = nil node.next = nil return node.value } } extension DoublyLinkedList: CustomStringConvertible { public var description: String { var string = "" var current = head while let node = current { string.append("\(node.value) -> ") current = node.next } return string + "end" } } public class LinkedListIterator<T>: IteratorProtocol { private var current: Node<T>? init(node: Node<T>?) { current = node } public func next() -> Node<T>? { defer { current = current? .next } return current } } extension DoublyLinkedList: Sequence { public func makeIterator() -> LinkedListIterator<T> { LinkedListIterator(node: head) } }Copy the code

Basic code

Bidirectional linked list as the underlying data store basic code:

Struct QueueLinkedList<T> {var list = DoublyLinkedList<T>()}Copy the code

Implementation agreement

extension QueueLinkedList: Queue { var isEmpty: Bool { list.isEmpty } var peek: T? { list.first? .value } mutating func enqueue(_ element: T) -> Bool { list.append(element) return true } mutating func dequeue() -> T? { guard let first = list.first else { return nil } return list.remove(first) } }Copy the code

Complexity analysis

As you can see, the implementation code is very simple. Here is the analysis of complexity:

operation	On average	Worst case
enqueue	O(1)	O(1)
dequeue	O(1)	O(1)
Spatial complexity	O(n)	O(n)

The time complexity of enqueue and dequeue operations is O(1), and the space complexity is O(n), because the bidirectional linked list does not need to be dynamically expanded by a certain multiple, and all nodes do not need to be moved when nodes are deleted or added.

Whereas each enqueue operation requires a dynamic allocation of the current node’s memory, arrays add to the memory already allocated.

(Array memory allocation is easy to manage, linked list is not necessarily contiguous allocation)

The queue is implemented using a Ring Buffer

The initial memory size of the circular buffer is fixed. Its rough data structure is as follows:

• The read pointer points to the current read position;

• The write pointer points to the next position to write;

If the read pointer and the write pointer point to the same location, the data is null. If the write pointer points to the end of memory, the write pointer points to the beginning of the data on the next write in a loop (read operations are also read in a loop).

For example, write operations start like this:

To this:

So if there is data at the current write location, the write operation may fail.

The implementation address of the circular buffer

Let’s paste the circular buffer directly:

public struct RingBuffer<T> { private var array: [T?]  private var readIndex = 0 private var writeIndex = 0 public init(count: Int) { array = Array<T? >(repeating: nil, count: count) } public var first: T? { array[readIndex] } public mutating func write(_ element: T) -> Bool { if ! isFull { array[writeIndex % array.count] = element writeIndex += 1 return true } else { return false } } public mutating  func read() -> T? { if ! isEmpty { let element = array[readIndex % array.count] readIndex += 1 return element } else { return nil } } private var  availableSpaceForReading: Int { writeIndex - readIndex } public var isEmpty: Bool { availableSpaceForReading == 0 } private var availableSpaceForWriting: Int { array.count - availableSpaceForReading } public var isFull: Bool { availableSpaceForWriting == 0 } } extension RingBuffer: CustomStringConvertible { public var description: String { let values = (0.. <availableSpaceForReading).map { String(describing: array[($0 + readIndex) % array.count]!) } return "[" + values.joined(separator: ", ") + "]" } }Copy the code

Basic code

Cyclic buffer as the underlying data store basic code:

Struct QueueRingBuffer<T> {private var ringBuffer: ringBuffer <T> Int) { ringBuffer = RingBuffer(count: count) } }Copy the code

Implementation agreement

extension QueueRingBuffer: Queue {
    
    var isEmpty: Bool {
        ringBuffer.isEmpty
    }
    
    var peek: T? {
        ringBuffer.first
    }
    
    mutating func enqueue(_ element: T) -> Bool {
        ringBuffer.write(element)
    }
    
    mutating func dequeue() -> T? {
        ringBuffer.read()
    }
}
Copy the code

Complexity analysis

Here is the analysis of complexity:

operation	On average	Worst case
enqueue	O(1)	O(1)
dequeue	O(1)	O(1)
Spatial complexity	O(n)	O(n)

The time complexity of enqueue and dequeue operations is O(1) and the space complexity is O(n). And since the number of elements is determined at initialization, the underlying array structure does not need to be dynamically expanded, but there is a drawback that writes may fail.

Implement queues with two arrays

The point of using two arrays to implement queues is that one array enqueue and the other dequeue.

Basic code

Struct QueueDoubleArray<T> {private var leftArray: Array<T> = [] private var rightArray: Array<T> = []Copy the code

Implementation agreement

extension QueueDoubleArray: Queue { var isEmpty: Bool { leftArray.isEmpty && rightArray.isEmpty } var peek: T? { leftArray.isEmpty ? rightArray.last : leftArray.last } mutating func enqueue(_ element: T) -> Bool { rightArray.append(element) return true } mutating func dequeue() -> T? {if leftarray.isEmpty {// Although this operation is O(n), this operation is performed relatively few times, LeftArray = rightarray.removeall () // The elements of the right enqueue array are added to the left dequeue array rightarray.removeall () // Return leftarray.poplast ()}}Copy the code

Complexity analysis

Here is the analysis of complexity:

operation	On average	Worst case
enqueue	O(1)	O(1)
dequeue	O(1)	O(1)
Spatial complexity	O(n)	O(n)

The enqueue operation is added to the end of the array on the right, without moving any existing elements of the array, O(1) operation.

In the dequeue operation, the data on the left is the reverse order of the data on the right, so leftarray.poplast () does not move the existing elements and returns the latest enqueue.

Compared with the queue implemented by the singular group, the dequeue operation implemented by the even group is O(1). Compared with the queue of linked list, the memory area of the queue of even group is continuous, and the memory management of the system is more efficient. In contrast to the circular buffer implementation queue, the binary implementation queue does not have a fixed number of elements in the queue when initialized.