[Stack, Queue] std::stack, queue

 

 

std::stack

이번에는 스택(Stack) 에 대해 알아봅니다.

여기서 말하는 스택은 메모리 영역(Stack Memory) 이 아니라,

자료구조(Stack Data Structure) 를 의미합니다.

 

 

 

3-1. 스택(Stack)이란?

스택은

LIFO (Last In, First Out)

구조를 가지는 자료구조입니다.

즉,

가장 마지막에 들어온 데이터가 가장 먼저 나갑니다.

예를 들어

push(1)
push(3)
push(5)

를 수행하면

5
3
1

순서로 꺼내게 됩니다.

---

3-2. std::stack

CPP Reference에서 std::stack을 보면

std::stack<T, Container>

형태의 템플릿으로 제공됩니다.

기본 컨테이너는

std::deque

이며,

필요하면

• std::vector
• std::list

등을 내부 컨테이너로 사용할 수도 있습니다.

주요 함수는 다음과 같습니다.

• push()
• emplace()
• pop()
• top()
• size()
• empty()

---

3-3. 동작 방식

예를 들어

push(1);
push(3);
push(5);

를 수행한 뒤

top();
pop();

을 반복하면

5
3
1

순서로 출력됩니다.

top()은 가장 위의 데이터를 확인하며,

pop()은 가장 위의 데이터를 제거합니다.

---

3-4. 내부 구현

std::stack은 추상 자료구조입니다.

실제 메모리에서는

• 내부 컨테이너(deque, vector, list)가 힙에 생성되고
• stack은 해당 컨테이너의 인터페이스만 제한하여 제공합니다.

즉,

stack 자체가 특별한 메모리 구조를 가지는 것이 아니라,

기존 컨테이너를 이용해 LIFO 동작만 제공하는 어댑터(Adapter)입니다.

---

4. std::queue

다음은 큐(Queue)입니다.

큐는

FIFO (First In, First Out)

자료구조입니다.

즉,

먼저 들어온 데이터가 먼저 나갑니다.

예를 들어

push(1)
push(3)
push(5)
push(7)

이라면

삭제되는 순서는

1
3
5
7

입니다.

---

4-1. std::queue

std::queue는

std::queue<T, Container>

형태로 제공됩니다.

기본 컨테이너는

std::deque

이며,

std::list도 사용할 수 있습니다.

하지만 std::vector는 사용할 수 없습니다.

주요 함수는

• push()
• emplace()
• pop()
• front()
• back()

입니다.

---

4-2. 동작 방식

예를 들어

push(1);
push(3);
push(5);

을 수행하면

• front()는 1
• back()은 5

를 반환합니다.

이후

pop();

을 호출하면

가장 먼저 들어온

1

이 제거되고,

다음 원소인

3

이 새로운 front()가 됩니다.

---

4-3. 실무에서의 활용

강의에서는 성능이 매우 중요한 상황이라면

std::stack이나 std::queue 대신

직접 구현하는 방법도 소개합니다.

예를 들어

• std::vector
• std::array

를 내부 저장소로 사용하여

직접 스택이나 큐를 구현할 수도 있습니다.

특히 큐는

• Circular Queue
• Circular Buffer
• Ring Buffer

등의 형태로 구현하면

메모리 지역성이 좋아지고,

포인터 추적도 최소화할 수 있어 성능상 유리합니다.

---

최종 정리

이번 강의에서는 std::forward_list, std::vector, std::list, std::stack, std::queue를 차례대로 살펴보았습니다.

• **std::forward_list**는 단일 연결 리스트로 메모리 사용량이 적지만, 마지막 삽입과 랜덤 액세스를 지원하지 않습니다.
• **std::list**는 삽입과 삭제는 빠르지만 캐시 효율이 낮아 실제 성능에서는 std::vector보다 불리한 경우가 많습니다.
• std::vector는 연속된 메모리를 사용하여 캐시 효율과 병렬 처리 측면에서 뛰어나므로, 실무에서는 대부분 std::vector를 사용하는 것이 권장됩니다.
• **std::stack**은 LIFO(Last In, First Out), **std::queue**는 FIFO(First In, First Out)를 제공하는 컨테이너 어댑터이며, 내부적으로는 std::deque 등을 이용해 구현됩니다.
• 성능이 매우 중요한 환경에서는 std::vector나 std::array를 기반으로 직접 스택이나 큐를 구현하는 방법도 고려할 수 있습니다.

 

 

 

 

 

스택(Stack)과 큐(Queue)

이번 영상에서는 스택(Stack)과 큐(Queue)에 대해 알아보겠습니다.

먼저 여기서 말하는 스택(Stack)은 메모리 영역 중 하나인 스택 메모리(Stack Memory)와는 다른 개념입니다. 오늘 설명드리는 스택은 데이터 구조(Data Structure)인 스택입니다.

1. 스택(Stack)

스택은 LIFO(Last In, First Out), 즉 나중에 들어온 데이터가 가장 먼저 나가는 방식의 데이터 구조입니다.

예를 들어 데이터를 차례대로 1, 3, 5 순서로 넣었다면, 데이터를 꺼낼 때는 5, 3, 1 순서로 나오게 됩니다.

std::stack

C++에서는 std::stack을 사용할 수 있습니다.

• <stack> 헤더에 정의되어 있습니다.
• 템플릿 매개변수로 데이터 타입과 내부 컨테이너를 지정할 수 있습니다.
• 기본 컨테이너는 std::deque입니다.

흥미로운 점은 내부 컨테이너를 사용자가 변경할 수 있다는 것입니다. 기본적으로는 std::deque를 사용하지만, std::list를 사용할 수도 있습니다. 반면 std::vector는 std::stack의 내부 컨테이너로도 사용할 수 있습니다.

주로 사용하는 함수는 다음과 같습니다.

• push() : 데이터 삽입
• pop() : 데이터 제거
• top() : 가장 위에 있는 데이터 확인

코드 동작 예시

간단한 예제를 살펴보겠습니다.

먼저 std::stack<int>를 하나 생성한 뒤 push()를 이용해 1, 3, 5를 차례대로 넣습니다.

그다음 top()을 호출하면 가장 마지막에 들어간 5가 출력됩니다.

이후 pop()을 호출하면 가장 위의 원소가 제거되고, 다시 top()을 호출하면 이번에는 3이 출력됩니다.

이 과정을 반복하면 마지막에는 모든 원소가 제거되고, size()를 통해 스택의 크기가 0이 된 것을 확인할 수 있습니다.

이처럼 스택은 LIFO(Last In, First Out) 특성에 따라 항상 가장 마지막에 들어온 데이터부터 처리됩니다.

메모리 관점

참고로 스택이라는 데이터 구조는 추상적인 개념입니다.

실제로 std::stack이 사용하는 데이터는 내부 컨테이너인 std::deque나 std::list 등에 저장되며, 이러한 컨테이너는 일반적으로 힙(Heap) 영역에 메모리를 할당하여 데이터를 관리합니다.

즉, 이름은 스택이지만 메모리의 스택 영역에 저장되는 것은 아니라는 점을 기억하시면 됩니다.

---

2. 큐(Queue)

이번에는 큐(Queue)를 살펴보겠습니다.

큐는 FIFO(First In, First Out), 즉 먼저 들어온 데이터가 먼저 나가는 방식의 데이터 구조입니다.

예를 들어 1, 3, 5, 7을 차례대로 넣었다면 데이터를 꺼낼 때도 1, 3, 5, 7 순서대로 처리됩니다.

std::queue

C++에서는 std::queue를 사용할 수 있습니다.

• <queue> 헤더에 정의되어 있습니다.
• 템플릿 매개변수로 데이터 타입과 내부 컨테이너를 지정할 수 있습니다.
• 기본 컨테이너는 std::deque입니다.

std::queue는 내부 컨테이너로 std::deque 또는 std::list를 사용할 수 있으며, std::vector는 사용할 수 없습니다.

주요 함수는 다음과 같습니다.

• push() : 데이터 삽입
• pop() : 데이터 제거
• front() : 가장 앞의 데이터 확인
• back() : 가장 뒤의 데이터 확인

코드 동작 예시

간단한 예제를 살펴보겠습니다.

먼저 std::queue<int>를 생성한 뒤 push()를 이용해 1, 3, 5를 입력합니다.

그다음 front()와 back()을 출력하면 각각 1과 5가 출력됩니다.

이후 pop()을 호출하면 가장 먼저 들어온 1이 제거되고, front()는 3을 가리키게 됩니다.

다시 pop()을 호출하면 3이 제거되고, 이제 front()와 back() 모두 5를 가리키게 됩니다.

이처럼 큐는 FIFO(First In, First Out) 정책에 따라 항상 먼저 들어온 데이터부터 처리됩니다.

---

3. 직접 구현하는 스택과 큐

스택과 큐는 비교적 단순한 데이터 구조이기 때문에, 실제 프로젝트에서는 직접 구현하는 경우도 많습니다.

특히 성능이 중요한 상황에서는 std::stack이나 std::queue를 사용하는 대신, 내부적으로 배열(Array)이나 std::vector를 이용해 직접 구현하기도 합니다.

이렇게 구현하면 최대 크기를 직접 관리할 수 있고, 메모리 사용 방식도 원하는 형태로 최적화할 수 있습니다.

또한 템플릿을 활용하면 다양한 타입을 지원하는 범용적인 스택과 큐를 만들 수도 있습니다.

특히 큐는 직접 구현할 경우 Circular Queue(서큘러 큐), Circular Buffer(서큘러 버퍼) 또는 Ring Buffer(링 버퍼) 형태로 구현하는 경우가 많습니다. 모두 같은 개념을 의미합니다.

이러한 방식은 내부적으로 배열이나 std::vector를 사용하기 때문에 데이터 지역성(Data Locality)이 좋아지고, 동적 메모리 할당을 최소화할 수 있어 높은 성능을 얻을 수 있습니다.

나중에 기회가 된다면 std::vector, 배열, 그리고 템플릿을 활용하여 스택과 큐를 직접 구현하는 방법도 별도의 영상으로 자세히 다뤄보겠습니다.

---

이번에는 스택과 큐라는 가장 기본적인 데이터 구조를 살펴봤습니다.

비교적 쉬운 내용이라 짧지만, 앞으로 다양한 알고리즘과 자료구조를 학습할 때 매우 자주 등장하는 개념이므로 꼭 이해하고 넘어가시기 바랍니다.