자료구조 _ Queue 그리고 Stack

Queue는 무엇인가요?

큐는 줄 형태의 선입선출 자료구조입니다. 활용예시는 프린트 출력, 은행창구 번호표 대기, 너비우선탐색(BFS) 등이 있습니다.

 

enqueue : 데이터 추가

dequeue : 데이터 추출

시간복잡도는 둘 다 O(1)입니다.

 

 

array-based queue vs list-based queue

array-based queue : 배열 기반 큐는 선입선출 과정에서 남는 메모리가 생깁니다. 이는 circular queue로 해결할 수 있습니다.

 

*circular queue는 배열이 끝까지 차면 첫부분에 비어있는 공간으로 다시 채우기 시작하는 것을 뜻합니다. 만약 공간이 없어서 채울 수 없게 되면 dynamic array와 같은 방법으로 array의 크기를 늘려야 합니다.

 

 

 

list-based queue : 링크드 리스트 기반 큐는 메모리 재할당이나 낭비가 없습니다. 하지만 enqueue를 할 때마다 메모리 할당(memory allocation)을 해야하기때문에 전반적인 runtime이 느릴 수 있습니다.

 

 

+

deque(double-ended queue)는 양쪽으로 enqueue와 dequeue가 가능합니다.

priority queue는 시간 순서가 아닌 우선순위 순으로 dequeue할 수 있습니다.

 

 

 

Queue vs priority queue

우선순위 큐(priority queue)는 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

시간복잡도는 push, pop 모두 O(logn)입니다.

 

 

 

Stack은 무엇인가요?

스택은 쌓아올리는 형태의 후입선출 자료구조입니다. 시간 복잡도는 O(1)입니다. 활용예시는 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로가기), 깊이 우선탐색(DFS)등이 있습니다. (스택은 재귀적인 특성이 있습니다)