[자료구조] 큐(Queue)

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

1. 개요
2. 본문
3. Reference 

---

개요

꼭 알아둬야 할 자료 구조인 큐(Queue)에 대해서 한 번 정리해 보도록 하겠습니다.

해당 글은 1차적으로 코드 없는 알고리즘과 데이터 구조 책을 읽고, 개념을 익힌 뒤 패스트캠퍼스의 인강을 통해 재정리한 내용입니다.

---

본문

큐 구조

가장 먼저 넣은 데이터가 가장 먼저 나오는 구조입니다.

이를 줄여서 FIFO(선입선출) 또는 LILO(후입후출) 이라고 부릅니다.

이 중 FIFO 정책이 필요할 때 주로 사용합니다.

 

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

 

큐 관련 용어

• Enqueue : 큐에 데이터 삽입
• Dequeue : 큐에 데이터 제거

 

큐 구현 코드

라이브러리를 이용하여 일반 큐 구현

import queue

# queue 라이브러리를 이용하여 큐 자료구조 불러오기
data_queue = queue.Queue()

# 불러온 자료 구조에 1->2->3 순서로 집어넣기
data_queue.put(1)
data_queue.put(2)
data_queue.put(3)

# FIFO임으로 1이 출력
print(data_queue.get())

# 남아있는 요소는 2,3으로 2가 출력
print(data_queue.qsize())

라이브러리를 이용하여 LIFO 큐 구현

import queue

# queue 라이브러리를 이용하여 LIFO 큐 자료구조 불러오기
data_queue = queue.LifoQueue()

# 불러온 자료 구조에 1->2->3 순서로 집어넣기
data_queue.put(1)
data_queue.put(2)
data_queue.put(3)

# LIFO임으로 3이 출력
print(data_queue.get())

# 남아있는 요소는 1,2으로 2가 출력
print(data_queue.qsize())

 

라이브러리를 이용하여 우선순위 큐 구현

import queue

# queue 라이브러리를 이용하여 LIFO 큐 자료구조 불러오기
data_queue = queue.PriorityQueue()

# 불러온 자료 구조에 우선 순위 값을 지정하여 집어넣기
data_queue.put((1,"1순위 우선순위"))
data_queue.put((3,"3순위 우선순위"))
data_queue.put((2,"2순위 우선순위"))

# 우선순위 값이 1순위(낮은 숫자 우선)인 값이 출력
# 1, "1순위 우선순위" 가 출력됨
print(data_queue.get())

# 남아있는 우선순위 2,3번이 있음으로 2가 출력
print(data_queue.qsize())

 

라이브러리를 이용하지 않고 직접 일반 큐 구현

import queue

queue_list = list()

def enqueue(data):
  queue_list.append(data)

def dequeue():
  print(queue_list[0])
  queue_list.remove(queue_list[0])

def qSize():
  print(len(queue_list))

# enqueue로 1 -> 2 -> 3 삽입
enqueue(1)
enqueue(2)
enqueue(3)

# FIFO임으로 1 -> 2 출력
dequeue()
dequeue()

# 요소 3만 남았으로 1 출력
qSize()

 

큐의 종류

위에서 구현한 LIFO 큐, 우선순위 큐에 대한 내용들을 간단한게 정리해보았습니다.

• LIFO 큐 : 후입선출 개념의 자료 구조
• 우선순위 큐 : 데이터 삽입 시에 매겨지는 우선순위에 따라 큐가 처리되는 자료 구조

 

큐의 사용 용도

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됩니다.
  해당 부분은 별도로 CS 카테고리 부분에서 정리하겠습니다.

---

Reference

• 코드 없는 알고리즘과 데이터 구조
• 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online.