자료구조 큐(Queue, 백준 알고리즘 2164번)

♣ Queue 개념

큐는 데이터를 보관하는 컨테이너이다. 먼저 입력된 데이터가 먼저 제거되므로 '선입선출'이라고 한다. 대기열은 앞과 뒤에 두 개의 끝이 있으며 항목은 후면에서 입력되고 전면에서 제거된다. 

Rear는 대기열 내부에 항목이 삽입되는 지점을 나타내고, Front는 대기열에서 항목이 제거되는 지점을 나타낸다. 

큐에서 항목은 순서대로 제거되고 사이의 항목을 제거할 수는 없다. 

 

파이썬에는 두 가지 형태의 큐가 존재한다. 

 

1. 선입선출 큐

먼저 들어가는 요소가 가장 먼저 나온다. 이를 사용하려면 큐 모듈에서 Queue 클래스를 호출해야 한다. 

 

2. 후입선출 큐

마지막으로 입력된 요소가 가장 먼저 나온다. 이를 사용하려면 대기열 모듈에서 LifoQueue 클래스를 호출해야 한다. 

 

FIFO queue

LIFO queue

 

 

♣ Queue와 LifoQueue 에서 사용하는 메서드

- put(item): queue 안에 항목 넣기

- get( ): 대기열에서 항목 반환하기

- empty( ): 대기열이 비어있으면 true를 반환하고 항목이 있으면 false 반환하기

- qsize( ): 큐의 크기 반환하기

- full( ): 큐가 가득 차면 true를 반환하고 그렇지 않으면 false 반환하기

 

 

♣ 백준 알고리즘 2164번

 

1부터 N까지의 카드가 있을 때 제일 위에 있는 카드를 버리고, 그 다음 제일 위에 있는 카드를 맨 아래로 옮긴다. 

이 활동을 남은 카드가 1장이 될 때까지 반복한다. 

 

 

♣ Queue를 이용한 문제 해결

 

Queue 클래스를 이용하여 선입선출 queue를 정의하고 for문을 이용하여 queue에 숫자를 집어넣었다.

그리고 get 메서드를 이용하여 q1의 사이즈가 1이 될 때까지 맨 위의 숫자를 제거하고, 그 다음 위에 오는 숫자를 맨 뒤로 집어넣기를 반복하였다.

 

하지만 위의 코드는 시간 초과가 난다. 왜 그런가 찾아보았더니 Queue 클래스는 시간을 많이 잡아먹는다고 한다. 따라서 이를 대신하여 queue를 사용할 수 있는 방법을 찾았다. 

 

 

♣ deque를 이용한 문제 해결

 

deque는 스텍과 큐의 기능을 모두 가진 객체로, 출입구를 양쪽에 가지고 있다. deque가 Queue 클래스보다 시간복잡도가 훨씬 작다. 

Queue와 다르게 popleft 메서드를 사용하여 맨 왼쪽 요소(카드로 치면 맨 위에 있는 카드)를 제거하고, 그 다음 맨 뒤에 있는 카드를 append 메서드를 이용하여 맨 오른쪽에 삽입하였다. 

 

자료구조를 왜 공부해야 하는지 알 수 있는 문제였다. 아직 헷갈리는 자료구조가 많은데 앞으로 계속 공부하면서 정리해야겠다. 

♣ 참고 자료

Queu(큐) 

https://www.entity.co.kr/entry/510-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%81%90Queue-FIFO-LIFO-%EC%98%88%EC%A0%9C

5.10 파이썬 큐(Queue) : FIFO, LIFO 예제

deque(데크)

https://dongdongfather.tistory.com/72

[파이썬 기초] 스택과 큐의 기능을 한번에 deque