Queue

Queue คืออะไร

Queue คือ linear data structure ที่ทำงานตามหลักการ "เข้าก่อนออกก่อน" (First In, First Out - FIFO) หมายความว่าข้อมูลชิ้นแรกที่ถูกเพิ่มเข้าไปใน queue จะเป็นข้อมูลชิ้นแรกที่ถูกนำออกจาก queue ด้วย คุณสมบัตินี้ทำให้ queue มีประโยชน์อย่างยิ่งในสถานการณ์ที่ต้องการประมวลผลข้อมูลต่างๆ ตามลำดับที่ได้รับ ไม่ว่าจะเป็นการจัดการงานพิมพ์ การจัดตารางเวลาทำงาน (task scheduling) หรือการค้นหาในกราฟแบบ "ค้นตามความกว้าง" (breadth-first search) เป็นต้น

ประเภท Queue

Linear Queue Queue พื้นฐานที่สุด โดยข้อมูลจะถูกเพิ่ม (enqueue) เข้าไปทางด้านหลัง และลบ (dequeue) ออกจากด้านหน้า

ตัวอย่าง code

#include <iostream>
#define SIZE 5

class Queue {
  int items[SIZE], front, rear;

public:
  Queue() : front(-1), rear(-1) {}

  bool isFull() { return rear == SIZE - 1; }

  bool isEmpty() { return front == -1; }

  void enqueue(int element) {
    if (isFull()) {
      std::cout << "Queue is full" << std::endl;
    } else {
      if (front == -1)
        front = 0;
      items[++rear] = element;
      std::cout << element << " inserted" << std::endl;
    }
  }

  int dequeue() {
    if (isEmpty()) {
      std::cout << "Queue is empty" << std::endl;
      return -1;
    } else {
      int element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } else {
        front++;
      }
      return element;
    }
  }

  void display() {
    if (isEmpty()) {
      std::cout << "Queue is empty" << std::endl;
    } else {
      for (int i = front; i <= rear; i++)
        std::cout << items[i] << " ";
      std::cout << std::endl;
    }
  }
};

int main() {
  Queue q;

  q.enqueue(1);
  q.enqueue(2);
  q.enqueue(3);

  q.display();

  q.dequeue();
  q.display();

  return 0;
}

Circular Queue Queue รูปแบบหนึ่งที่เพิ่มประสิทธิภาพโดยการเชื่อมตำแหน่งท้ายสุดเข้ากับตำแหน่งแรก เป็นการแก้ปัญหา "พื้นที่เหลือทิ้ง" (ที่บางครั้งเกิดขึ้นใน Linear Queue ที่ชี้ไปยังพื้นที่ว่าง) โดยการนำพื้นที่ที่เกิดจากการลบข้อมูลกลับมาใช้ใหม่ได้

ตัวอย่าง code

#include <iostream>
#define SIZE 5

class CircularQueueArray {
  int items[SIZE], front, rear;

public:
  CircularQueueArray() : front(-1), rear(-1) {}

  bool isFull() { return (rear + 1) % SIZE == front; }

  bool isEmpty() { return front == -1; }

  void enqueue(int element) {
    if (isFull()) {
      std::cout << "Queue is full" << std::endl;
    } else {
      if (front == -1)
        front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      std::cout << element << " inserted into queue" << std::endl;
    }
  }

  void dequeue() {
    if (isEmpty()) {
      std::cout << "Queue is empty" << std::endl;
    } else {
      std::cout << items[front] << " removed from queue" << std::endl;
      if (front == rear) {
        front = -1;
        rear = -1; // Queue is empty
      } else {
        front = (front + 1) % SIZE;
      }
    }
  }

  void display() {
    if (isEmpty()) {
      std::cout << "Queue is empty" << std::endl;
      return;
    }
    std::cout << "Queue elements are: ";
    if (rear >= front) {
      for (int i = front; i <= rear; i++)
        std::cout << items[i] << " ";
    } else {
      for (int i = front; i < SIZE; i++)
        std::cout << items[i] << " ";
      for (int i = 0; i <= rear; i++)
        std::cout << items[i] << " ";
    }
    std::cout << std::endl;
  }
};

Priority Queue abstract data type ที่แต่ละข้อมูลจะมีค่าความสำคัญ (priority) กำกับไว้ การลบข้อมูล (dequeue) จะลบข้อมูลที่มีค่าความสำคัญสูงสุดออกไปก่อน

ตัวอย่าง code

#include <iostream>

class Node {
public:
  int data;
  int priority;
  Node *next;

  Node(int d, int p) : data(d), priority(p), next(nullptr) {}
};

class PriorityQueue {
  Node *head;

public:
  PriorityQueue() : head(nullptr) {}

  void enqueue(int d, int p) {
    Node *newNode = new Node(d, p);
    if (head == nullptr || head->priority > p) {
      newNode->next = head;
      head = newNode;
    } else {
      Node *temp = head;
      while (temp->next != nullptr && temp->next->priority <= p) {
        temp = temp->next;
      }
      newNode->next = temp->next;
      temp->next = newNode;
    }
  }

  void dequeue() {
    if (head == nullptr) {
      std::cout << "Queue is empty" << std::endl;
      return;
    }
    Node *temp = head;
    std::cout << temp->data << " dequeued" << std::endl;
    head = head->next;
    delete temp;
  }

  void display() {
    if (head == nullptr) {
      std::cout << "Queue is empty" << std::endl;
      return;
    }
    Node *temp = head;
    while (temp != nullptr) {
      std::cout << temp->data << "(" << temp->priority << ") ";
      temp = temp->next;
    }
    std::cout << std::endl;
  }
};

Double-Ended Queue (Deque) Queue อีกชนิดหนึ่งที่มีความยืดหยุ่น ในการเพิ่ม (insert) หรือลบ (delete) ข้อมูลได้ทั้งจากด้านหน้าและด้านหลัง

ตัวอย่าง code

#include <iostream>
using namespace std;

class Node {
public:
  int value;
  Node *next;
  Node *prev;
  Node(int value) : value(value), next(nullptr), prev(nullptr) {}
};

class Deque {
private:
  Node *front;
  Node *rear;
  int size;

public:
  Deque() : front(nullptr), rear(nullptr), size(0) {}

  // Check if deque is empty
  bool isEmpty() const { return size == 0; }

  // Insert at the front
  void insertFront(int value) {
    Node *newNode = new Node(value);
    if (isEmpty()) {
      front = rear = newNode;
    } else {
      newNode->next = front;
      front->prev = newNode;
      front = newNode;
    }
    size++;
  }

  // Insert at the rear
  void insertRear(int value) {
    Node *newNode = new Node(value);
    if (isEmpty()) {
      front = rear = newNode;
    } else {
      rear->next = newNode;
      newNode->prev = rear;
      rear = newNode;
    }
    size++;
  }

  // Delete from front
  void deleteFront() {
    if (isEmpty()) {
      cout << "Deque is empty" << endl;
      return;
    }
    Node *temp = front;
    front = front->next;
    if (front == nullptr) {
      rear = nullptr;
    } else {
      front->prev = nullptr;
    }
    delete temp;
    size--;
  }

  // Delete from rear
  void deleteRear() {
    if (isEmpty()) {
      cout << "Deque is empty" << endl;
      return;
    }
    Node *temp = rear;
    rear = rear->prev;
    if (rear == nullptr) {
      front = nullptr;
    } else {
      rear->next = nullptr;
    }
    delete temp;
    size--;
  }

  // Get front element
  int getFront() const {
    if (isEmpty()) {
      cout << "Deque is empty" << endl;
      return -1;
    }
    return front->value;
  }

  // Get rear element
  int getRear() const {
    if (isEmpty()) {
      cout << "Deque is empty" << endl;
      return -1;
    }
    return rear->value;
  }

  // Destructor to clean up the linked list
  ~Deque() {
    while (!isEmpty()) {
      deleteFront();
    }
  }
};

int main() {
  Deque dq;

  dq.insertFront(1);
  dq.insertRear(2);
  dq.insertFront(3);
  dq.insertRear(4);

  cout << "Front element: " << dq.getFront() << endl;
  cout << "Rear element: " << dq.getRear() << endl;

  dq.deleteFront();
  dq.deleteRear();

  cout << "Front element after deletion: " << dq.getFront() << endl;
  cout << "Rear element after deletion: " << dq.getRear() << endl;

  return 0;
}

Queue และ STL

C++ Standard Template Library (STL) มี container adapter แบบคิว (queue) รวมอยู่ด้วย โดย std::queue จะทำหน้าที่เป็นโครงสร้างข้อมูลที่ทำงานตามหลัก "เข้าก่อน ออกก่อน" (FIFO) ซึ่งหมายความว่าข้อมูลที่ถูกเพิ่ม (enqueue) เข้าไปก่อน จะถูกนำออก (dequeue) ก่อนเช่นกัน

ในทางปฏิบัติ std::queue จะถูกสร้างขึ้นโดยครอบไว้เหนือ sequential container อื่นๆ ใน STL ซึ่งอาจเป็น std::deque หรือ std::list โดยถ้าเราไม่ได้ระบุ container ชัดเจน ระบบจะใช้ std::deque ในการสร้าง std::queue เป็น default ไว้

คำสั่งสำคัญต่างๆ ของ `std::queue`

push(g) เพิ่มข้อมูล 'g' เข้าไปด้านหลังสุดของ Queue
pop() ลบข้อมูลตัวแรกออกจาก Queue (คำสั่งนี้จะไม่คืนค่าของข้อมูลที่ถูกลบออกไป)
front() คืนค่าแบบอ้างอิง (reference) ไปยังข้อมูลชิ้นแรกใน Queue
back() คืนค่าแบบอ้างอิง (reference) ไปยังข้อมูลชิ้นสุดท้ายใน Queue
empty() ตรวจสอบว่า Queue ว่างอยู่หรือไม่
size() คืนค่าจำนวนข้อมูลทั้งหมดใน Queue

ตัวอย่างการใช้งาน

#include <iostream>
#include <queue>
using namespace std;

int main() {
  queue<int> q;

  // Enqueue elements
  q.push(1);
  q.push(2);
  q.push(3);

  cout << "Front element is: " << q.front() << endl;
  cout << "Back element is: " << q.back() << endl;

  // Dequeue elements
  q.pop();
  cout << "Front element after pop: " << q.front() << endl;

  // Check if the queue is empty
  if (!q.empty()) {
    cout << "Queue is not empty" << endl;
  }

  // Size of the queue
  cout << "Size of queue is: " << q.size() << endl;

  return 0;
}

Use Case กับ Queue

หนึ่งในตัวอย่างการ queue ที่พบได้บ่อยและเป็นประโยชน์ในเชิงการพัฒนา Software ก็คือการจัดการงานพิมพ์ภายใน Queue เครื่องพิมพ์ โดยปกติแล้วเครื่องพิมพ์จะรับงานได้ทีละหนึ่งงาน ดังนั้นหากมีผู้ใช้หลายคนส่งงานพิมพ์พร้อมกัน งานเหล่านี้จะต้องถูกจัดเข้าคิว และดำเนินการตามลำดับที่ได้รับ ซึ่งสอดคล้องกับหลักการ "เข้าก่อน ออกก่อน" (FIFO) ของ Queue พอดี เราจึงสามารถนำ Queue มาประยุกต์ใช้กับ case นี้ได้

ตัวอย่าง Printer Queue Management System

โจทย์ปัญหา

ลองจินตนาการถึงออฟฟิศที่มีเครื่องพิมพ์เพียงเครื่องเดียว แต่มีพนักงานหลายคนที่ต้องการส่งงานพิมพ์ เนื่องจากเครื่องพิมพ์สามารถทำงานได้ครั้งละหนึ่งงานเท่านั้น งานพิมพ์ที่ส่งเข้ามาเพิ่มเติมจึงต้องเข้า Queue รอดำเนินการตามลำดับเวลา

การแก้ปัญหาโดยใช้ Queue

เราสามารถจัดการงานพิมพ์ได้อย่างมีประสิทธิภาพด้วยการใช้โครงสร้างข้อมูลแบบ Queue เมื่อมีงานพิมพ์เข้ามา งานนั้นจะถูกเพิ่ม (enqueue) เข้าไปยังท้ายสุดของ Queue เครื่องพิมพ์จะเริ่มทำงานพิมพ์จากด้านหน้าสุดของ Queue ซึ่งเป็นการรับประกันว่างานต่างๆจะถูกพิมพ์ออกมาตามลำดับที่ได้รับ เมื่อมีการพิมพ์งานใดเสร็จสิ้น งานนั้นจะถูกนำออก (dequeue) จากด้านหน้าของ Queue และเครื่องพิมพ์ก็จะรับงานถัดไปใน Queue มาดำเนินการต่อได้นั่นเอง

#include <iostream>
#include <queue>
#include <string>

class PrintJob {
public:
  std::string documentName;
  int numberOfPages;

  PrintJob(std::string docName, int pages)
      : documentName(docName), numberOfPages(pages) {}
};

class PrinterQueue {
private:
  std::queue<PrintJob> queue;

public:
  void addJob(const PrintJob &job) {
    queue.push(job);
    std::cout << "Added to queue: " << job.documentName << " ("
              << job.numberOfPages << " pages)" << std::endl;
  }

  void processJobs() {
    while (!queue.empty()) {
      PrintJob currentJob = queue.front();
      std::cout << "Printing: " << currentJob.documentName << " ("
                << currentJob.numberOfPages << " pages)" << std::endl;
      // Simulate printing delay
      queue.pop(); // Remove the job from the queue after printing
    }
    std::cout << "All print jobs completed." << std::endl;
  }
};

int main() {
  PrinterQueue printer;

  printer.addJob(PrintJob("Document1.pdf", 10));
  printer.addJob(PrintJob("Document2.pdf", 5));
  printer.addJob(PrintJob("Document3.pdf", 12));

  printer.processJobs(); // Start processing print jobs

  return 0;
}

ตัวอย่างนี้ แสดงให้เห็นว่าเราสามารถใช้ queue ในการจัดการงานพิมพ์ได้อย่างไร โดยแต่ละงานพิมพ์จะถูกจำลองด้วย class PrintJob และมีการจัดการงานทั้งหมดด้วย std::queue วิธีการนี้ทำให้มั่นใจได้ว่างานพิมพ์จะถูกดำเนินการตามลำดับที่ได้รับ ซึ่งเป็นการแสดงให้เห็นลักษณะเด่นแบบ "เข้าก่อน ออกก่อน" (FIFO) ของ Queue ออกมานั่นเอง

Use case อื่นๆ

Job Scheduling Queue ****มีบทบาทสำคัญในระบบปฏิบัติการ เพื่อจัดลำดับงาน (process) ที่ต้องใช้ CPU โดยงานต่างๆ จะถูกบรรจุอยู่ใน queue ตามลำดับเวลาที่มาถึง ทำให้มั่นใจได้ว่าแต่ละงานสามารถทำออกมาอย่างเป็นระเบียบได้
Asynchronous Data ในการเขียนโปรแกรมเชิงเหตุการณ์ (event-driven programming) queue จะช่วยจัดการ event ต่างๆ, ข้อความ หรือชุดข้อมูล ที่เกิดขึ้นในเวลาที่ไม่ตรงกันได้ โดย queue จะรับรองว่าการประมวลผลจะเกิดขึ้นตามลำดับที่ได้รับเข้ามาได้
Load Balancing ในระบบกระจายงานขนาดใหญ่ (Distributed Systems) Queue มีส่วนช่วยกระจายงานต่างๆ ไปยังทรัพยากรด้านการคำนวณอย่างทั่วถึง ทำให้มั่นใจได้ว่าไม่มีทรัพยากรหน่วยใดต้องทำงานหนักเกินไป ในขณะที่ทรัพยากรอื่นๆ ว่างอยู่ได้
Breadth-First Search - BFS Queue ****จะใช้ในการสำรวจข้อมูลใน tree, graph แบบทีละชั้นๆ (level by level) เพื่อให้แน่ใจว่า node ทั้งหมดที่ความลึกแต่ละชั้น จะถูกประมวลผลก่อนหน้าที่จะย้ายไปยังความลึกชั้นถัดไปได้
การทำ Caching ระบบ LRU caching (Least Recently Used caching) สามารถนำไปใช้ได้ด้วยการอาศัย queue เพื่อติดตามว่าข้อมูลส่วนไหนเคยถูกใช้ล่าสุดได้ โดยข้อมูลที่ไม่ได้ถูกใช้เป็นระยะเวลานานที่สุด จะถูกจัดให้ถูกนำออกจากระบบก่อนได้จากการใช้ประโยชน์ของ Queue
Concurrency Control ในสภาวะที่มีการทำงานแบบ multi-threaded หรือแบบขนานกันไป Queue จะช่วยจัดการงานต่างๆ โดยรับรองว่าทรัพยากรจะถูกใช้ได้อย่างมีประสิทธิภาพและปลอดภัยโดยปราศจากข้อขัดแย้งใดๆในระบบได้

Queue ผ่าน LeetCode

Problem 933 - Number of Recent Calls

https://leetcode.com/problems/number-of-recent-calls/description/

โจทยคือ ต้อง implement class สำหรับนับจำนวนคำขอ (request) ที่เกิดขึ้นล่าสุดภายในกรอบเวลาที่กำหนด (3000 miliseconds) โดยใช้ queue)ในการติดตามเวลา (timestamp) ของแต่ละคำขอที่ถูกส่งเข้ามา

ในการแก้โจทย์ Number of Recent Calls โดยใช้ Queue เราต้องสร้างคลาส (class) ที่สามารถติดตามจำนวนการร้องขอ (request) ที่เกิดขึ้นภายในช่วงเวลาหนึ่ง เช่นภายใน 3,000 มิลลิวินาที เราจะใช้คิวเก็บค่าเวลา (timestamp) ของแต่ละครั้งที่มีการเรียกใช้ฟังก์ชัน ping เมื่อ ping ถูกเรียกด้วยเวลาใหม่ล่าสุด (t) เราจะเพิ่ม t เข้าไปในคิว แล้วจึงลบคำขอทั้งหมดที่มีอายุมากกว่า 3,000 มิลลิวินาทีออกไปจากคิว เมื่อทำเช่นนี้แล้ว ขนาดของคิวที่เหลือจะบอกให้เราทราบได้ว่ามีคำร้องขอที่เกิดขึ้นภายในระยะเวลาล่าสุดกี่รายการ

#include <iostream>
#include <queue>
using namespace std;

class RecentCounter {
private:
  queue<int> calls;

public:
  RecentCounter() {}

  int ping(int t) {
    // Add the new call timestamp to the queue
    calls.push(t);

    // Remove calls that are outside the 3000ms window from the front of the
    // queue
    while (!calls.empty() && calls.front() < t - 3000) {
      calls.pop();
    }

    // The size of the queue now represents the number of recent calls
    return calls.size();
  }
};

int main() {
  RecentCounter *obj = new RecentCounter();
  cout << obj->ping(1) << endl;    // Ping at t = 1
  cout << obj->ping(100) << endl;  // Ping at t = 100
  cout << obj->ping(3001) << endl; // Ping at t = 3001
  cout << obj->ping(3002) << endl; // Ping at t = 3002
  delete obj;                                // Clean up
  return 0;
}

โปรแกรมนี้จะสร้างคลาส (class) ที่ชื่อว่า RecentCounter ซึ่งจะมีเมธอด (method) หนึ่งชื่อว่า ping คอยรับค่าเวลา (timestamp) t เป็นค่าป้อนเข้า (input) และส่งคืนจำนวนการเรียกฟังก์ชัน ping ที่เกิดขึ้นภายใน 3,000 มิลลิวินาทีก่อนหน้า รวมถึงการเรียกในครั้งปัจจุบันด้วย ในส่วนของฟังก์ชันหลัก (main function) เราจะเห็นตัวอย่างการใช้คลาส RecentCounter โดยมีการเรียก ping หลายๆ ครั้ง และมีการพิมพ์ผลลัพธ์ของการเรียกแต่ละครั้งแสดงออกมา

Queue คืออะไร​

ประเภท Queue​

Queue และ STL​

คำสั่งสำคัญต่างๆ ของ std::queue​

Use Case กับ Queue​

ตัวอย่าง Printer Queue Management System​

Use case อื่นๆ​

Queue ผ่าน LeetCode​

Problem 933 - Number of Recent Calls​

Queue คืออะไร

ประเภท Queue

Queue และ STL

คำสั่งสำคัญต่างๆ ของ `std::queue`

Use Case กับ Queue

ตัวอย่าง Printer Queue Management System

Use case อื่นๆ

Queue ผ่าน LeetCode

Problem 933 - Number of Recent Calls