std::deque는 느리다. (feat. Queue and Deque implementations using two stacks: concepts and applications)

std::deque는 청크 단위로 메모리를 할당하고, 이로 인해 캐시히트가 떨어지고 덱을 여러 개 선언했을 때 메모리를 엄청나게 많이 잡아 먹는다는 단점이 있다.

std::stack과 std::queue는 기본 컨테이너로 std::deque를 사용한다. (https://en.cppreference.com/w/cpp/container/stack) (https://en.cppreference.com/w/cpp/container/queue)

따라서 STL의 스택과 큐, 덱은 모두 느리고, 메모리를 많이 먹는다는 단점을 공유한다.

실제로 필자는 과거에 std::queue를 여러 개 선언하여 메모리 초과를 받는 억까를 당한적이 있다. (https://codeforces.com/contest/1896/submission/234266177)

이 글에서는 std::stack, std::queue, std::deque의 이러한 비효율적인 구현을 해결하기 위한 방법을 알아보겠다.

 

1. std::stack

sol1. std::stack<T>를 사용하는 대신, std::stack<T, std::vector<T>>를 사용한다.

그냥 내부 컨테이너를 벡터로 바꾸면 해결된다.

sol2. std::stack<T>를 사용하지 않는다.

std::vector<T>가 std::stack<T>의 모든 기능을 제공하기 때문에, 모든 스택을 벡터로 대체 할 수 있다.

 

2. std::queue, std::deque

큐를 스택(벡터) 2개로 구현하는 것은 매우 간단하다.

두 개의 스택 head, tail을 관리하는데, head의 top이 맨 앞으로 오고, tail의 top이 맨 뒤로 오게 두 스택을 붙여 놓으면 된다.

push는 그냥 tail 스택에 원소를 집어 넣으면 되고, pop은 head가 비어 있지 않다면 head에서 원소를 하나 뽑고, head가 비어있다면 tail의 원소들을 전부 head로 옮기는 작업을 수행한 후 head의 원소를 하나 뽑으면 된다. (https://232-aka-pretty-pi.tistory.com/28)

이렇게 구현된 큐는 당연히 amortized O(1)에 동작한다.

 

덱도 비슷하게 구현할 수 있다. head, tail중 한 스택이 비어있는데 그 스택이 있는 방향에서 pop을 해야한다면, 반대쪽 스택의 반을 잘라서 비어있는 스택을 채우면 된다. (https://232-aka-pretty-pi.tistory.com/27)

이렇게 구현된 덱도 당연히 amortized O(1)이다. push 연산은 말할것도 없이 O(1)이고, 스택을 반으로 자르는 연산을 생각해보면, 만약 스택을 반으로 가를 때 그 크기가 S라면, O(S)만큼의 연산을 해야하고, 스택의 크기가 각각 floor(S / 2), ceil(S / 2)가 될 것이다. 따라서 다시 스택을 반으로 가르는 연산을 하기 위해서는 최소한 S / 2번 정도의 pop(Front or Back) 연산이 일어나야 하므로 amortized O(1)으로 덱이 작동한다. 

 

응용 : 결합법칙이 성립하는 어떠한 이항연산 *에 대해 현재 큐나 스택의 원소가 a[0], ..., a[n - 1]일 때 a[0] * a[1] * ... * a[n - 1]을 관리하는 자료구조를 만들 수 있다. (https://232-aka-pretty-pi.tistory.com/18) (https://232-aka-pretty-pi.tistory.com/26)

 

3. 큐 2개로 스택을 구현?

큐 2개로 스택을 구현할 수도 있다고 주장하는 블로그 글을 몇 개 봤는데, 

다들 push나 pop 중 적어도 하나는 O(N)으로 구현 해 놓은 것 같다.

이런 똥같은 구현은 응용할 곳도 없는 것 같은데 왜 있는지 모르겠다.