Queue Optimized - dequeu is not O(1)

[chipbk10]

Brief Intro

Queue Optimized - dequeue is not O(1)

More Details

    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }

If the condition happens, the complexity will be O(n/4) ~ O(n)
I think you should use LinkedList to implement a Queue to archive O(1) in all cases of dequeue

[iiicey]

邮件已收到。我会尽快回复！祝您一切顺利！兰雨田

[hollance]

The text says that it's O(1) on average, or "O(1) amortized". Same as appending to an array. When it happens it's slow but it only happens rarely, so it doesn't matter. (Unless you need a guarantee that it's "never slower than X", which this doesn't give.)

[chipbk10]

"Same as appending to an array" is not correct. Appending element in array in Swift is always O(1). Do you think in Java or Python, they have the same implementation like we do here for the Queue?

[hollance]

Appending an element to a Swift array is also O(1) amortized, which is not the same as O(1).

Just to make it clear: this Queue implementation does not mean to be optimal. It just shows one way that dequeuing can be made faster. Using a linked list would give O(1) dequeuing indeed but comes with other trade-offs.

[chipbk10]

Can you please tell me what is the other trade-offs if we use LinkedList?

[hollance]

The advantage of using an array as the backing store for the queue is that this is a contiguous area of memory. That means it's really easy to iterate through the queue (just increment or decrement the index). It also helps with efficient cache access. With a linked list, the nodes are connected with pointers so it's slower to go from one node to the next, plus the nodes could be located anywhere in memory, which is worse for the cache.

[chipbk10]

You are right about appending an element to a Swift array is also O(1) amortized. Thanks for that.

https://developer.apple.com/documentation/swift/array/3126937-append

The trade-off to use LinkedList here is the memory cost. It will cost more memory than using an array, because, each node in LinkedList holds data and reference to next. Meanwhile, an array holds only actual data and its index.

Thank you for the discussion.

[kelvinlauKL]

You are right about appending an element to a Swift array is also O(1) amortized. Thanks for that.

https://developer.apple.com/documentation/swift/array/3126937-append

The trade-off to use LinkedList here is the memory cost. It will cost more memory than using an array, because, each node in LinkedList holds data and reference to next. Meanwhile, an array holds only actual data and its index.

Thank you for the discussion.

Memory + the fact that reference types are always stored in the heap. This means every modification to the linked list (such as appending / removing a node) would require a locking operation on the heap. That has a cost to performance - whereas simple values in a Swift array can sit in the stack - which doesn't require a lock

[hollance]

I don't think that appending / removing nodes uses any kind of lock, plus there is no guarantee that a Swift array will be stored on the stack. (Allocating new nodes, however, might require a lock.)

[kelvinlauKL]

Hmm, I was under the assumption that if the array housed "simple" types (i.e. [Int]), then it could be guaranteed in the stack.

[yuvashrikarunakaran]

import Foundation

// Node for the linked list
class Node {
var value: T
var next: Node?
var prev: Node?

init(value: T) {
    self.value = value
}

}

// Queue implemented using a doubly linked list
class LinkedListQueue {
private var head: Node?
private var tail: Node?
private var count = 0

// Enqueue operation - add element to the tail
func enqueue(_ value: T) {
    let newNode = Node(value: value)
    if let tailNode = tail {
        tailNode.next = newNode
        newNode.prev = tailNode
        tail = newNode
    } else {
        // If the queue is empty, both head and tail will be the same node
        head = newNode
        tail = newNode
    }
    count += 1
}

// Dequeue operation - remove element from the head
func dequeue() -> T? {
    guard let headNode = head else { return nil }

    // If there's only one element, reset head and tail
    if headNode.next == nil {
        tail = nil
    }

    head = headNode.next
    head?.prev = nil
    count -= 1

    return headNode.value
}

// Peek operation - return the front element without removing
func peek() -> T? {
    return head?.value
}

// Check if the queue is empty
func isEmpty() -> Bool {
    return count == 0
}

// Return the current count of elements in the queue
func size() -> Int {
    return count
}

}

// Example usage

let queue = LinkedListQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.dequeue() ?? "Queue is empty") // Outputs: 1
print(queue.dequeue() ?? "Queue is empty") // Outputs: 2
print(queue.peek() ?? "Queue is empty") // Outputs: 3
print(queue.size()) // Outputs: 1