[자료구조] 큐와 스택

큐(queue)

큐는 선입선출의 자료구조로 인큐와 디큐의 시간복잡도가 O(1) 입니다. 주로 순서를 보장해주는 경우에 사용되며 큐를 통해 Cache, 프로세스 관리, 너비우선탐색 등을 구현할 수 있습니다.

이러한 큐는 배열이나 링크드 리스트로 구현할 수 있습니다.

 

> Array-Base / List-Base

Array-Base
배열을 이용해 큐를 구현하면, 인큐와 디큐 과정에서 남는 메모리가 생깁니다. 따라서 메모리의 낭비를 줄이기 위해 주로 원형 큐 형식으로 구현합니다. 또한 인큐가 계속 발생하면 고정된 배열 크기를 넘어가게 되어서 동적 배열과 같은 방법으로 배열의 size를 확장시켜야 합니다.
전반적으로 리스트를 이용하는 것보다 배열을 이요하는 것이 퍼포먼스가 더 좋지만, 최악의 케이스에는 resize를 해야하므로 훨씬 더 느릴 수 있습니다.

List-Base
리스트를 이용해 큐를 구현하는 경우엔 보통 싱글 링크드 리스트로 구현합니다. 인큐는 리스트의 append를 하는 것으로 구현되고, 디큐는 맨 앞의 원소를 삭제하고 first head를 변경하는 식으로 구현됩니다.
그러나 리스트를 이용하면 인큐를 할 때마다 메모리 할당을 해야하기 때문에 전반적인 런타임이 느릴 수 있습니다.

큐는 명령큐나 네트워크같이 특정한 상황에서 시스템이 딜레이 걸리는 경우나, 앞 명령이 처리되는 것을 대기하는 경우에서 사용할 수 있습니다.

큐의 개념을 좀 더 확장하면 양쪽에서 인큐와 디큐가 가능한 데큐(deque)와, 시간 순서가 아닌 우선순위가 높은 순서대로 출력할 수 있는 priority queue(우선순위 큐)가 있습니다.

 

C++ STL의 queue 클래스

C++ 표준라이브러리(STL)의 queue는 실제로 컨테이너 어댑터(container adapter)입니다. 즉, 실제 데이터를 저장하는 것은 다른 컨테이너가 하며, queue는 그 위에 추가적인 인터페이스를 제공합니다.

 

기본적으로 queue는 deque(double ended queue)를 기반으로 구현되어 있습니다. deque는 앞과 뒤에서 모든 원소를 추가하거나 제거할 수 있는 시퀀스 컨테이너이기에, 이러한 deque를 기반으로 한 queue의 push와 pop 연산이 O(1)의 시간복잡도로 수행될 수 있는것입니다.

 

내부 구현을 deque가 아닌 list나 vector를 기반으로하는 queue를 생성할 수도 있습니다. 하지만 이 경우에는 해당 컨테이너의 특성에 따라 queue의 성능이 달라질 수 있으므로 주의해야 합니다.

 

예를들어, list를 기반으로 한 queue도 가능하지만, list에서 임의의 위치에 접근하는 시간복잡도는 O(n) 이므로 비용이 많이 드는 작업이 될 수 있습니다.

 

반면, vector를 기반으로 한다면, push 연산은 O(1)의 시간복잡도가 걸리지만, pop 연산은 O(n)의 시간복잡도가 걸리게 됩니다. 따라서 일반적인 경우에는 deque를 사용하여 구현된 기본 STL queue를 사용하는 것이 가장 좋을 수 있습니다.

> pop이 O(n)의 시간복잡도가 걸리는 이유

vector는 pop_back을 사용하는 경우 O(1)의 시간복잡도를 가지지만, 중간이나 앞 부분에서 요소를 제거하면 그 뒤에 모든 요소들을 앞으로 한 칸씩 이동해야 하므로 O(n)의 시간복잡도를 갖는다.

이러한 vector를 기반으로 queue를 구현한다면 queue의 pop 연산에서 queue의 맨 앞에 있는 요소를 제거해야 하므로 O(n)의 시간복잡도가 걸리게 되는 것이다.

 

C++ STL의 deque 클래스

queue는 deque를 기반으로 만들어졌다고 했는데, 그렇다면 deque에서 push와 pop의 연산이 어떻게 시간복잡도 O(1)을 가질 수 있을까요?

 

deque는 내부적으로 여러 개의 고정 크기 배열들이 연결 리스트(linked list) 형태로 연결되어 있습니다. 이런 형태로 만들어졌기 때문에, 앞과 뒤에서 모두 원소를 추가하거나 삭제하는 연산이 가능한 것입니다.

연결된 각각의 배열은 독립적인 메모리에 할당되므로, 하나의 배열에서 원소를 추가하거나 제거해도 다른 배열들에는 영향을 주지 않습니다. 따라서 push_front, push_back, pop_front, pop_back 등의 연산은 O(1) 시간 복잡도를 가집니다.

 

큐와 우선순위 큐를 비교하여 설명해주세요.

큐는 시간 순서상 먼저 삽입한 데이터가 먼저 나오는 선입선출의 구조이고, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조입니다.

따라서 큐의 삽입/삭제 시간복잡도는 O(1)이고, 우선순위 큐의 삽입/삭제 시간복잡도는 O(log N)입니다.

우선순위 큐는 힙을 이용하여 구현할 수 있습니다.

 

힙

힙은 완전이진트리를 활용하는 자료구조로, 우선순위 큐의 구현과 일치합니다. 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 최대힙과, 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 최소힙이 존재합니다.

트리는 보통 링크드 리스트로 구현하지만, 힙은 트리임에도 불구하고 배열을 이용해 구현해야 합니다. 그 이유는, 새로운 노드를 힙의 마지막 위치에 추가할 때, 배열을 기반으로 구현해야 이 과정이 수월해지기 때문입니다.

 

> 인덱스로 보는 부모 자식 관계

완전이진트리의 특성을 활용하여 배열의 인덱스만으로 부모 자식 간의 관계를 정의합니다.
부모 노드 : n / 2
왼쪽 자식 노드 : 2n
오른쪽 자식 노드 : 2n + 1

 

대표적인 힙의 시간복잡도는 삽입/삭제가 각각 O(log N)입니다. 힙 트리의 높이가 log N인데, push와 pop을 했을 때 swap 하는 과정이 최대 log N번 반복되기 때문입니다.

 

최대힙 - push
1. 새로운 데이터를 push하면 힙의 맨 마지막 인덱스에 값을 저장한다.
2. 부모 노드의 값이 더 클 때까지 swap한다.

최대힙 - pop
1. 첫번째 인덱스에 저장되어 있는 루트 노드를 pop한다.
2. 마지막 인덱스에 저장되어 있는 값을 top(루트 노드)으로 옮긴다.
3. top 노드 값이 자식 노드보다 작다면 양쪽 자식 노드 중 더 큰 값과 swap 한다.
4. 자식노드가 더 작을때까지 swap 과정을 반복한다.

 

스택 (stack)

스택은 후입선출의 자료구조로 push와 pop의 시간복잡도가 O(1) 입니다. 스택을 통해 후위 표기법 연산이나 괄호의 유효성 검사, 깊이 우선 탐색 등을 구현할 수 있습니다. 

또한 스택을 이용해 함수가 스택프레임으로 제작되었고, 콜 스택에 의해 움직이므로 스택과 함수의 운영 구조는 동일합니다.

배열을 포함한 벡터나, 링크드 리스트로 구현할 수 있습니다.

재귀함수를 추적하거나 네비게이션으로 길을 찾고 그 길을 플레이어로부터 보여주는 방식 등등에 값을 뒤집는 상황에서 사용할 수 있습니다.

 

C++ STL의 stack 클래스

C++ STL의 stack은 컨테이너 어댑터로, deque를 내부 컨테이너로 사용하여 구현되었습니다. 실제로 자체적인 데이터 구조체를 갖지 않고 deque의 STL 컨테이너 위에서 작동하는 인터페이스 역할을 합니다.

queue와 마찬가지로 deque를 기반으로 구현되었고, deque가 아닌 list, vector를 지정하여 사용할 수도 있습니다.

 

스택 두개를 이용하여 큐를 구현해보세요.

큐의 인큐를 구현할 때 첫번째 스택을 사용하고, 디큐를 구현할 때 두번째 스택을 사용하면 스택 두개로 큐를 구현할 수 있습니다.

 

1. 인큐에 사용하는 스택을 인스택이라고 부르고, 디큐에 사용되는 스택을 아웃스택으로 부르도록 하자.
2. 인큐: 인스택에 push하여 데이터를 저장한다.
3. 디큐: 아웃스택이 비어있지 않다면 아웃스택을 pop하여 데이터를 출력한다.
3-1. 아웃스택이 비어있다면, 인스택에 있는 모든 데이터를 pop하고 아웃스택으로 push하여 데이터를 역순으로 넣어주고, 아웃스택에서 pop한다.

 

시간복잡도

인큐: 인스택에 push만 하면 되므로 O(1)

디큐: 최악의 경우, 아웃스택이 비어있으면 인스택에 있는 n개의 데이터를 옮겨줘야 하므로 O(n)

아웃스택이 비어있지 않은 경우엔 아웃스택 pop만 하면 되므로 O(1)

 

큐 두개를 이용하여 스택을 구현해보세요

1. 스택의 push에 사용되는 큐를 q1이라고 부르고 pop에 사용할 큐를 q2라고 부르도록 하자.
2. push : q1으로 인큐하여 데이터를 저장한다.
3. pop : q1에 저장된 데이터의 갯수가 1 이하로 남을때까지 디큐한 뒤, q2에 인큐한다.
3-1. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터가 q2에 옮겨진다.
3-2. q1에 남아있는 하나의 데이터를 디큐하여 pop의 결과로 반환해준다.
3-3. 다음에 진행될 pop을 위해 q1과 q2의 이름을 swap 한다.

 

시간복잡도

push : q1에 인큐만 하면 되므로 O(1)

pop : q1에 저장된 n개의 원소 중 n-1개를 q2로 옮겨야 하므로 O(n)