자료구조 — 스택(Stack)과 큐(Queue)

개요 — 스택과 큐가 왜 게임 개발자에게 중요한가

스택(Stack)과 큐(Queue)는 프로그래밍에서 가장 자주 만나는 추상 자료구조(ADT, Abstract Data Type)입니다. 배열이나 연결 리스트가 “데이터를 어떻게 저장하는가”에 대한 답이라면, 스택과 큐는 “데이터를 어떤 순서로 꺼내는가”에 대한 답입니다.

게임 엔진 내부에서는 이 두 자료구조가 수없이 활용됩니다.

• 함수 호출 스택(Call Stack): C++ 함수가 호출될 때마다 스택 프레임이 쌓이고, 반환되면 꺼내집니다.
• 실행취소(Undo) 시스템: 에디터의 Ctrl+Z는 작업 기록을 스택에 저장했다가 역순으로 꺼냅니다.
• 렌더 커맨드 큐: Render Thread는 Game Thread로부터 커맨드를 큐로 전달받아 순서대로 처리합니다.
• AI 커맨드 큐: 유닛이 이동 → 공격 → 대기 명령을 순서대로 실행할 때 큐를 사용합니다.

이 포스팅에서는 스택과 큐의 내부 구조부터 UE5 실전 코드까지 단계적으로 살펴봅니다.

---

1. 스택(Stack) — LIFO 구조와 내부 원리

1.1 LIFO(Last In, First Out) 개념

스택은 마지막으로 넣은 데이터가 가장 먼저 꺼내지는 자료구조입니다. 접시를 쌓는 것과 같습니다. 맨 위에 놓인 접시만 꺼낼 수 있고, 새 접시는 항상 맨 위에 놓습니다.

Push(10) → Push(20) → Push(30)

    [ 30 ]  ← Top (다음에 꺼낼 위치)
    [ 20 ]
    [ 10 ]
    ──────
    (Bottom)

Pop() → 30 반환
Pop() → 20 반환
Pop() → 10 반환

1.2 메모리 레이아웃과 동작 원리

std::stack은 기본적으로 std::deque를 컨테이너 어댑터(Container Adaptor)로 사용하지만, std::vector를 지정할 수도 있습니다. 내부적으로 Top 포인터(또는 인덱스) 하나만으로 모든 연산을 처리합니다.

배열 기반 스택 (std::stack<T, std::vector<T>>):

인덱스:   [0]   [1]   [2]   [3]   ...
값:       [10]  [20]  [30]  [ ]   ...
                              ↑
                           Top = 2 (현재 원소 수 - 1)

Push(40): Top++ → 인덱스 3에 40 저장
Pop():    Top-- → 인덱스 2의 값(30) 반환
Peek/Top: 인덱스 Top의 값 반환 (꺼내지 않음)

Top 포인터를 증감하는 것만으로 모든 핵심 연산이 처리되므로, 데이터를 실제로 이동시킬 필요가 없습니다.

1.3 핵심 연산과 시간복잡도

연산	메서드	시간복잡도	설명
Push (삽입)	push()	O(1) 상각	Top 위치에 삽입 (재할당 시 O(n))
Pop (제거)	pop()	O(1)	Top 원소를 제거 (반환값 없음)
Peek/Top (조회)	top()	O(1)	Top 원소를 반환 (제거하지 않음)
Empty (비어있는지 확인)	empty()	O(1)	원소 수가 0인지 확인
Size (크기)	size()	O(1)	현재 원소 수 반환

핵심 포인트: 스택의 모든 연산은 O(1)입니다. “맨 위”에 대한 접근만 허용하기 때문에 복잡한 탐색이 필요 없습니다.

1.4 C++ std::stack 코드 예시

#include <stack>
#include <vector>
#include <iostream>

// ===== 기본 std::stack 사용 =====
void BasicStackExample()
{
    // 기본 컨테이너: std::deque
    std::stack<int32_t> Stack;

    // Push — O(1) 상각
    Stack.push(10);
    Stack.push(20);
    Stack.push(30);
    // 내부 상태: Bottom[10, 20, 30]Top

    // Top 조회 — O(1), 제거 없음
    int32_t TopValue = Stack.top(); // 30
    std::cout << "Top: " << TopValue << "\n";

    // Pop — O(1), 반환값 없음 (top()으로 먼저 읽어야 함)
    Stack.pop(); // 30 제거
    Stack.pop(); // 20 제거

    // Size / Empty
    std::cout << "Size: " << Stack.size() << "\n"; // 1
    std::cout << "Empty: " << Stack.empty() << "\n"; // false

    Stack.pop(); // 10 제거
    std::cout << "Empty: " << Stack.empty() << "\n"; // true
}

// ===== 성능 최적화: vector를 내부 컨테이너로 지정 =====
// std::deque는 청크(chunk) 기반 메모리로 캐시 효율이 std::vector보다 낮음.
// 스택 크기가 예측 가능하다면 vector + reserve가 유리합니다.
void OptimizedStackExample()
{
    // vector를 내부 컨테이너로 사용
    std::stack<int32_t, std::vector<int32_t>> FastStack;

    // reserve로 재할당 방지 (스택 최대 깊이를 알고 있을 때)
    FastStack.c.reserve(128); // 주의: .c는 protected 멤버, 상속 또는 커스텀 구현 필요

    // 실무에서는 std::vector를 직접 스택처럼 사용하는 방법이 더 흔함
    std::vector<int32_t> VectorStack;
    VectorStack.reserve(128);

    VectorStack.push_back(10); // Push
    VectorStack.push_back(20);
    VectorStack.push_back(30);

    int32_t Top = VectorStack.back(); // Peek — O(1)
    VectorStack.pop_back();           // Pop  — O(1)
}

// ===== 스택 활용 예시: 괄호 유효성 검사 =====
bool IsValidParentheses(const std::string& Str)
{
    std::stack<char> BracketStack;

    for (char Ch : Str)
    {
        if (Ch == '(' || Ch == '[' || Ch == '{')
        {
            BracketStack.push(Ch); // 여는 괄호는 Push
        }
        else if (Ch == ')' || Ch == ']' || Ch == '}')
        {
            if (BracketStack.empty()) return false; // 짝 없이 닫는 괄호

            char Open = BracketStack.top();
            BracketStack.pop();

            // 짝이 맞지 않으면 유효하지 않음
            if ((Ch == ')' && Open != '(') ||
                (Ch == ']' && Open != '[') ||
                (Ch == '}' && Open != '{'))
            {
                return false;
            }
        }
    }

    return BracketStack.empty(); // 모든 괄호가 닫혔는지 확인
}

---

2. 큐(Queue) — FIFO 구조와 내부 원리

2.1 FIFO(First In, First Out) 개념

큐는 먼저 넣은 데이터가 먼저 꺼내지는 자료구조입니다. 줄 서기(대기열)와 동일한 원리입니다. 새 데이터는 항상 뒤(Back)에서 들어오고, 꺼내는 것은 항상 앞(Front)에서 이루어집니다.

Enqueue(10) → Enqueue(20) → Enqueue(30)

Front → [ 10 ][ 20 ][ 30 ] ← Back

Dequeue() → 10 반환 (Front에서 꺼냄)
Dequeue() → 20 반환
Dequeue() → 30 반환

2.2 메모리 레이아웃과 동작 원리 — 원형 버퍼(Circular Buffer)

단순 배열로 큐를 구현하면 Dequeue 시마다 나머지 원소를 모두 앞으로 이동시켜야 해서 O(n)이 됩니다. 이를 해결하는 것이 원형 버퍼(Circular Buffer / Ring Buffer) 패턴입니다.

원형 버퍼 (크기 6):

초기 상태:
Index:   [0]  [1]  [2]  [3]  [4]  [5]
         [ ]  [ ]  [ ]  [ ]  [ ]  [ ]
Front=0, Back=0

Enqueue(A, B, C):
Index:   [0]  [1]  [2]  [3]  [4]  [5]
         [A]  [B]  [C]  [ ]  [ ]  [ ]
Front=0, Back=3

Dequeue() → A 반환:
Index:   [0]  [1]  [2]  [3]  [4]  [5]
         [ ]  [B]  [C]  [ ]  [ ]  [ ]
Front=1, Back=3   (원소 이동 없음!)

Enqueue(D, E, F):
Index:   [0]  [1]  [2]  [3]  [4]  [5]
         [ ]  [B]  [C]  [D]  [E]  [F]
Front=1, Back=6%6=0

Enqueue(G) — Back이 인덱스 0으로 wrap around:
Index:   [0]  [1]  [2]  [3]  [4]  [5]
         [G]  [B]  [C]  [D]  [E]  [F]
Front=1, Back=1  (가득 참)

Front와 Back 인덱스를 % 배열크기로 순환시키면 원소를 이동시키지 않고도 O(1) 연산이 가능합니다. std::deque는 고정 크기 청크(chunk)를 연결하는 방식으로 비슷한 효과를 얻습니다.

2.3 핵심 연산과 시간복잡도

연산	메서드	시간복잡도	설명
Enqueue/Push (삽입)	push()	O(1) 상각	Back에 삽입
Dequeue/Pop (제거)	pop()	O(1)	Front 원소를 제거 (반환값 없음)
Front 조회	front()	O(1)	Front 원소를 반환 (제거하지 않음)
Back 조회	back()	O(1)	Back 원소를 반환 (제거하지 않음)
Empty (비어있는지 확인)	empty()	O(1)	원소 수가 0인지 확인
Size (크기)	size()	O(1)	현재 원소 수 반환

2.4 C++ std::queue / std::deque 코드 예시

#include <queue>
#include <deque>

// ===== 기본 std::queue 사용 =====
void BasicQueueExample()
{
    // 기본 컨테이너: std::deque
    std::queue<int32_t> Queue;

    // Enqueue (Push) — O(1) 상각
    Queue.push(10);
    Queue.push(20);
    Queue.push(30);
    // 내부 상태: Front[10, 20, 30]Back

    // Front / Back 조회 — O(1), 제거 없음
    int32_t FrontVal = Queue.front(); // 10
    int32_t BackVal  = Queue.back();  // 30

    // Dequeue (Pop) — O(1), 반환값 없음
    Queue.pop(); // 10 제거
    Queue.pop(); // 20 제거

    std::cout << "Front: " << Queue.front() << "\n"; // 30
    std::cout << "Size: "  << Queue.size()  << "\n"; // 1
}

// ===== std::deque — 앞뒤 삽입·삭제가 모두 O(1)인 범용 컨테이너 =====
// std::queue와 std::stack의 기본 컨테이너이며, 독립적으로도 자주 사용됩니다.
void DequeExample()
{
    std::deque<int32_t> Deque;

    // 뒤 삽입 — O(1)
    Deque.push_back(20);
    Deque.push_back(30);

    // 앞 삽입 — O(1)  (std::vector는 O(n))
    Deque.push_front(10);
    // 결과: [10, 20, 30]

    // 인덱스 접근 — O(1)  (std::list는 O(n))
    int32_t Middle = Deque[1]; // 20

    // 앞 제거 — O(1)
    Deque.pop_front();

    // 뒤 제거 — O(1)
    Deque.pop_back();

    // 중간 삽입 — O(n) (이 경우는 std::vector와 동일)
    Deque.insert(Deque.begin() + 1, 25);
}

// ===== 큐 활용 예시: BFS (너비 우선 탐색) =====
struct FNode
{
    int32_t Value;
    int32_t Left  = -1; // 왼쪽 자식 인덱스 (-1: 없음)
    int32_t Right = -1; // 오른쪽 자식 인덱스
};

void BreadthFirstSearch(const std::vector<FNode>& Tree, int32_t RootIdx)
{
    if (Tree.empty()) return;

    std::queue<int32_t> NodeQueue;
    NodeQueue.push(RootIdx); // 루트 노드 인덱스 삽입

    while (!NodeQueue.empty())
    {
        int32_t CurrIdx = NodeQueue.front(); // Front 조회
        NodeQueue.pop();                      // 제거

        const FNode& Curr = Tree[CurrIdx];
        std::cout << "Visit: " << Curr.Value << "\n";

        // 자식 노드를 큐에 삽입 (왼쪽 → 오른쪽 순서 유지)
        if (Curr.Left  != -1) NodeQueue.push(Curr.Left);
        if (Curr.Right != -1) NodeQueue.push(Curr.Right);
    }
}

---

3. 시간복잡도 종합 비교

연산	std::stack	std::queue	std::deque	std::vector (참고)
끝(Back) 삽입	O(1) 상각	O(1) 상각	O(1) 상각	O(1) 상각
앞(Front) 삽입	불가	불가	O(1) 상각	O(n)
끝(Back) 제거	O(1) — Top	불가	O(1)	O(1)
앞(Front) 제거	불가	O(1) — Front	O(1)	O(n)
Top/Front 조회	O(1)	O(1)	O(1)	O(1)
인덱스 임의 접근	불가	불가	O(1)	O(1)
중간 삽입/삭제	불가	불가	O(n)	O(n)

핵심 설계 원칙: 스택과 큐는 의도적으로 접근을 제한합니다. “중간 원소를 꺼내야 한다”는 요구가 생긴다면, 그 자료구조는 스택/큐가 아닌 다른 자료구조가 필요하다는 신호입니다.

---

4. Unreal Engine 실전 활용

4.1 실행취소(Undo) 스택

에디터나 게임 내 실행취소 기능은 스택의 가장 대표적인 활용 사례입니다. 작업을 할 때마다 스택에 쌓고, Undo 시 역순으로 꺼내 되돌립니다.

// Engine/Source/Editor/UnrealEd/Public/Editor.h 참조
// Unreal Editor는 내부적으로 FTransaction 기반 Undo/Redo 시스템을 사용하지만
// 게임플레이용 커스텀 Undo 스택을 별도로 구현하는 패턴을 보여줍니다.

// 커맨드 패턴 + 스택으로 Undo 구현
class ICommand
{
public:
    virtual ~ICommand() = default;
    virtual void Execute()  = 0;
    virtual void Undo()     = 0;
};

// 캐릭터 이동 커맨드 예시
class FMoveCommand : public ICommand
{
public:
    FMoveCommand(AActor* InTarget, const FVector& InDelta)
        : Target(InTarget)
        , MoveDelta(InDelta)
    {
    }

    virtual void Execute() override
    {
        if (IsValid(Target))
        {
            Target->AddActorWorldOffset(MoveDelta);
        }
    }

    virtual void Undo() override
    {
        if (IsValid(Target))
        {
            Target->AddActorWorldOffset(-MoveDelta); // 반대 방향으로 이동
        }
    }

private:
    TObjectPtr<AActor> Target;
    FVector            MoveDelta;
};

// Undo 스택 매니저
UCLASS()
class UCommandManager : public UObject
{
    GENERATED_BODY()

public:
    // 커맨드 실행 후 Undo 스택에 Push
    void ExecuteCommand(TSharedPtr<ICommand> InCommand)
    {
        if (!InCommand.IsValid()) return;

        InCommand->Execute();
        UndoStack.push(InCommand);

        // Redo 스택은 새 커맨드 실행 시 무효화
        while (!RedoStack.empty())
        {
            RedoStack.pop();
        }
    }

    // Undo: 스택의 Top 커맨드를 역실행
    void Undo()
    {
        if (UndoStack.empty()) return;

        TSharedPtr<ICommand> Command = UndoStack.top();
        UndoStack.pop();

        Command->Undo();
        RedoStack.push(Command); // Undo된 커맨드는 Redo 스택으로 이동
    }

    // Redo: Redo 스택 Top을 재실행
    void Redo()
    {
        if (RedoStack.empty()) return;

        TSharedPtr<ICommand> Command = RedoStack.top();
        RedoStack.pop();

        Command->Execute();
        UndoStack.push(Command);
    }

    bool CanUndo() const { return !UndoStack.empty(); }
    bool CanRedo() const { return !RedoStack.empty(); }

private:
    std::stack<TSharedPtr<ICommand>> UndoStack;
    std::stack<TSharedPtr<ICommand>> RedoStack;
};

4.2 게임 이벤트 큐

Game Thread와 Render Thread, 또는 서버-클라이언트 간 이벤트를 순서대로 처리할 때 큐를 사용합니다. Unreal Engine의 TQueue는 Lock-Free 멀티스레드 큐로, 스레드 간 안전한 이벤트 전달에 최적화되어 있습니다.

// Engine/Source/Runtime/Core/Public/Containers/Queue.h 참조
#include "Containers/Queue.h"

// 게임 이벤트 구조체
struct FGameEvent
{
    enum class EType : uint8
    {
        PlayerDamaged,
        EnemyKilled,
        ItemPickup,
        LevelCompleted,
    };

    EType   Type;
    int32   SourceActorID;
    int32   TargetActorID;
    float   Value; // 데미지량, 보상 등
};

// 이벤트 큐 시스템 (Game Thread에서 생산, 처리 시스템에서 소비)
UCLASS()
class AEventQueueManager : public AActor
{
    GENERATED_BODY()

public:
    // 이벤트 발생 시 큐에 삽입 (여러 스레드에서 안전하게 호출 가능)
    // TQueue<T, EQueueMode::Mpsc>: Multi-Producer, Single-Consumer
    void EnqueueEvent(const FGameEvent& Event)
    {
        EventQueue.Enqueue(Event);
    }

    // 매 Tick에 큐에 쌓인 이벤트를 일괄 처리
    virtual void Tick(float DeltaTime) override
    {
        Super::Tick(DeltaTime);

        // 이번 Tick에 처리할 최대 이벤트 수 제한 (프레임 예산 보호)
        constexpr int32 MaxEventsPerTick = 32;
        int32 ProcessedCount = 0;

        FGameEvent Event;
        while (ProcessedCount < MaxEventsPerTick && EventQueue.Dequeue(Event))
        {
            ProcessEvent(Event);
            ++ProcessedCount;
        }
    }

private:
    // Spsc: Single-Producer Single-Consumer (단일 생산자-소비자, 가장 빠름)
    // Mpsc: Multi-Producer Single-Consumer (다중 생산자-단일 소비자)
    TQueue<FGameEvent, EQueueMode::Mpsc> EventQueue;

    void ProcessEvent(const FGameEvent& Event)
    {
        switch (Event.Type)
        {
        case FGameEvent::EType::PlayerDamaged:
            // 데미지 처리 로직
            UE_LOG(LogTemp, Log, TEXT("Player %d took %.1f damage from %d"),
                Event.TargetActorID, Event.Value, Event.SourceActorID);
            break;

        case FGameEvent::EType::EnemyKilled:
            // 적 처치 처리 로직
            UE_LOG(LogTemp, Log, TEXT("Enemy %d killed by %d"),
                Event.TargetActorID, Event.SourceActorID);
            break;

        default:
            break;
        }
    }
};

4.3 AI 커맨드 큐

유닛이 명령을 순서대로 실행할 때 큐를 사용합니다. 이동 → 공격 → 대기처럼 선입선출 순서가 보장되어야 합니다.

// AI 커맨드 타입
UENUM(BlueprintType)
enum class EAICommandType : uint8
{
    MoveTo      UMETA(DisplayName = "Move To"),
    AttackTarget UMETA(DisplayName = "Attack Target"),
    Wait        UMETA(DisplayName = "Wait"),
    Patrol      UMETA(DisplayName = "Patrol"),
};

USTRUCT(BlueprintType)
struct FAICommand
{
    GENERATED_BODY()

    UPROPERTY(EditAnywhere, BlueprintReadWrite)
    EAICommandType Type = EAICommandType::Wait;

    UPROPERTY(EditAnywhere, BlueprintReadWrite)
    FVector TargetLocation = FVector::ZeroVector;

    UPROPERTY(EditAnywhere, BlueprintReadWrite)
    TObjectPtr<AActor> TargetActor = nullptr;

    UPROPERTY(EditAnywhere, BlueprintReadWrite)
    float Duration = 0.f; // Wait 커맨드 지속 시간
};

// AI 컨트롤러에서 커맨드 큐 사용
UCLASS()
class AMyAIController : public AAIController
{
    GENERATED_BODY()

public:
    // 커맨드를 큐 뒤에 추가
    UFUNCTION(BlueprintCallable, Category = "AI|Command")
    void QueueCommand(const FAICommand& Command)
    {
        CommandQueue.Enqueue(Command);

        // 현재 유휴 상태라면 즉시 다음 커맨드 실행
        if (!bIsExecutingCommand)
        {
            ExecuteNextCommand();
        }
    }

    // 현재 커맨드 취소 후 큐 비우기 (긴급 명령 시)
    UFUNCTION(BlueprintCallable, Category = "AI|Command")
    void ClearCommandQueue()
    {
        // TQueue에는 Empty() 메서드가 없으므로 Dequeue로 비움
        FAICommand Discarded;
        while (CommandQueue.Dequeue(Discarded)) {}

        bIsExecutingCommand = false;
    }

    // 커맨드 완료 시 호출 (이동 완료, 공격 완료 등 이벤트에서 호출)
    void OnCommandCompleted()
    {
        bIsExecutingCommand = false;
        ExecuteNextCommand();
    }

private:
    TQueue<FAICommand> CommandQueue;
    bool               bIsExecutingCommand = false;

    void ExecuteNextCommand()
    {
        FAICommand NextCommand;
        if (!CommandQueue.Dequeue(NextCommand))
        {
            return; // 큐가 비어있으면 대기
        }

        bIsExecutingCommand = true;

        switch (NextCommand.Type)
        {
        case EAICommandType::MoveTo:
            MoveToLocation(NextCommand.TargetLocation);
            break;

        case EAICommandType::AttackTarget:
            if (IsValid(NextCommand.TargetActor))
            {
                // 공격 로직 실행
            }
            break;

        case EAICommandType::Wait:
            // 타이머로 Duration 후 OnCommandCompleted 호출
            GetWorldTimerManager().SetTimer(
                WaitTimerHandle,
                this,
                &AMyAIController::OnCommandCompleted,
                NextCommand.Duration,
                false
            );
            break;

        default:
            OnCommandCompleted(); // 알 수 없는 커맨드는 즉시 완료 처리
            break;
        }
    }

    FTimerHandle WaitTimerHandle;
};

---

5. 우선순위 큐(Priority Queue)와 힙(Heap) 기초

5.1 우선순위 큐란?

일반 큐는 먼저 들어온 것이 먼저 나가지만, 우선순위 큐는 가장 높은 우선순위를 가진 원소가 먼저 나갑니다. 병원 응급실처럼, 도착 순서보다 긴급도에 따라 처리되는 구조입니다.

우선순위 큐에 삽입: (우선순위, 값)
Insert(3, "일반 몬스터")
Insert(7, "보스 몬스터")   ← 우선순위 7
Insert(1, "잡몹")
Insert(5, "엘리트 몬스터")

Pop 순서: (7, "보스") → (5, "엘리트") → (3, "일반") → (1, "잡몹")

5.2 힙(Heap) — 우선순위 큐의 내부 구조

우선순위 큐는 일반적으로 힙(Heap) 자료구조로 구현됩니다. 힙은 **완전 이진 트리(Complete Binary Tree)**이며, 부모 노드가 자식 노드보다 항상 크거나(Max-Heap) 작은(Min-Heap) 성질을 가집니다.

Max-Heap 예시 (부모 >= 자식):

         [90]            ← 루트: 항상 최대값
        /    \
     [70]    [80]
    /    \   /
  [40] [50] [60]

배열 표현: [90, 70, 80, 40, 50, 60]
인덱스:     [0]  [1]  [2]  [3]  [4]  [5]

부모-자식 관계 (0-indexed):
- 인덱스 i의 왼쪽 자식: 2*i + 1
- 인덱스 i의 오른쪽 자식: 2*i + 2
- 인덱스 i의 부모: (i - 1) / 2

힙의 핵심은 항상 루트에 최대값(또는 최소값)이 위치한다는 것입니다. Pop 시 루트를 꺼내고 힙 성질을 복원(Heapify)하는 데 O(log n)이 걸립니다.

연산	시간복잡도	설명
Push (삽입)	O(log n)	끝에 추가 후 위로 Heapify-Up
Pop (최댓값 제거)	O(log n)	루트 제거 후 Heapify-Down
Top/Peek (최댓값 조회)	O(1)	항상 루트
힙 생성 (Build Heap)	O(n)	n개 원소로 힙 초기화

5.3 C++ std::priority_queue 사용법

#include <queue>
#include <functional> // std::greater

// ===== Max-Heap (기본): 가장 큰 값이 먼저 나옴 =====
void MaxHeapExample()
{
    std::priority_queue<int32_t> MaxHeap;

    MaxHeap.push(30);
    MaxHeap.push(10);
    MaxHeap.push(50);
    MaxHeap.push(20);

    // Pop 순서: 50 → 30 → 20 → 10 (내림차순)
    while (!MaxHeap.empty())
    {
        std::cout << MaxHeap.top() << " "; // Peek
        MaxHeap.pop();
    }
}

// ===== Min-Heap: std::greater<T> 지정 — 가장 작은 값이 먼저 나옴 =====
void MinHeapExample()
{
    std::priority_queue<int32_t, std::vector<int32_t>, std::greater<int32_t>> MinHeap;

    MinHeap.push(30);
    MinHeap.push(10);
    MinHeap.push(50);
    MinHeap.push(20);

    // Pop 순서: 10 → 20 → 30 → 50 (오름차순)
    while (!MinHeap.empty())
    {
        std::cout << MinHeap.top() << " ";
        MinHeap.pop();
    }
}

// ===== 커스텀 비교 함수: 구조체 기반 우선순위 큐 =====
struct FTask
{
    int32       Priority; // 높을수록 먼저 처리
    FString     Name;
    float       ExecutionTime;
};

// 우선순위가 높을수록 먼저 나오게 하려면 less-than이 아닌 greater-than으로 비교
struct FTaskComparator
{
    bool operator()(const FTask& A, const FTask& B) const
    {
        return A.Priority < B.Priority; // Max-Heap: 우선순위 높은 것이 Top
    }
};

void TaskSchedulerExample()
{
    std::priority_queue<FTask, std::vector<FTask>, FTaskComparator> TaskQueue;

    TaskQueue.push({3, TEXT("일반 AI 업데이트"), 0.5f});
    TaskQueue.push({9, TEXT("플레이어 데미지 처리"), 0.1f});
    TaskQueue.push({1, TEXT("환경 오브젝트 업데이트"), 2.0f});
    TaskQueue.push({7, TEXT("보스 AI 페이즈 전환"), 0.3f});

    // 처리 순서: 우선순위 9 → 7 → 3 → 1
    while (!TaskQueue.empty())
    {
        const FTask& Top = TaskQueue.top();
        UE_LOG(LogTemp, Log, TEXT("[Priority %d] %s"), Top.Priority, *Top.Name);
        TaskQueue.pop();
    }
}

5.4 UE5에서의 활용 — TArray 기반 힙 연산

Unreal Engine은 TArray에 힙 연산 메서드를 내장하고 있습니다. 별도의 자료구조 없이 TArray를 힙으로 사용할 수 있습니다.

// Engine/Source/Runtime/Core/Public/Containers/Array.h 참조
// TArray::HeapPush / HeapPop / HeapTop / Heapify

#include "Containers/Array.h"

// UE5의 TArray 힙 예시
void UE5HeapExample()
{
    TArray<int32> Heap;

    // Heapify: 기존 TArray를 Max-Heap으로 변환 — O(n)
    Heap = {30, 10, 50, 20, 40};
    Heap.Heapify(); // 내부 배열을 힙 성질 만족하도록 재정렬

    // HeapPush: 힙에 원소 삽입 — O(log n)
    Heap.HeapPush(60);

    // HeapTop: 최대값 조회 — O(1)
    int32 MaxValue = Heap.HeapTop(); // 60

    // HeapPop: 최대값 제거 및 반환 — O(log n)
    int32 Popped;
    Heap.HeapPop(Popped, /*bAllowShrinking=*/false);
    // Popped == 60, bAllowShrinking=false로 메모리 재할당 방지
}

// 커스텀 비교자(Predicate)를 사용한 Min-Heap
void UE5MinHeapExample()
{
    TArray<int32> MinHeap = {30, 10, 50, 20, 40};

    // 람다로 Min-Heap 정렬 (작은 값이 Top)
    auto MinPredicate = [](const int32& A, const int32& B)
    {
        return A < B; // A가 B보다 작으면 A가 더 높은 우선순위
    };

    MinHeap.Heapify(MinPredicate);

    int32 MinPopped;
    MinHeap.HeapPop(MinPopped, MinPredicate, /*bAllowShrinking=*/false);
    // MinPopped == 10
}

// 실전 예시: Damage Number 우선순위 처리
// 화면에 표시할 데미지 숫자를 우선순위 큐로 관리
USTRUCT()
struct FDamageDisplay
{
    GENERATED_BODY()

    float   Damage     = 0.f;
    bool    bIsCritical = false;
    float   Priority   = 0.f; // 크리티컬 > 일반
};

UCLASS()
class UDamageDisplaySystem : public UGameInstanceSubsystem
{
    GENERATED_BODY()

public:
    void AddDamageDisplay(float Damage, bool bCritical)
    {
        FDamageDisplay Display;
        Display.Damage      = Damage;
        Display.bIsCritical = bCritical;
        Display.Priority    = bCritical ? Damage * 2.f : Damage; // 크리티컬 가중치

        DisplayQueue.HeapPush(Display, [](const FDamageDisplay& A, const FDamageDisplay& B)
        {
            return A.Priority > B.Priority; // Priority 높은 것이 Top
        });
    }

    void ProcessTopDisplay()
    {
        if (DisplayQueue.IsEmpty()) return;

        FDamageDisplay Top;
        DisplayQueue.HeapPop(Top, [](const FDamageDisplay& A, const FDamageDisplay& B)
        {
            return A.Priority > B.Priority;
        }, /*bAllowShrinking=*/false);

        // 화면에 데미지 숫자 표시 로직
        UE_LOG(LogTemp, Log, TEXT("Displaying Damage: %.1f (Critical: %s)"),
            Top.Damage,
            Top.bIsCritical ? TEXT("YES") : TEXT("NO")
        );
    }

private:
    TArray<FDamageDisplay> DisplayQueue; // TArray를 힙으로 운용
};

---

6. 정리 및 체크리스트

한눈에 보는 선택 기준

질문	적합한 자료구조
LIFO가 필요한가? (역순 처리, Undo, 함수 호출)	std::stack / TArray(스택처럼)
FIFO가 필요한가? (이벤트 처리, AI 명령, BFS)	std::queue / TQueue
앞뒤 삽입·삭제가 모두 O(1)이어야 하는가?	std::deque
우선순위에 따라 처리 순서가 달라야 하는가?	std::priority_queue / TArray(Heap)
멀티스레드 환경에서 큐가 필요한가?	TQueue (Lock-Free)

게임 개발 스택·큐 체크리스트

• 실행취소 기능 구현 시 커맨드 패턴과 스택을 조합했는가?
• AI 명령 처리에서 순서 보장이 필요한 경우 큐를 사용하고 있는가?
• 멀티스레드 이벤트 전달에는 TQueue<T, EQueueMode::Mpsc>를 사용하고 있는가?
• 우선순위 큐가 필요할 때 TArray::HeapPush/HeapPop을 활용하고 있는가?
• Tick 내에서 이벤트 큐를 처리할 때 프레임당 처리 수 상한을 두고 있는가?
• std::priority_queue::pop()은 반환값이 없으므로 top() 후 pop() 패턴을 지키고 있는가?
• TQueue::Dequeue()의 반환값(bool)으로 큐가 비어있는지 확인하고 있는가?