# Queue

[data structure](/web/appendix/data.md) ⟩ Queue

{% tabs %}
{% tab title="👥 相關" %}

* [Stack](/web/appendix/data/stack.md)
  {% endtab %}

{% tab title="⬇️ 應用" %}

* [WaitingList](/web/appendix/data/waitinglist.md) - a Stack or a Queue.
  {% endtab %}

{% tab title="📗 參考" %}

* [ ] Advanced Swift (2017.11) ⟩ Ch. 3, Queue: A Custom Collection
* [ ] Data Structures and Algorithms in Swift ⟩ Ch. 8, Queues
* [ ] Scalar ⟩ [JavaScript Queue](https://www.scaler.com/topics/javascript-queue/)
* [ ] JavaScript Tutorial ⟩ [JavaScript Queue](https://www.javascripttutorial.net/javascript-queue/)  
  {% endtab %}
  {% endtabs %}

## implementations

{% tabs %}
{% tab title="JS" %}

* replit ⟩ WaitingList ⟩ [Queue](https://replit.com/@pegasusroe/WaitingList#DataStructure/Queue.js)  

```javascript
// ⭐ 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 };
```

💈範例：

```javascript
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());
    });
}
```

📃 結果：

```javascript
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)
```

{% endtab %}

{% tab title="Swift" %}

* replit ⟩ [Queue (swift)](https://replit.com/@pegasusroe/Queue#Queue.swift/Queue.swift)&#x20;

```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)](https://replit.com/@pegasusroe/Queue#Queue.swift/QueueProtocol.swift)

```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.
  }
}
```

{% endtab %}
{% endtabs %}

## archive code

{% tabs %}
{% tab title="JS" %}

* replit ⟩ [Queue (using object)](https://replit.com/@pegasusroe/Queue-using-object#DataStructure/Queue.js)&#x20;
* archived：2022.12.29

```javascript
// ⭐ 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 };
```

💈範例：

```javascript
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);
});
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lochiwei.gitbook.io/web/appendix/data/queue.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.