Queues

Queues are containers of objects based on arrays that follow a First-In-First-Out (FIFO) order, meaning that the least recently added item is removed first. Queues are helpful in cases where the FIFO order of data needs to be maintained, such as for caching and handling real-time system interruptions. A real-life example of a queue data structure is a line at a ticket counter or amusement park ride, where the people at the front of the line are the first to be served.

Implementation of queues

Queues can be implemented using various data structures, including:

• Arrays: these are are sequential collections of elements stored in contiguous memory locations and are easy to implement, but they have a fixed size and cannot be altered once they are created.
• Linked lists: These are collections of elements linked together using pointers and are more flexible than arrays, but they are more complex to implement and require extra memory to store pointers.
• Dynamic arrays: These are arrays can automatically resize themselves when required and combine the simplicity of arrays with the flexibility of linked lists, but they are generally slower than other data structures.
• Heaps: They are complete binary trees where the parent node is either greater than or equal to (in the case of a max heap) or less than or equal to (in the case of a min heap) its children and are more complex to implement, but they can be more efficient for certain operations, such as finding the maximum or minimum element in the queue.

큐(Queue)는 배열을 기반으로 한 객체 컨테이너로, 먼저 추가된 항목이 먼저 제거되는 First-In-First-Out (FIFO) 순서를 따르는데, 이는 가장 최근에 추가된 항목이 먼저 제거되는 것을 의미합니다. 큐는 데이터의 FIFO 순서를 유지해야 하는 경우에 유용하며, 캐싱 및 실시간 시스템 인터럽션 처리와 같은 상황에서 사용됩니다. 큐 데이터 구조의 현실적인 예는 티켓 카운터나 놀이공원 놀이기구 앞의 줄입니다. 여기서 줄 맨 앞에 있는 사람들이 가장 먼저 서비스를 받습니다.

큐의 구현 큐는 다양한 데이터 구조를 사용하여 구현할 수 있으며, 이에는 다음과 같은 것들이 포함됩니다:

• 배열(Arrays): 연속적인 메모리 위치에 저장된 요소들의 순차적인 모음으로, 구현이 간단하지만 크기가 고정되어 생성 후에는 변경할 수 없습니다.
• 연결 리스트(Linked Lists): 포인터를 사용하여 연결된 요소들의 모음으로, 배열보다 유연하지만 구현이 더 복잡하며 포인터를 저장하기 위한 추가 메모리가 필요합니다.
• 동적 배열(Dynamic Arrays): 필요한 경우 자동으로 크기를 조절할 수 있는 배열로, 배열의 간결성과 연결 리스트의 유연성을 결합하지만 다른 데이터 구조에 비해 일반적으로 느릴 수 있습니다.
• 힙(Heaps): 부모 노드가 자식 노드보다 크거나 같은 경우 (최대 힙의 경우) 또는 부모 노드가 자식 노드보다 작거나 같은 경우 (최소 힙의 경우) 완전 이진 트리인 힙으로, 구현이 더 복잡하지만 큐에서 최대 또는 최소 요소를 찾는 것과 같은 특정 작업에서 효율적일 수 있습니다.

Implement Queue using Linked Lists

#include <iostream>

class Queue {
private:
    struct Node {
        int data;
        Node* next;
        Node(int value) : data(value), next(nullptr) {}
    };

    Node* frontPtr;
    Node* rearPtr;

public:
    Queue() : frontPtr(nullptr), rearPtr(nullptr) {}

    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }

    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            frontPtr = newNode;
            rearPtr = newNode;
        }
        else {
            rearPtr->next = newNode;
            rearPtr = newNode;
        }
    }

    void dequeue() {
        if (!isEmpty()) {
            Node* temp = frontPtr;
            frontPtr = frontPtr->next;
            delete temp;
        }
    }

    int front() const {
        if (!isEmpty()) {
            return frontPtr->data;
        }
        else {
            throw std::runtime_error("Queue is empty");
        }
    }

    bool isEmpty() const {
        return frontPtr == nullptr;
    }
};