Stack, Queue

Stack

스택 ADT 의 주요 연산은 삽입 시 collection의 top(위)에 추가하는 push 연산과 삭제 시 collection 의 top(위)에 값을 삭제하는 pop d연산이 있다. 이 연산으로 인해 우리는 Stack(스택)을 LIFO(Last In First out) 자료구조라고 부른다.

 

디자인 선택

스택 자료구조를 디자인 하기 위해 Linked List 혹은 동적 Array 를 활용할 수 있다.

LinkedList를 활용하는 경우 push 연산 시 head 에 추가하고(insert(v, i)) pop 연산 시 head를 제거하는(remove(0)) 연산을 통해 O(1) 시간 복잡도로 구현할 수 있다.

동적 배열을 활용하는 경우 배열의 마지막 index 에 push 연산 시 추가, pop 연산 시 삭제하는 식으로 역시 O(1) 시간복잡도로 구현할 수 있다.

 

스택 자료구조 활용

스택 자료구조를 활용하는 대표적인 예시로는 

• 괄호 매칭: 수학 표현식에서 괄호 (), {}, [] 를 사용하는 경우 서로의 짝을 찾기 위해 사용될 수 있다.
• 후위 표기법(Postfix Expression): 후위 표기법으로 표현된 표현식이 주어진 경우 연산을 스택을 활용해 연산할 수 있다.(2 3 + 4 * -> (2 + 3) * 4 )

 

Queue

큐 자료구조는 아이템의 순서를 유지하는 컬렉션 ADT로 주요 연산으로는 컬렉션 앞에 아이템을 추가하는 enqueue 연산과 컬렉션 위에 아이템을 삭제하는 dequeue 연산이 있다.

 

디자인 선택

Queue 자료구조를 구현하기 위해 Linked List 와 Array 를 활용할 수 있다.

배열이 Linked List 보다 메모리에서 차지하는 크기가 작고 메모리에 연속적인 배치로 인한 성능적으로 우수하다는 점으로 장점이 많은 자료구조이지만 큐에 있어서는 문제가 있다. 배열을 활용하는 경우 발생하는 문제점을 설명함으로써 큐를 구현할 때 Linked List 를 많이 사용하는 지를 설명한다.

 

1. dequeue 연산 시 시간 복잡도 O(N)

배열을 이용하여 큐를 구현 시 dequeue 연산에서 인덱스 0 에 위치한 값을 삭제하기 때문에 배열에 남아있는 값들의 위치를 한 칸씩 앞으로 이동시켜야 하는 문제가 발생한다. 배열의 모든 값을 이동시켜야 하므로 시간복잡도는 O(N)이다. 이를 해결하기 위한 방법으로 값들을 이동시키지 않기 위한 큐의 앞을 가리키는 데이터를 추가한다.

 

2. 배열의 앞 쪽에 빈 공간이 많아짐

배열의 앞을 가리키는 인덱스 데이터로 인해서 데이터를 이동시킬 필요는 없어졌지만 배열의 앞의 공간이 비어있게 되는 문제가 발생한다. 

큐를 오래동안 사용하게 된다면 이 큐의 사이즈는 터무니없이 커지게 된다. 이를 해결하기 위해서 크기가 고정된 배열을 사용하고 배열의 끝에 도달 시 0번째 인덱스부터 다시 추가될 수 있게 한다.

 

3. 배열이 꽉차는 경우 Resize

고정된 사이즈의 배열이기 때문에 배열의 공간이 없을 수도 있다. 이 경우 resize를 해야 하는데 이 연산 중에 데이터 복사가 필히 일어나 연산 성능이 오래 걸린다. 그리고 실제 큐에 포함된 값의 크기보다 배열의 크기가 커 메모리 공간을 더 많이 차지할 수 밖에 없다.

 

Linked List 로 구현을 한다면 enqueue, dequeue 연산 모두 O(1) 시간복잡도 안에 해결할 수 있다. 데이터를 추가할 때마다 Vertex를 추가하기 때문에 resize 시 데이터를 복사하거나 자료구조의 크기 실제 삽입된 데이터의 크기보다 월등히 큰 문제가 발생하지 않는다.

 

추가로 스택 2개로 이용하여 큐를 구현할 수도 있다.

입력용 스택과 출력용 스택을 구분한다. enqueue 시 입력용 스택에 데이터를 삽입한다. dequeue 시 출력용 스택을 확인하여 비어 있다면 입력용 스택의 값들을 모두 꺼내 출력용 스택에 넣고 top의 값을 삭제한다. 출력용 스택에 비어 있는 경우를 제외하고는 enqueue, dequeue 연산 모두 O(1) 시간복잡도를 갖는다.

 

큐 자료구조 활용

그래프 탐색 알고리즘 중 BFS(Breathe-First Search) 에서 큐를 활용할 수 있다.

 

Double-Ended Queue (Deque)

덱(Double-Eneded Queue, 일명 Deque) 은 head 에 삽입하고 tail에서 꺼내 삭제하는 큐와 달리 head, tail 상관없이 삽입과 삭제가 가능한 자료구조이다. 이중 연결 리스트(Doubly Linked List) 을 이용하여 구현이 되어 head, tail에 삽입 및 삭제하는 연산의 시간 복잡도는O(1) 이다.

 

덱 자료구조 활용

덱은 0/1 가중치를 갖는 그래프 탐색에서 가장 짧은 거리(shortest path)를 찾는 문제(변형 bfs)에서 활용할 수 있다.