[알고리즘(5)] Python으로 알아보는 큐(Queue)

출처: flacticon

 

[알고리즘 포스팅 순서]

1. 시간복잡도

2. 배열

3. 연결리스트

4. 스택

5. 큐

6. 트리

7. 그래프

8. 해쉬테이블

9. 정렬(선택, 버블, 삽입, 퀵, 힙, 병합)

10. 코테 대비 백준 문제 풀이 꿀팁

 

벌써 절반이나 왔다. 이번에 알아볼 자료구조는 큐(Queue)이다.

이는 나중에 많이 사용되니 기억해 둘 필요가 있는 중요한 개념이다.

 

[큐란?]

큐는 데이터가 삽입된 순서대로 삭제도 이루어지는 자료구조이다.

컴퓨터 운영체제에서 시스템 콜이 진행될 때에도 사용된다.

 

큐를 한국말로 하면 '줄, 대기줄'을 의미한다.

예로 들면 게임 롤(LoL)에서 '큐를 돌린다'라는 관용 표현에서도 쓰인다.

매표소에서 줄을 선 순서대로 표를 구매하는 모습으로도 이해할 수 있다.

 

이를 FIFO (First In First Out) 라고 하는 선형구조(유한 순서 리스트라고도 함)라고 한다.

가장 먼저 들어온 데이터가 가장 먼저 나간다는 뜻이다.

(마치 내 기억력처럼?)

 

이는 LIFO구조인 스택(Stack)과 정반대인 특징을 가진다.

 

[구조와 기능]

1. 기본 구조

이해를 위해 기본 구조는 이렇게 생겼다.

 

2. front와 rear

큐에서는 제일 앞에 있는 노드를 front라고 하며,

마지막에 들어간 노드를 rear (or back)이라 한다.

 

3. enqueue와 dequeue

enqueue: 가장 마지막에 자료를 넣는 것(rear이 됨)으로 위의 그림을 보면 연결 리스트의 append와 같다.

dequeue: 가장 먼저 들어간 자료(front)를 꺼내는 것으로 연결 리스트의 popleft과 같다.

 

4. 구현 방법

큐를 구현하는 방법은 두 가지가 있다.

(1) 배열: 구현이 쉬움, 크기가 정적임 (but, 파이썬의 경우 배열이 리스트와 같기 때문에 똑같음)

(2) 연결리스트: 크기가 동적임, 추가 메모리 필요

 

5. 종류

선형큐, 원형큐(환원큐라고도 함), 우선순위큐(힙큐라고도 함)가 있다.

선형큐는 지금까지 설명한 일반적인 큐이고

원형큐는 front와 rear가 연결되어 있는 큐라고 보면 된다.

원형큐(Circle Queue)가 궁금하다면 참고문헌 4. 블로그를 보면 된다.

우선순위큐는 각 데이터에 우선순위가 매겨져서 dequeue가 될 때 우선순위를 따지는 것을 의미한다.

우선순위큐(Priority Queue/Heap Queue)가 궁금하다면 참고문헌 5. 블로그를 보면 된다.

원형큐

우선순위큐

 

 

[코드]

다음 기능이 있는 일반 큐를 구현하였다.

1. push(Data data): queue에 data 삽입
2. pop(): queue의 front에 있는 원소 삭제
3. front(): queue의 front에 있는 원소 출력 (삭제가 아니다)
4. rear(): queue의 rear에 있는 원소 출력

class Queue:
  def __init__(self):
    self.queue = []

  def push(self, data):
    temp = [data]
    self.queue = temp + self.queue
    print(self.queue)

  def pop(self):
    self.queue.pop()

  def front(self):
    print(self.queue[-1])

  def rear(self):
    print(self.queue[0])



## __main__ ##
queue = Queue()
queue.push(5)
queue.push(10)
queue.push(15)
queue.push(20)
queue.front()
queue.pop()
queue.pop()
queue.push(25)
queue.front()
queue.rear()

-> main문을 실행하면 다음과 같은 결과가 나온다.

 

 

끄읏

 

[참고문헌]

1. 위키독스: https://wikidocs.net/192523

2. 블로그: https://yoongrammer.tistory.com/46

3. 블로그: https://donggu1105.tistory.com/163

4. 블로그: https://codingsmu.tistory.com/123

5. 블로그: https://velog.io/@mein-figur/Python%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq