這是什麼？

先來看看 GeeksforGeeks 的定義：

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

如果 Stack，Queue 的出現也是模擬真實世界的行為，在任何序列中，維持先進先出、後進後出的行為，最典型的就是排隊行為（如同 Queue 的中文解釋），排隊結帳、排隊進出停車場等等。

因為是序列，可以用 Array 與 Linked List 實作，實作的功能要包含幾點：

• 判斷 Queue 內是否為空。
• 將項目放入 Queue（Enqueue，特定名詞）。
• 移除 Queue 內最上層項目（Dequeue，特定名詞）。
• 定義 Queue 的容量上限。

用 Array 實作

來源

JS

class Queue {
  /**
   * @param {number} capacity
   */
  constructor(capacity) {
    this.capacity = capacity;
    this.front = 0;
    this.size = 0;

    this.rear = capacity - 1;
    this.arr = new Array(capacity);
  }
}

/**
 * @param {Queue} queue
 */
const isFull = (queue) => {
  return (queue.size === queue.capacity);
};

/**
 * @param {Queue} queue
 */
const isEmpty = (queue) => {
  return (queue.size === 0);
};

/**
 * @param {Queue} queue
 * @param {number} item
 */
const enqueue = (queue, item) => {
  if (isFull(queue)) {
    return;
  }

  queue.rear = (queue.rear + 1) % queue.capacity;
  queue.arr[queue.rear] = item;
  queue.size = queue.size + 1;

  console.log(item + " enqueued to queue");
};

/**
 * @param {Queue} queue
 */
const dequeue = (queue) => {
  if (isEmpty(queue)) {
    return Number.MIN_VALUE;
  }

  let item = queue.arr[queue.front];
  queue.front = (queue.front + 1) % queue.capacity;
  queue.size = queue.size - 1;
  return item;
};

/**
 * @param {Queue} queue
 */
const front = (queue) => {
  if (isEmpty(queue)) {
    return Number.MIN_VALUE;
  }

  return queue.arr[queue.front];
};

/**
 * @param {Queue} queue
 */
const rear = (queue) => {
  if (isEmpty(queue)) {
    return Number.MIN_VALUE;
  }

  return queue.arr[queue.rear];
};

let queue = new Queue(1000);

enqueue(queue, 10);
enqueue(queue, 22);
enqueue(queue, 33);
enqueue(queue, 44);

console.log(dequeue(queue) + " dequeued from queue\n");

console.log("Front item is: " + front(queue));
console.log("Rear item is: " + rear(queue));

Java

public class Queue {
    public class QueueNode {
        int key;
        QueueNode next;

        public QueueNode(int key) {
            this.key = key;
            this.next = null;
        }
    }

    QueueNode front, rear;

    public Queue() {
        this.front = null;
        this.rear = null;
    }

    void enqueue(int key) {
        QueueNode temp = new QueueNode(key);

        if (this.rear == null) {
            this.front = temp;
            this.rear = temp;
            return;
        }

        this.rear.next = temp;
        this.rear = temp;
    }

    int dequeue() {
        if (this.front == null) {
            return Integer.MIN_VALUE;
        }

        QueueNode temp = this.front;
        this.front = this.front.next;

        if (this.front == null) {
            this.rear = null;
        }

        return temp.key;
    }

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.enqueue(11);
        queue.enqueue(22);
        queue.enqueue(33);
        System.out.println(queue.dequeue() + " dequeued from queue");
        System.out.println(queue.dequeue() + " dequeued from queue");
        System.out.println("Queue Front: " + queue.front.key);
        System.out.println("Queue Rear: " + queue.rear.key);

        queue.enqueue(44);
        queue.enqueue(55);
        queue.enqueue(66);
        System.out.println(queue.dequeue() + " dequeued from queue");
        System.out.println("Queue Front: " + queue.front.key);
        System.out.println("Queue Rear: " + queue.rear.key);
    }
}

C

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct Queue
{
    int front, rear, size;
    unsigned int capacity;
    int *arr;
};

struct Queue *create_queue(unsigned int capacity)
{
    struct Queue *queue = (struct Queue *)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;

    queue->rear = capacity - 1;
    queue->arr = (int *)malloc(queue->capacity * sizeof(int));

    return queue;
}

int is_full(struct Queue *queue)
{
    return (queue->size == queue->capacity);
}

int is_empty(struct Queue *queue)
{
    return (queue->size == 0);
}

void enqueue(struct Queue *queue, int item)
{
    if (is_full(queue))
    {
        return;
    }

    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->arr[queue->rear] = item;
    queue->size = queue->size + 1;

    printf("%d enqueued to queue\n", item);
}

int dequeue(struct Queue *queue)
{
    if (is_empty(queue))
    {
        return INT_MIN;
    }

    int item = queue->arr[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

int front(struct Queue *queue)
{
    if (is_empty(queue))
    {
        return INT_MIN;
    }

    return queue->arr[queue->front];
}

int rear(struct Queue *queue)
{
    if (is_empty(queue))
    {
        return INT_MIN;
    }

    return queue->arr[queue->rear];
}

int main()
{
    struct Queue *queue = create_queue(1000);

    enqueue(queue, 10);
    enqueue(queue, 22);
    enqueue(queue, 33);
    enqueue(queue, 44);

    printf("%d dequeued from queue\n\n", dequeue(queue));

    printf("Front item is %d\n", front(queue));
    printf("Rear item is %d\n", rear(queue));

    return 0;
}

用 Linked List 實作

來源

JS

class QueueNode {
  /**
   * @param {number} key
   * @param {QueueNode} next
   */
  constructor(key) {
    this.key = key;
    this.next = null;
  }
}

class Queue {
  /**
   * @param {QueueNode} front
   * @param {QueueNode} rear
   */
  constructor() {
    this.front = null;
    this.rear = null;
  }
}

/**
 * @param {Queue} queue
 * @param {number} key
 */
const enqueue = (queue, key) => {
  let temp = new QueueNode(key);

  if (queue.rear === null) {
    queue.front = temp;
    queue.rear = temp;
    return;
  }

  queue.rear.next = temp;
  queue.rear = temp;
};

/**
 * @param {Queue} queue
 */
const dequeue = (queue) => {
  if (queue.front === null) {
    return Number.MIN_VALUE;
  }

  let temp = queue.front;

  queue.front = queue.front.next;

  if (queue.front === null) {
    queue.rear = null;
  }

  return temp.key;
};

let queue = new Queue();
console.log("queue", queue)

enqueue(queue, 11);
enqueue(queue, 22);
enqueue(queue, 33);
enqueue(queue, 44);
console.log(dequeue(queue) + " dequeued from queue");
console.log("Front item is: " + queue.front.key);
console.log("Rear item is: " + queue.rear.key);
enqueue(queue, 55);
enqueue(queue, 66);
console.log(dequeue(queue) + " dequeued from queue");
console.log("Front item is: " + queue.front.key);
console.log("Rear item is: " + queue.rear.key);

Java

public class QueueLinkedList {
    public class QueueNode {
        int key;
        QueueNode next;

        public QueueNode(int key) {
            this.key = key;
            this.next = null;
        }
    }

    QueueNode front, rear;

    public QueueLinkedList() {
        this.front = null;
        this.rear = null;
    }

    void enqueue(int key) {
        QueueNode temp = new QueueNode(key);

        if (this.rear = null) {
            this.front = temp;
            this.rear = temp;
            return;
        }

        this.rear.next = temp;
        this.rear = temp;
    }

    int dequeue() {
        if (this.front == null) {
            return Integer.MIN_VALUE;
        }

        QueueNode temp = this.front;
        this.front = this.front.next;

        if (this.front == null) {
            this.rear = null;
        }

        return temp;
    }

    public static void main(String[] args) {
        QueueLinkedList queue = new QueueLinkedList();
        queue.enqueue(11);
        queue.enqueue(22);
        queue.enqueue(33);
        System.out.println(queue.dequeue() + " dequeued from queue");
        System.out.println(queue.dequeue() + " dequeued from queue");
        queue.enqueue(44);
        queue.enqueue(55);
        queue.enqueue(66);
        System.out.println(queue.dequeue() + " dequeued from queue");

        System.out.println("Queue Front: " + queue.front.key);
        System.out.println("Queue Rear: " + queue.rear.key);
    }
}

C

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct QueueNode
{
    int key;
    struct QueueNode *next;
};

struct Queue
{
    struct QueueNode *front, *rear;
};

struct QueueNode *new_node(int key)
{
    struct QueueNode *temp = (struct QueueNode *)malloc(sizeof(struct QueueNode));
    temp->key = key;
    temp->next = NULL;
    return temp;
}

struct Queue *create_queue()
{
    struct Queue *queue = (struct Queue *)malloc(sizeof(struct Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

void enqueue(struct Queue *queue, int key)
{
    struct QueueNode *temp = new_node(key);

    if (queue->rear == NULL)
    {
        queue->front = temp;
        queue->rear = temp;
        return;
    }

    queue->rear->next = temp;
    queue->rear = temp;
}

int dequeue(struct Queue *queue)
{
    if (queue->front == NULL)
    {
        return INT_MIN;
    }

    struct QueueNode *temp = queue->front;

    queue->front = queue->front->next;

    if (queue->front == NULL)
    {
        queue->rear = NULL;
    }

    return temp->key;
    free(temp);
}

int main()
{
    struct Queue *queue = create_queue();
    enqueue(queue, 11);
    enqueue(queue, 22);
    printf("%d dequeued from queue\n", dequeue(queue));
    enqueue(queue, 33);
    enqueue(queue, 44);
    enqueue(queue, 55);
    printf("%d dequeued from queue\n", dequeue(queue));

    printf("Front item is %d\n", queue->front->key);
    printf("Rear item is %d\n", queue->rear->key);
}

刷題：933. Number of Recent Calls

連結

題目

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

• RecentCounter() Initializes the counter with zero recent requests.
• int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Constraints:

1 <= t <= 104
Each test case will call ping with strictly increasing values of t.
At most 104 calls will be made to ping.

思考

這題拐了許多個彎，才理解他在詢問什麼。
模擬情況是，有個物件負責收集過往接收到 Request 時的時間，接著回傳在三秒內有多少筆 Request。

Example 的表達是：

# 在 1ms 秒接受到 request
# 三秒內允許的區間是 [1 -3000, 1] = [-2900, 1]
# 區間是 -2900 ms ~ 1 ms 的 request 都允許。
# 目前只有 [1] 一筆，回傳 1。

發送來的時間是遞增，最多 10000 筆 Request。
想通後就是一題標準的 Queue 的應用，每次接受到 Request 後計算區間，接著判斷 Queue 內要踢掉哪些元素。

解題

JS

// 用 Queue 模擬
class RecentCounter {
  constructor() {
    this.queue = [];
  }

  isEmpty() {
    return this.queue.length === 0;
  }

  size() {
    return this.queue.length;
  }

  /**
   * @param {number} t
   */
  enqueue(t) {
    this.queue.push(t);
  }

  dequeue() {
    this.queue = this.queue.slice(1);
  }

  peek() {
    return this.queue[0];
  }

  /**
   * @param {number} t
   */
  ping(t) {
    if (this.isEmpty()) {
      this.enqueue(t);
      return 1;
    } else {
      const min = t - 3000;

      while (!this.isEmpty() && this.peek() < min) {
        this.dequeue();
      }

      this.enqueue(t);
    }

    return this.size();
  }
}

// Leet Code 較佳解
var RecentCounter = function() {
  this.queue = [];
};

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    this.queue.push(t);

    while (this.queue[0] < t - 3000) {
      this.queue.shift();
    }

    return this.queue.length;
};

Java

// 使用內建 Queue & Linked List
class RecentCounter {
    Queue<Integer> queue;

    public RecentCounter() {
        queue = new LinkedList<Integer>();
    }

    public int ping(int t) {
        if (queue.isEmpty()) {
            queue.offer(t);
            return 1;
        } else {
            int min = t - 3000;

            while (!queue.isEmpty() && queue.peek() < min) {
                queue.poll();
            }

            queue.offer(t);
        }

        return queue.size();
    }
}

C

#define MAX 10000

typedef struct
{
    int front, rear, size;
    int capacity;
    long int ping_time[MAX];
} RecentCounter;

struct RecentCounter *recentCounterCreate()
{
    RecentCounter *rc = malloc(sizeof(RecentCounter));
    rc->capacity = MAX;
    rc->front = 0;
    rc->size = 0;

    rc->rear = MAX - 1;
    return rc;
}

int recentCounterPing(RecentCounter *obj, int t)
{
    if (obj->size == 0)
    {
        obj->rear = (obj->rear + 1) % obj->capacity;
        obj->ping_time[obj->rear] = t;
        obj->size = obj->size + 1;
        return 1;
    }
    else
    {
        int min = t - 3000;

        while ((obj->size != 0) && (obj->ping_time[obj->front] < min))
        {
            obj->front = (obj->front + 1) % obj->capacity;
            obj->size = obj->size - 1;
        }

        obj->rear = (obj->rear + 1) % obj->capacity;
        obj->ping_time[obj->rear] = t;
        obj->size = obj->size + 1;
    }

    return obj->size;
}

void recentCounterFree(RecentCounter *obj)
{
    free(obj);
}

看法

一開始打算用 Queue 的概念實作，過程中發現三件事：

• JS 的 Prototype Chain 的概念不太熟，只會用語法糖 class。
• Java 內建 class Queue 的內建函示命名不太習慣，用的時候查一下功能。
• C 如同昨天，要小心控制陣列內的元素如何進出，同時加深這方面的操作。

倒是每次提交後就可以看到不少神人開發出不同的寫法，對題目越熟悉的情況下，能夠精簡不必要的流程，消耗時間可以更少。

結論

比起 Stack，Queue 在程式世界的實用能找到的案例不多（小弟畢竟不太熟悉），開始期待之後 BFS & DFS 會如何運用 Stack & Queue。