---
tags: 資料結構, LeetCode
disqus: HackMD
---

# 佇列(Queue)

:::spoiler 文章目錄
[toc]
:::

## 介紹

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

佇列的幾個重點:

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

(圖片來自於[Queues](https://devdojo.com/algonoob/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](https://visualgo.net/zh/list))

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](https://visualgo.net/zh/list))

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](https://visualgo.net/zh/list))

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](https://leetcode.com/problems/implement-queue-using-stacks)

### 題目說明

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


### Code

1. `push(x)`- 將一個元素推`x`到佇列的後面。
1. `pop()`- 從佇列的前面移除並返回元素。它通過首先將所有元素從轉移`queue`到`queue2`，從`queue2`彈出元素，然後將所有元素轉移回`queue`。
1. `peek()`- 返回佇列前面的元素而不刪除它。它首先將所有元素從轉移`queue`到`queue2`，檢索最後一個元素`queue2`，然後將所有元素轉移回`queue`。
1. `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]