Queue

Queue

First In, First Out, 선입선출 구조를 가진 자료구조

Implementation

Linked List 기반으로 Queue 구현

#include<iostream>

using namespace std;

struct Node {
    int data;
    Node* next;

    explicit Node(int value) : data(value), next(nullptr){}
};

class Queue {
private:
    Node* frontNode;
    Node* rearNode;
    int size;

public:
    explicit Queue() : frontNode(nullptr), rearNode(nullptr), size(0){}

    // 큐에 요소 추가
    void enqueue(int value) {
        Node* newNode = new Node(value);
        if(empty()) {
            frontNode = rearNode = newNode;
        } else {
            rearNode->next = newNode;
            rearNode = newNode;
        }
        size++;
    }

    // 큐의 앞에서 요소 제거
    void dequeue() {
        if(empty()) {
            return;
        }
        Node* temp = frontNode;
        frontNode = frontNode->next;
        delete temp;
        size--;
        if(frontNode == nullptr) {
            rearNode = nullptr;
        }
    }

    // 큐의 앞 요소 반환
    int front() const {
        if(empty()) {
            return -1;
        }
        return frontNode->data;
    }

    // 큐가 비어있는지 확인
    bool empty() const {
        return frontNode == nullptr;
    }

    // 큐의 크기 반환
    int getSize() const {
        return size;
    }

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

int main() {
    Queue queue;

    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    cout<<"Front element: "<<queue.front()<<endl;
    queue.dequeue();
    cout<<"Front element: "<<queue.front()<<endl;
    cout<<"Queue size: "<<queue.getSize()<<endl;

    if(queue.empty()) {
        cout<<"Queue is empty"<<endl;
    }else {
        cout<<"Queue is not empty"<<endl;
    }

    return EXIT_SUCCESS;
}

Output

Efficiency

Linked List 기반 효율표

Efficiency Summary

데이터를 순서대로 처리해야 할때 적합, FIFO 구조
넓이 우선 탐색(BFS) 등에서 사용될 때 적합 (경로 탐색 문제, 네트워크 연결 분석, 최단 거리 탐색과 같은 알고리즘에서 Queue를 사용)
스트림 데이터 처리, 멀티스레드 같이 데이터를 순차적으로 처리하는 구조일때 적합

임의의 인덱스에 빠르게 접근할때 부적합
중간에 데이터를 삽입/삭제해야 하는 경우 부적합
데이터가 정렬해야하는 경우 부적합
양방향 접근이 필요한 경우 부적합, deque 자료구조가 있음

STL

std::queue

일반적인 선입선출 방식의 큐 제공
기본적으로 std::deque를 내부 컨테이너로 사용