스택과 큐

스택과 큐

1. 스택과 큐란?

스택(Stack)과 큐(Queue)는 여러 데이터를 저장하고 관리하는 자료구조이다.

둘의 가장 큰 차이점은 데이터를 어떤 순서로 꺼내는가이다.

• Stack → LIFO
• Queue → FIFO

즉, 데이터를 저장하는 방식보다 데이터를 꺼내는 순서가 핵심이다.

---

2. Stack

2-1. Stack이란?

Stack은 LIFO(Last In, First Out) 방식의 자료구조이다.

LIFO는 후입선출이라는 의미로, 가장 나중에 들어온 데이터가 가장 먼저 나간다.

책을 위로 계속 쌓는 상황을 생각하면 이해하기 쉽다.

      [ C ] ← 가장 먼저 꺼냄
      [ B ]
      [ A ]

A → B → C 순서로 데이터를 넣었다면:

Push(A)
Push(B)
Push(C)

Pop() → C
Pop() → B
Pop() → A

즉,

입력: A → B → C
출력: C → B → A

가 된다.

---

3. Stack의 주요 연산

Stack에서 가장 중요한 연산은 다음과 같다.

• Push
• Pop
• Top

추가적으로 Empty와 Size도 자주 사용한다.

---

3-1. Push

Push는 Stack에 데이터를 추가하는 연산이다.

stack.push(10);

처음에는:

[10]

다시 20을 넣으면:

stack.push(20);

[20] ← Top
[10]

30을 넣으면:

stack.push(30);

[30] ← Top
[20]
[10]

따라서 Push는 Stack의 위쪽에 데이터를 추가하는 연산이라고 이해하면 된다.

---

3-2. Pop

Pop은 Stack의 가장 위에 있는 데이터를 제거하는 연산이다.

현재 Stack이 다음과 같다고 하자.

[30] ← Top
[20]
[10]

stack.pop();

을 실행하면:

[20] ← Top
[10]

30이 제거된다.

여기서 중요한 점은 C++의 pop()은 제거한 값을 반환하지 않는다는 것이다.

따라서 다음과 같이 사용할 수 없다.

int value = stack.pop();

대신 데이터를 확인한 후 제거해야 한다.

int value = stack.top();
stack.pop();

즉,

top() → 현재 데이터를 확인
pop() → 데이터를 제거

의 역할을 한다.

---

3-3. Top

Top은 Stack의 가장 위에 있는 데이터를 확인하는 연산이다.

예를 들어:

[30] ← Top
[20]
[10]

일 때:

stack.top();

을 실행하면 30을 확인할 수 있다.

하지만 Top은 데이터를 제거하지 않는다.

즉:

top()
↓
데이터 확인

pop()
↓
데이터 제거

로 구분해야 한다.

---

3-4. Empty

Stack이 비어 있는지 확인하는 연산이다.

stack.empty();

비어 있다면 true, 데이터가 있다면 false를 반환한다.

예를 들어:

if (!stack.empty())
{
    int value = stack.top();
    stack.pop();
}

이런 방식으로 사용할 수 있다.

빈 Stack에서 top()이나 pop()을 사용하는 것은 잘못된 사용이므로, 데이터를 꺼내기 전에 비어 있는지 확인하는 습관이 중요하다.

---

3-5. Size

현재 Stack에 몇 개의 데이터가 들어 있는지 확인한다.

stack.size();

예를 들어:

[30]
[20]
[10]

이라면:

stack.size();

의 결과는 3이다.

---

4. C++의 std::stack

C++에서는 Stack을 직접 구현하지 않아도 STL에서 제공하는 std::stack을 사용할 수 있다.

#include <stack>

std::stack<int> stack;

std::stack<int>에서 int는 Stack에 저장할 데이터의 타입이다.

예를 들어:

stack.push(10);
stack.push(20);
stack.push(30);

을 실행하면:

[30] ← Top
[20]
[10]

이 된다.

그리고:

while (!stack.empty())
{
    int value = stack.top();
    stack.pop();
}

를 사용하면:

30
20
10

순서로 데이터를 처리하게 된다.

---

5. Queue

5-1. Queue란?

Queue는 FIFO(First In, First Out) 방식의 자료구조이다.

FIFO는 선입선출이라는 의미이다.

즉, 가장 먼저 들어온 데이터가 가장 먼저 나간다.

사람들이 줄을 서 있는 상황을 생각하면 이해하기 쉽다.

입구                         출구
 ↓                            ↓

[A] [B] [C] [D]

A가 가장 먼저 들어왔다면 A가 가장 먼저 나간다.

Enqueue(A)
Enqueue(B)
Enqueue(C)

Dequeue() → A
Dequeue() → B
Dequeue() → C

즉,

입력: A → B → C
출력: A → B → C

가 된다.

---

6. Queue의 주요 연산

Queue에서는 다음과 같은 개념을 사용한다.

• Enqueue
• Dequeue
• Front
• Back

C++의 std::queue에서는 Enqueue와 Dequeue라는 이름 대신 push()와 pop()을 사용한다.

---

6-1. Enqueue

Enqueue는 Queue의 뒤쪽에 데이터를 추가하는 연산이다.

개념적으로:

[10]

여기에 20과 30을 추가하면:

Front              Back
 ↓                   ↓
[10] [20] [30]

가 된다.

C++의 std::queue에서는 다음과 같이 사용한다.

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

여기서 push()는 Queue에서는 뒤쪽에 데이터를 추가하는 역할을 한다.

---

7. Dequeue

Dequeue는 Queue의 가장 앞쪽에 있는 데이터를 제거하는 연산이다.

현재 Queue가:

Front              Back
 ↓                   ↓
[10] [20] [30]

이라면:

queue.pop();

을 실행했을 때 10이 제거된다.

결과:

Front        Back
 ↓             ↓
[20] [30]

Stack과 마찬가지로 queue.pop()도 제거한 값을 반환하지 않는다.

따라서 다음과 같이 사용해야 한다.

int value = queue.front();
queue.pop();

즉,

front() → 데이터 확인
pop()   → 데이터 제거

의 순서이다.

---

8. Front

Front는 Queue의 가장 앞에 있는 데이터를 확인하는 연산이다.

예를 들어:

Front              Back
 ↓                   ↓
[10] [20] [30]

에서:

queue.front();

를 실행하면 10을 확인할 수 있다.

하지만 front()는 데이터를 제거하지 않는다.

따라서:

int value = queue.front();

를 실행해도 Queue는 그대로 유지된다.

[10] [20] [30]

---

9. Back

Back은 Queue의 가장 뒤에 있는 데이터를 확인하는 연산이다.

Front              Back
 ↓                   ↓
[10] [20] [30]

에서:

queue.back();

을 실행하면 30을 확인할 수 있다.

Front와 Back 역시 확인만 하는 연산이고 데이터를 제거하지 않는다.

---

10. Queue의 Empty와 Size

Stack과 마찬가지로 Queue에서도 empty()와 size()를 사용할 수 있다.

Empty

queue.empty();

Queue가 비어 있는지 확인한다.

Size

queue.size();

현재 Queue에 저장된 데이터의 개수를 확인한다.

예를 들어:

[10] [20] [30]

이라면:

queue.size();

의 결과는 3이다.

---

11. C++의 std::queue

C++에서는 STL에서 제공하는 std::queue를 사용할 수 있다.

#include <queue>

std::queue<int> queue;

데이터를 추가하면:

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

다음과 같은 상태가 된다.

Front              Back
 ↓                   ↓
[10] [20] [30]

그리고:

while (!queue.empty())
{
    int value = queue.front();
    queue.pop();
}

를 실행하면:

10
20
30

순서로 데이터를 처리하게 된다.

---

12. Stack과 Queue 비교

Stack과 Queue는 둘 다 데이터를 저장하지만 데이터를 꺼내는 순서가 다르다.

구분StackQueue

방식	LIFO	FIFO
의미	후입선출	선입선출
먼저 나가는 데이터	가장 나중에 들어온 데이터	가장 먼저 들어온 데이터
데이터 추가	Push	Enqueue
데이터 제거	Pop	Dequeue
데이터 확인	Top	Front
뒤쪽 확인	없음	Back
C++	std::stack	std::queue

간단하게 기억하면:

Stack

넣기 ↓
[ C ] ← 꺼내기
[ B ]
[ A ]

LIFO

Queue

넣기 → [ A ] [ B ] [ C ] → 꺼내기

        FIFO

---

13. std::deque

Stack과 Queue를 공부하면 std::deque도 함께 알아둘 필요가 있다.

deque는 Double Ended Queue의 줄임말이다.

말 그대로 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료구조이다.

Front                    Back
 ↓                         ↓
[ A ] [ B ] [ C ] [ D ]
 ↑                         ↑
앞에서 추가/삭제       뒤에서 추가/삭제

C++에서는:

#include <deque>

std::deque<int> dq;

와 같이 사용할 수 있다.

---

13-1. push_front()

앞쪽에 데이터를 추가한다.

dq.push_front(10);

---

13-2. push_back()

뒤쪽에 데이터를 추가한다.

dq.push_back(20);

결과:

[10] [20]

---

13-3. pop_front()

앞쪽의 데이터를 제거한다.

dq.pop_front();

---

13-4. pop_back()

뒤쪽의 데이터를 제거한다.

dq.pop_back();

즉 deque는 양쪽을 자유롭게 사용할 수 있다는 특징이 있다.

---

14. Stack, Queue, Deque의 관계

Stack과 Queue가 완전히 별개의 저장 방식이라고 생각할 필요는 없다.

Stack과 Queue는 데이터를 사용하는 규칙이 다른 자료구조라고 이해하는 것이 좋다.

개념적으로:

Deque
 ├── 앞/뒤 모두 사용 가능
 │
 ├── Stack처럼 사용 가능
 │
 └── Queue처럼 사용 가능

deque는 양쪽에서 데이터를 추가하고 제거할 수 있기 때문에 Stack과 Queue를 구현하는 데 적합하다.

즉, 자료구조에서는 단순히 "어떤 데이터를 저장하는가"뿐만 아니라 어떤 방식으로 데이터를 접근하고 제거하도록 제한하는가도 중요하다.

---

15. Stack과 이후 자료구조의 연결

Stack은 이후에 공부할 내용과 연결되는 중요한 자료구조이다.

특히 다음과 같은 관계가 있다.

Stack
  ↓
재귀
  ↓
DFS

하지만 여기서 재귀와 DFS의 자세한 내용을 다루지는 않는다.

현재 단계에서는 Stack이 이후 알고리즘 공부에서 중요한 역할을 한다는 것만 알아두면 된다.

다음 단계인 재귀에서 함수를 반복적으로 호출하고 종료하면서 이전 호출 위치로 돌아가는 과정 등을 공부하게 되면 Stack과의 관계를 자세하게 이해할 수 있다.

---

16. Stack과 Queue를 실제 문제에 적용하면

자료구조는 단순히 자료를 저장하기 위한 문법이 아니라 문제의 상황에 맞는 데이터 처리 순서를 선택하는 도구이다.

예를 들어 작업을 처리한다고 생각해보자.

Stack을 사용하는 경우

최근에 들어온 작업을 먼저 처리해야 한다면 Stack이 적합하다.

작업 A
작업 B
작업 C ← 가장 최근에 들어옴

처리 순서:
C → B → A

이것이 LIFO이다.

---

Queue를 사용하는 경우

먼저 들어온 작업을 먼저 처리해야 한다면 Queue가 적합하다.

작업 A → 작업 B → 작업 C

처리 순서:
A → B → C

이것이 FIFO이다.

따라서 자료구조를 공부할 때는 단순히 함수 이름을 외우는 것보다:

이 상황에서는 어떤 순서로 데이터를 꺼내야 하는가?

를 생각하는 것이 중요하다.

---

17. Unreal Engine에서 생각해보기

Unreal Engine에서도 C++ 자료구조를 사용할 수 있다.

예를 들어 여러 작업을 순서대로 처리해야 하는 상황을 생각하면 Queue의 개념을 적용할 수 있다.

처리해야 할 작업

[이동] [공격] [재장전]

먼저 들어온 작업부터 처리한다면:

이동 → 공격 → 재장전

이므로 Queue의 FIFO 방식과 비슷하다.

반대로 가장 최근의 작업을 먼저 처리해야 하는 상황이라면:

이동
공격
재장전 ← 가장 최근 작업

Stack의 LIFO 방식이 적합할 수 있다.

다만 이것은 자료구조의 개념을 이해하기 위한 예시이며, Unreal Engine에서 모든 작업 시스템을 무조건 std::stack이나 std::queue로 구현한다는 의미는 아니다.

---

18. 이번 단계에서 꼭 기억해야 할 핵심

Stack

LIFO
Last In First Out
후입선출

가장 나중에 들어온 데이터가 가장 먼저 나간다.

주요 연산:

push()
pop()
top()
empty()
size()

중요한 점:

int value = stack.top();
stack.pop();

top()은 확인하고 pop()은 제거한다.

pop()이 값을 반환한다고 생각하면 안 된다.

---

Queue

FIFO
First In First Out
선입선출

가장 먼저 들어온 데이터가 가장 먼저 나간다.

주요 연산:

push()
pop()
front()
back()
empty()
size()

중요한 점:

int value = queue.front();
queue.pop();

front()는 확인하고 pop()은 제거한다.

Queue에서도 pop()이 값을 반환하지 않는다는 점을 기억해야 한다.

---

Deque

Double Ended Queue

양쪽 끝에서 데이터를 추가하거나 제거할 수 있다.

주요 연산:

push_front()
push_back()
pop_front()
pop_back()

---

19. 최종 정리

이번 단계에서 가장 중요한 것은 다음 세 가지이다.

① Stack = LIFO

A → B → C

C → B → A

마지막에 들어온 것이 먼저 나간다.

② Queue = FIFO

A → B → C

A → B → C

먼저 들어온 것이 먼저 나간다.

③ 데이터 확인과 제거는 별개이다.

Stack:

stack.top();
stack.pop();

Queue:

queue.front();
queue.pop();

즉:

확인 → 제거

의 구조를 기억해야 한다.

---

20. C++ 자료구조 정리

std::stack
    ↓
한쪽 끝에서 추가/제거
    ↓
LIFO

std::queue
    ↓
뒤에서 추가 / 앞에서 제거
    ↓
FIFO

std::deque
    ↓
앞과 뒤 모두 추가/제거 가능

이번 4단계의 핵심은 Stack과 Queue의 동작 원리를 이해하고, 각각 언제 필요한지를 구분하는 것이다.

특히 다음 단계에서 재귀를 공부할 때 Stack과의 연결 관계가 등장하므로, 지금은 Stack = LIFO, Queue = FIFO라는 기본 구조를 확실하게 이해해 두는 것이 중요하다.