Queue & Stack

C++ STL에서 queue와 stack을 사용하면 동작 방법이 어떠냐는 후배의 물음에 대답할 수 없었기에 나름대로 정리 해보려한다. 나의 수준에서 바라보고 적는 글이기에 많은 부분에서 오류가 있을꺼라 예상하며 지적과 비판은 언제나 환영하는 마음으로 작성한다.

 

사용 방법이 아닌 동작이 어떻게 이뤄지는지는 한번도 생각해 본 적이 없고 검색해도 사용방법에 대해서만 나오기에 이번 기회에 자세히 알아보자.

 

STL에서는 Queue와 Stack은 Container Adapter로 전체적인 Container 클래스가 정의되어 있지 않고 Wrapper Container(기존 컨테이너)의 인터페이스를 제한하여 유저 접근을 통제한 컨테이너이다. 여기서 Wrapper Container는 기본적으로 SequenceContainer의 요구조건을 만족해야하고 반드시 back(), push_back(), pop_back() 인터페이스를 제공해야한다. Queue와 Stack은 기본적으로 deque를 WrapperContainer로 사용한다. 앞에 요구조건을 만족한다면 다른 것으로 대체하는 것도 가능하다. STL에서는 vector, deque, list가 요구조건을 만족한다.

 

기본적으로 Queue와 Stack 모두 Deque를 기반으로 만들어진 것이기 때문에 Deque에 대해서 먼저 알아보자.

Deque

Deque는 SequenceContainer로  double-ended queue라고도 하며 원소가 앞과 뒤 모두 추가될 수 있는 queue이다.

Vector와 구분되는 차이점은 vector의 경우 배열이 가득차면 새로운 메모리 블럭을 만들고 기존의 데이터를 복사한 다음 기존의 메모리 블럭을 제거하는데 deque의 경우 메모리가 가득차면 그저 새로운 메모리 블럭을 추가한다.

출처 : https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl

위 그림과 같이 실제 데이터를 가지고 있는 Chunk, 데이터를 보유한 Chunk을 관리해 주는 map, 맨 앞의 데이터 위치를 알려주는 begin(), 맨 뒤를 알려주는 end()로 구성되어 있다.

때문에 메모리 정책상 처음부터 끝까지 연속적인 메모리 공간이 아니므로 임의 접근 연산이 가능한것과는 별개로 포인터 연산을 통해 deque의 원소들을 안전하게 접근할 수 없다.

Queue

template<
    class T,
    class Container = std::deque<T>
> class queue;

 

원소를 deque(underlying container)의 뒤에만 push하고 앞에서만 pop하도록 제한한 것이다.

 

Stack

template<
    class T,
    class Container = std::deque<T>
> class stack;

원소를 deque(underlying container)의 뒤에만 push하고 뒤에서만 pop하도록 제한한 것이다.

 

 

참조

https://embeddedartistry.com/blog/2017/08/02/an-overview-of-c-stl-containers/

An Overview of C++ STL Containers - Embedded Artistry

 

https://marmelo12.tistory.com/305

[C++ STL] std::deque (시퀀스 컨테이너)

 

https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl

What really is a deque in STL?

 

https://godway1225.wordpress.com/2019/07/22/stl-deque-%EB%8A%94-%EC%99%9C-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%95%B4%EC%A0%9C%EB%A5%BC-%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94%EA%B1%B8%EA%B9%8C/

stl deque는 왜 메모리 해제를 하지 않는걸까?