📦Queue
🚧 under construction
data structure ⟩ Queue
implementations
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)
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
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);
});
Last updated