파이썬 알고리즘 기초 - 큐(Queue)

이번 시간에는 '큐' 라고 하는 데이터 구조를 다뤄 보겠습니다. 

그림으로 먼저 보겠습니다. 

직사각형 타일이 데이터라고 생각하시면 됩니다. 

 

 

출처: http://www.stoimen.com/blog/2012/06/05/computer-algorithms-stack-and-queue-data-structure/

'큐'를 표현하는 그림들은 많이 있습니다. 

데이터를 하나하나 넣었습니다. 

 

앞으로 여러 데이터 구조를 살펴볼 것입니다.

각 구조마다 핵심적인 특성을 말하는 약어가 있습니다. 

핵심은 FIFO(First In First Out) 입니다.  LILO(Last-In, Last-Out) 랑 같은 의미입니다. 보통 FIFO 로 많이 얘기합니다.

 

위 그림을 보면 31이라는 데이터가 제일 먼저 들어갔고 제일 우측에 있습니다. 입구는 insert 출구는 delete로 위 그림에는 나와 있는데요. 6개의 데이터를 넣었는데 제일 먼저 들어간 31이 제일 먼저 나오는 특성을 갖고 있는 것이 '큐'입니다.

음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 같습니다.

 

다른 그림을 보죠.

 

출처: https://velog.io/@pa324/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Queue%ED%81%90-udjxr0hb3x

똑같은 원리를 설명하는데 약간  더 전문적으로 얘기 해보겠습니다. 

큐에 데이터를 넣는 것을 Enqueue 라고 합니다. 큐에서 데이터를 꺼내는 것을 Dequeue 라고 합니다. 

 

데이터가 들어오는 위치는 뒤쪽에 있으며, 뒤쪽을 Rear 또는 Back, Tail 이라고 하며, 데이터가 나가는 위치는 앞쪽에 있으며, 앞쪽을 Front 또는 Head 라 한다. 데이터를 입력하는 동작을 Enqueue, 제거하는 동작을 Dequeue라고도 합니다. 

 

아래와 같은 큐를 예로 들겠습니다.

 

head 라는 것은 먼저 들어온 데이터 있고 tail 이라는 것은 가장 나중에 데이터를 뜻합니다. 

여기서 57이라는 데이터를 Enqueue 해보겠습니다.

 

tail 이 57로 바뀌었습니다. 가장 마지막에 들어온 데이터니깐 '꼬리'겠죠? 

 

이번에는 Dequeue를 적용해보겠습니다. 

 

91이 사라지고, 71이 head 가 되었습니다. 한 번 더 해보겠습니다.

 

이제 큐가 어떤 식으로 데이터를 넣고, 삭제하는 지 감이 오시나요? 

 

https://visualgo.net/en/list

VisuAlgo - Linked List (Single, Doubly), Stack, Queue, Deque

감이 안 오신다면 위 링크에 들어가셔서 해당 데이터타입을 눌러서 왼쪽 하단에 하늘색 버튼에 커서를 옮겨서 말한 기능을 직접 해보시면 더 이해가 잘 될겁니다 :) 

 

자, 이제 파이썬으로 구현 해보겠습니다. 

 

1) FIFO 

 

먼저 queue라고 하는 라이브러리를 이용해서 구현해보겠습니다. 

아마 코딩테스트할 때는 이러한 자료구조 라이브러리가 사용되는지는 잘 모르겠지만, 이 포스팅은 그 부분은 고려하지 않습니다. 

마지막에는 라이브러리 없이 구현을 해볼 것입니다. 

 

큐라고 하는 것은 일반적으로 FIFO의 특성을 갖고 있지만 다른 특성을 가진 큐도 있습니다. 우선 위에서는 그냥 '큐'를 구현했습니다. 그냥 큐를 인스턴스 화 하시면 FIFO 의 특성을 가진 큐가 생깁니다. enqueue 는 put 이라는 메서드로 dequeue 는 get 이라는 메서드로 실행됩니다. 'apple'이 먼저 입력되었고 출력도 먼저 되면서 FIFO 가 잘 실행되는 것을 확인할 수 있습니다. 

 

2) LifoQueue()

(Last-in, First-out)

그대로 이해하시면 됩니다. 마지막에 들어온 데이터가 먼저 나가는 구조입니다. 뭔가 익숙하시죠? 

나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨) 로 이해하시면 됩니다~

 

 

다 똑같습니다. 인스턴스화 할 때 이름만 LifoQueue() 로 객체화 시켜주면 됩니다. 

 

3) PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

이번에는 데이터를 넣어줄 때, 튜플의 좌측(콤마 앞)에 우선순위의 숫자를 넣어줍니다.

우선순위에 따라서(=숫자가 낮을수록 먼저) 데이터를 꺼냅니다.

 

4) 리스트 변수로 FIFO 큐 메서드인 Enqueue, Dequeue 구현해보기

 

먼저 함수로 바로 만든 다음,

리스트에 원소를 넣는 append 와 데이터를 빼내는 pop 을 이용할 수 있습니다.

 

다른 방법은 dequeue에서 리스트의 인덱싱을 사용해서 구현하는 건데요. 

첫 번째 원소를 따로 변수로 만들어준 다음 리스트에서는 이를 제거하고 return 해주는 방법도 있습니다. 

 

이상 데이터 구조 '큐'를 다뤄보았습니다. 

 

 

이번 포스팅은 

패스트캠퍼스 온라인 강좌인 '알고리즘 기술면접 완전 정복'을 참고 했습니다. 

감사합니다 :)

 

 

--참고--

 

https://ian90.tistory.com/52