📦Queue

🚧 under construction

data structure ⟩ Queue

👥 相關

• Stack

⬇️ 應用

• WaitingList - a Stack or a Queue.

📗 參考

• Advanced Swift (2017.11) ⟩ Ch. 3, Queue: A Custom Collection

• Data Structures and Algorithms in Swift ⟩ Ch. 8, Queues

• Scalar ⟩ JavaScript Queue

• JavaScript Tutorial ⟩ JavaScript Queue

implementations

JS

• replit ⟩ WaitingList ⟩ Queue

// ⭐ Queue
//    2022.12.29 - 13.28 : add `.explored`
// ---------------------------------------------------------------------------
// 🔹 q.enqueue()
// 🔹 q.dequeue()
// 🔸 q.first
// 🔸 q.length
// 🔸 q.isEmpty
// ---------------------------------------------------------------------------
// 🔸 q.visited            visited items
// 🔸 q.waiting            waiting items
// 🔸 q.explored           = visited + waiting
// 🔹 q.isVisited()        check if item is visited
// 🔹 q.isWaiting()        check if item is waiting
// 🔹 q.isExplored()       check if item is explored (= visited or waiting)
// ---------------------------------------------------------------------------
// 🔹 toString()
// 🔹 q.log()
// 🔸 q.debugInfo
//
// implementing "queue" using an "array".
class Queue {

    // 🔸 private members
    #items = [];            // explored = visited + waiting 
    #head = 0;              // index for first waiting node in queue
    
    // ⭐ const q = new Queue(a, b, c ...)
    constructor(...items) {
        this.#items.push(...items);
    }
    
    // 🔹 q.enqueue(a, b, c ...)
    enqueue(...items) {
        this.#items.push(...items);
    }
    
    // 🔹 q.dequeue()
    dequeue() {
        if (this.isEmpty) return null;
        const head = this.first;
        this.#head += 1;
        return head;
    }
    
    // 🔸 q.first
    get first() {
        if (this.isEmpty) return null;
        return this.#items[this.#head];
    }
    
    // 🔸 q.length
    get length() {
        return this.#items.length - this.#head;
    }
    
    // 🔸 q.isEmpty
    get isEmpty() {
        return this.length === 0;
    }

    // -------------
    //   dubugging
    // -------------

    // 🔹 toString()
    toString() {
        const str = `Queue:\n` +
            ` • visited: [${this.visited}]\n` +
            ` • waiting: [${this.waiting}]\n` +
            `            ${this.debugInfo}`;
        return str;
    }

    // 🔸 q.visited
    get visited() {
        return this.#items.slice(0, this.#head);
    }

    // 🔸 q.waiting
    get waiting() {
        return this.#items.slice(this.#head);
    }

    // 🔸 q.explored
    get explored() {
        return this.#items.slice();
    }

    // 🔹 q.isVisited()
    isVisited(item) {
        return this.visited.includes(item);
    }

    // 🔹 q.isWaiting()
    isWaiting(item) {
        return this.waiting.includes(item);
    }

    // 🔹 q.isExplored()
    isExplored(item) {
        return this.#items.includes(item);
    }

    // 🔹 q.log()
    log() {
        console.log(this.toString());
    }

    // 🔸 q.debugInfo
    get debugInfo() {
        return `(H: ${this.#head}, T: ${this.#items.length}, L: ${this.length})`;
    }
}

module.exports = { Queue };

💈範例：

const { log } = console;

// ⭐ import
const { Queue } = require('../DataStructure/Queue.js');

// test Queue
function test_Queue() {
    
    const q = new Queue(1, 2, 3); 
    
    // ✅ execute commands
    ;[
        // commands        value    Queue        H  T  L    | value   Stack
        // --------------------------------------------------------------------
        `q`,              //        <- 1,2,3]    0  3  3    |        [1,2,3 ->
        `q.dequeue()`,    // 1      <- 2,3]      1  3  2    | 3      [1,2   
        `q.first`,        // 2                              | 2
        `q.dequeue()`,    // 2      <- 3]        2  3  1    | 2      [1   
        `q.enqueue(4)`,   //        <- 3,4]      2  4  2    |        [1,4  
        `q.dequeue()`,    // 3      <- 4]        3  4  1    | 4      [1
        `q.dequeue()`,    // 4      <- ]         4  4  0    | 1      [
        `q.dequeue()`,    // null   <- ]         4  4  0    | null   [
        `q.isEmpty`,      // true                           | true

    ].forEach(cmd => {
        log('-'.repeat(40));
        log(`${cmd}`);
        const value = eval(cmd);      // execute command
        if (!(value instanceof Queue)) { log(value); }
        log(q.toString());
    });
}

📃 結果：

command:  q
Queue:
 • visited: []
 • waiting: [1,2,3]
            (H: 0, T: 3, L: 3)
----------------------------------------
command:  q.dequeue()
 result:  1
Queue:
 • visited: [1]
 • waiting: [2,3]
            (H: 1, T: 3, L: 2)
----------------------------------------
command:  q.first
 result:  2
Queue:
 • visited: [1]
 • waiting: [2,3]
            (H: 1, T: 3, L: 2)
----------------------------------------
command:  q.dequeue()
 result:  2
Queue:
 • visited: [1,2]
 • waiting: [3]
            (H: 2, T: 3, L: 1)
----------------------------------------
command:  q.enqueue(4)
 result:  undefined
Queue:
 • visited: [1,2]
 • waiting: [3,4]
            (H: 2, T: 4, L: 2)
----------------------------------------
command:  q.dequeue()
 result:  3
Queue:
 • visited: [1,2,3]
 • waiting: [4]
            (H: 3, T: 4, L: 1)
----------------------------------------
command:  q.dequeue()
 result:  4
Queue:
 • visited: [1,2,3,4]
 • waiting: []
            (H: 4, T: 4, L: 0)
----------------------------------------
command:  q.dequeue()
 result:  null
Queue:
 • visited: [1,2,3,4]
 • waiting: []
            (H: 4, T: 4, L: 0)
----------------------------------------
command:  q.isEmpty
 result:  true
Queue:
 • visited: [1,2,3,4]
 • waiting: []
            (H: 4, T: 4, L: 0)

Swift

• replit ⟩ Queue (swift)

struct Queue<T>: QueueProtocol {

  // backing store
  var outs = [T]()  // for dequeue
  var ins = [T]()   // for enqueue

  public init() {}

  public mutating func enqueue(_ element:T) {
    ins.append(element)
  }

  // removes front of queue
  @discardableResult
  public mutating func dequeue() -> T? {
    // if outs is empty, move items from ins to outs
    if outs.isEmpty {
      outs = ins.reversed()
      ins.removeAll()
    }
    // get item from outs
    return outs.popLast()
  }

  // queue.isEmpty
  public var isEmpty: Bool {
    return ins.isEmpty && outs.isEmpty
  }

  public var first: T? {
    if !outs.isEmpty { return outs.last }
    return ins.first
  }

}// end: Queue

// CustomStringConvertible
extension Queue: CustomStringConvertible {
  // print(queue) -> " ⇢ 3, 2, 1 ⇢"
  public var description: String {
    return " ⇢ [ " 
      + (isEmpty ? " " : (ins.reversed() + outs).map {"\($0)"}.joined(separator: ", "))
      + " ] ⇢ "
  }
}

• replit ⟩ QueueProtocol (swift)

public protocol QueueProtocol: ExpressibleByArrayLiteral {
  associatedtype Element
  init()  // default initializer
  mutating func enqueue(_ element:Element)
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var first: Element? { get }
}

extension QueueProtocol {

  /// initializers

  // 1. var q = Queue([1,2,3])
  public init(_ items:[Element]) {
    self.init()
    self.enqueue(items)
  }

  // 2. var q = Queue(1,2,3)
  public init(_ items:Element...) {
    self.init(items)    // go to 1.
  }

  /// enqueue

  // 4. queue.enqueue([1,2,3])
  public mutating func enqueue(_ items:[Element]) {
    for item in items { enqueue(item) }
  }

  // 5. queue.enqueue(1,2,3)
  //    queue.enqueue(4)
  public mutating func enqueue(_ items:Element...) {
    enqueue(items)    // go to 4.
  }

}// end: extension

// ExpressibleByArrayLiteral
extension QueueProtocol {
  // 3. var q:Queue<Int> = [1,2,3]
  public init(arrayLiteral items:Element...) {
    self.init(items)    // go to 1.
  }
}

archive code

JS

• replit ⟩ Queue (using object)

• archived：2022.12.29

// ⭐ Queue
// ---------
// implementing "queue" using an "object".
// 像銀行櫃檯「抽號碼牌」，號碼小的先。
// ---------------------------------------------------------------------------
// 🔹 q.enqueue(a, b, c ...)
// 🔹 q.dequeue()
// 🔸 q.first
// 🔸 q.length
// 🔸 q.isEmpty
// ----------------------------
// 🔹 toString()
// 🔹 q.log()
// 🔸 q.debugInfo
//
class Queue {

    // 🔸 private members
    #elements = Object.create(null);    // pure empty object
    #head = 0;                          // 目前排第一位的碼牌 (already in queue)
    #tail = 0;                          // 下一個可抽的新碼牌 (not in queue yet)
    
    // ⭐ const q = new Queue(a, b, c ...)
    constructor(...elements) {
        this.enqueue(...elements);
    }
    
    // 🔹 q.enqueue(a, b, c ...)
    enqueue(...elements) {
        for (const element of elements) {
            this.#elements[this.#tail] = element;
            this.#tail += 1;
        }
    }
    
    // 🔹 q.dequeue()
    dequeue() {
        if (this.isEmpty) return null;
        const item = this.#elements[this.#head];
        delete this.#elements[this.#head];
        this.#head += 1;
        return item;
    }
    
    // 🔸 q.first
    get first() {
        if (this.isEmpty) return null;
        return this.#elements[this.#head];
    }
    
    // 🔸 q.length
    get length() {
        return this.#tail - this.#head;
    }
    
    // 🔸 q.isEmpty
    get isEmpty() {
        return this.length === 0;
    }

    // 🔹 toString()
    toString() {
        let a = [];
        for(let i = this.#head; i < this.#tail; i++) {
            a.push(this.#elements[i]);
        }
        return `Queue: [${a}]`;
    }

    // -------------
    //   dubugging
    // -------------

    // 🔹 q.log()
    log() {
        console.log(this.toString());
    }

    // 🔸 q.debugInfo
    get debugInfo() {
        return `head #: ${this.#head}, tail #: ${this.#tail}`;
    }
}

module.exports = { Queue };

💈範例：

const { log } = console;
const { Queue } = require('./DataStructure/Queue.js');

const q = new Queue(1, 2, 3);

// ✅ log expressions that never throw
// ---------------------------------------------------------------------------
;[
    // commands        value    Queue        H  T  L
    // ----------------------------------------------------------
    `q`,              //        : [1,2,3]    0, 3, 3
    `q.dequeue()`,    // 1,     : [2,3]      1, 3, 2
    `q.first`,        // 2
    `q.dequeue()`,    // 2,     : [3]        2, 3, 1
    `q.enqueue(4)`,   //        : [3,4]      2, 4, 2
    `q.dequeue()`,    // 3,     : [4]        3, 4, 1
    `q.dequeue()`,    // 4,     : []         4, 4, 0
    `q.dequeue()`,    // null,  : []         4, 4, 0
    `q.isEmpty`,      // true,  

].forEach(x => {
    log('-'.repeat(40));
    log(`${x}`);
    x = eval(x);      // execute command
    if (!(x instanceof Queue)) { log(x); }
    log(q.toString(), q.debugInfo);
});