佇列(Queue)

介紹

佇列式資料結構的一種，類似堆疊，但佇列是在頭尾兩端最新增和刪除，數據就像在排隊，在隊伍中最晚到的人排在最後面，先到的人則優先處理(如下圖所示)。

佇列的幾個重點:

• 先進先出的原理，稱為 First In First Out 縮寫為 FIFO
• 元素沒有index
• 從後面加入，從前面移除
• Enqueue指的是新增東西至queue，Dequeue指的是從queue移除東西

(圖片來自於Queues)

實作Queue

JS Array實作

我們可以利用Array的方法模擬Queue，利用push模擬新客人來排隊，利用shift模擬最前面的客人已處理完成離開了。

let queue = [];
queue.push(68);
queue.push(50);
queue.push(92);
queue.push(29);
queue.push(57);
queue.push(88);

queue.shift();

物件導向實作

初始化節點以及queue

Node節點有值以及可以知道他的下一個節點是誰

Queue 我們能知道他頭尾的節點以及長度為何

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
 }

入隊enqueue

將新的值加到尾端

(圖片來自於visualgo)

1. 新增新節點
2. 如果頭為空，則將頭尾指向新節點
3. 否則的話，舊尾端的下一個為新節點，再把新尾端指向新節點
4. Queue長度加一

enqueue(value) {
    let newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
}

出隊dequeue

將最前端的值移出

(圖片來自於visualgo)

1. 如果head為空則回傳null
2. 如果queue長度為一則將head移除並回傳，並將頭尾及長度設為空
3. 非上述兩項，代表queue長度大於一，則將head指向head的下一個，並將原先的head移出回傳，queue長度減一

dequeue() {
    if (this.head === null) {
        return null;
    } else if (this.length === 1) {
        let temp = this.head;
        this.head = null;
        this.tail = null;
        this.length = 0;
        return temp;
    } else {
        let temp = this.head;
        this.head = this.head.next;
        this.length--;
        return temp;
    }
}

返回第一個

返回第一個的值，可以把它想像成最早排隊的

(圖片來自於visualgo)

1. 如果head存在則回傳
2. 否則回傳null

getHead() {
    if (this.head === null) {
        return null;
    } else {
        return this.head.value;
    }
}

完整程式碼

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    enqueue(value) {
        let newNode = new Node(value);
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
    }

    dequeue() {
        if (this.head === null) {
            return null;
        } else if (this.length === 1) {
            let temp = this.head;
            this.head = null;
            this.tail = null;
            this.length = 0;
            return temp;
        } else {
            let temp = this.head;
            this.head = this.head.next;
            this.length--;
            return temp;
        }
    }

    getHead() {
        if (this.head === null) {
            return null;
        } else {
            return this.head.value;
        }
    }

    printAll() {
        let current = this.head;
        while (current) {
            console.log(current.value);
            current = current.next;
        }
    }
}

let myQueue = new Queue();

myQueue.enqueue(68);
myQueue.enqueue(50);
myQueue.enqueue(92);
myQueue.enqueue(29);
myQueue.enqueue(57);
myQueue.enqueue(88);

myQueue.dequeue();
myQueue.getHead(); // 50   

myQueue.printAll(); // 50, 92, 29, 57, 88

複雜度

時間複雜度

Action動作	平均	最壞
訪問(Access)	$O(n)$	$O(n)$
搜尋(Search)	$O(n)$	$O(n)$
插入(Insertion)	$O(1)$	$O(1)$
刪除(Deletion)	$O(1)$	$O(1)$

空間複雜度

$O(n)$

實戰

232. Implement Queue using Stacks

題目說明

僅使用兩個堆疊實現先進先出 (FIFO) 佇列。實現的佇列應該支持普通佇列的所有功能（push、peek、pop和empty）。

Code

1. push(x)- 將一個元素推x到佇列的後面。
2. pop()- 從佇列的前面移除並返回元素。它通過首先將所有元素從轉移queue到queue2，從queue2彈出元素，然後將所有元素轉移回queue。
3. peek()- 返回佇列前面的元素而不刪除它。它首先將所有元素從轉移queue到queue2，檢索最後一個元素queue2，然後將所有元素轉移回queue。
4. empty()- 如果佇列為空則返回，false否則返回。

var MyQueue = function() {
    this.queue = []
    this.queue2 = []
};

/** 
 * Pushes element x to the back of the queue.
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.queue.push(x)
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    while(this.queue.length !== 0){
		this.queue2.push(this.queue.pop())
	}

	var pop = this.queue2.pop()

	while(this.queue2.length !== 0){
		this.queue.push(this.queue2.pop())
	}

	return pop
};

/**
 * Returns the element at the front of the queue.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    while(this.queue.length !== 0){
        this.queue2.push(this.queue.pop())
    }

    var peek = this.queue2[this.queue2.length - 1]

    while(this.queue2.length !== 0){
        this.queue.push(this.queue2.pop())
    }
    return peek
};

/**
 * Returns true if the queue is empty, false otherwise.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.queue == 0
};

/** 
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

[name=@joe94113] [time=Tue, Feb 7, 2023 10:00 PM] [color=#907bf7]