CS 비전공자의 IT 기업 면접 뽀개기 - (1) Data Structure - Queue

자료구조(Data structure)는 데이터들의 모임, 관계, 함수, 명령 등의 집합을 의미한다. 즉, 처리하고자 하는 데이터들이 모여 있는 형태, 혹은, 처리하고자 하는 데이터들 사이의 관계 (수직, 상하, 일방적, 상호 등)를 정의한 것, 혹은, 데이터들을 사용하기 용이하게 저장해 놓은 형태라고 볼 수 있다.

자료구조를 잘 선택하면 사용하는 메모리와 시간, 공간적 효율성을 확보할 수 있다.

Queue

Stack과 비슷하지만, 먼저 들어간 자료가 먼저 나오는 선입선출(FIFO) 구조이다. 큐에 새로운 데이터가 들어오면 enqueue, 데이터가 삭제될 때는 dequeue가 된다.

Queue의 종류로는 Circular queue, Priority queue가 있다.

ADT

• front(head): 데이터를 deque할 수 있는 위치.
• rear(tail): 데이터를 enque할 수 있는 위치
• is_empty() -> bool
• enqueue(data) -> None: 삽입
• dequeue() -> data: 삭제
• peak() -> data or 1: 맨 위의 값을 출력

Python 구현

파이썬에서는 collections.deque로 구현되어 있다. Queue.queue도 있지만, 멀티 쓰레드를 위한 환경이기 때문에 매우 느리기에 코딩 테스트에서는 권장하지 않는다.

다음은 List로 구현한 코드이다.

그러나 dequeue시에 pop(0)를 하면 O(N)의 시간복잡도를 갖아 상당히 느려진다. 반면 collections.deque의 경우 O(1)이 된다. 이는 doubly linked list로 이루어져 있기 때문이다.

다음은 linked list를 이용하여 구현한 모습이다.

Reference

초보몽키의 개발블로그

Daim’s blog

Circular Queue

방금전에 보았듯 list로 queue를 구현할 경우 매우 느리다. 이는 데이터가 dequeue 될 경우 데이터의 idx가 한 칸씩 이동하기 때문이다. 이를 극복하는 방법으로는 Circular queue가 있다.

마지막 index에서 다음 index로 넘어가면 IndexError가 발생하게 되는데, 이를 방지하기 위해 (index + 1) % len(arr)를 이용하여 index를 순환 시킨다. 따라서 max index와 index가 같게 되면, 다시 0으로 index가 순환된다. 이는 배열의 특성인 제한된 길이에 맞게 고안된 것이다.

• 처음에 공간을 생성한데로 활용할 수 있음
• 따라서 enqueue가 별로 없으면 공간이 낭비됨
• 크기를 늘리기가 힘듬

Python 구현

다음은 linked list를 활용하여 구현한 모습이다.

생성자에서 max를 받아 queue를 max 길이만큼 초기화한다. 그리고 현재 front/rear의 index를 담을 변수를 초기화한다. 초기 front/rear의 index는 0이다.

index는 앞서 설명했듯 (index + 1) % len(arr)씩 움직인다. 따라서 최대 사이즈가 된다면 0으로 다시 돌아가게 된다.

enqueue가 발생하면 rear만 움직인다. rear에서 한 칸((index + 1) % len(arr)) 이동한 index에 데이터를 추가한다. 그리고 추가한 데이터는 새로운 rear가 된다. 만일 queue가 꽉 찼을 경우 에러를 발생시킨다.

dequeue가 일어나면 front를 움직인다. 현재 front는 None으로 바꾸고, front는 한 칸((index + 1) % len(arr)) 이동한다. 만일 queue가 비었다면 에러를 발생시킨다.

front와 rear가 같으면 큐가 비어있다. 따라서 이를 이용하여 is_empty()를 구현한다.

rear의 바로 다음이 front이면 큐는 꽉 찬 것이다. 따라서 이를 이용하여 is_full()을 구현한다. 혹은, size를 따로 지정한 후,

Reference

Daim’s blog

Study and Share IT

Programming PEACE

위키피디아: Circular buffer

Priority Queue

우선순위 큐는 FIFO의 특성을 갖는 일반적인 큐와는 다르게 deque시에 우선 순위에 따라 먼저 제거하는 구조이다. 따라서 내부적으로 정렬하는 구조를 갖고 있어야 한다. 그러나 연결리스트나 array로 구현하게 될 경우 정렬을 위해 빈번하게 수정해야 하므로 heap을 이용하여 구현한다.

Priority 큐는 Dijkstra 알고리즘, Huffman 코딩, Prim 알고리즘 등 다양한 알고리즘에서 활용되며, python에서는 heapq 모듈을 통해 구현되어 있다.

Python 사용

데이터를 삽입할 때 priority를 통해 우선순위를 함께 삽입한다.

Refrence

Engineering Blog by Dale Seo

Daim’s blog