[자료구조] 큐(Queue)란?

Posted on | In
큐의 개념과 구조. 큐의 용어와 라이브러리. 큐의 예제와 파이썬 리스트로의 구현

큐(Queue)란?

  • 큐는 배열과 함께 가장 쉽지만, 컴퓨터에서 핵심적인 운영체제와 인터넷의 네트워크 기능에도 많이 쓰인다.

구조

  • 큐는 줄을 서는 행위와 유사하다.
  • 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조이다.
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대이다.

용어

  • Enqueue: 큐에 데이터를 넣는 기능이다.
  • Dequeue: 큐에서 데이터를 꺼내는 기능이다.

라이브러리

  • 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 를 제공한다.
  • 프로그램에 따라 적합한 자료구조를 사용한다.
    • Queue(): 가장 일반적인 큐 자료구조이다.
    • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(스택 구조)이다.
    • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터를 출력한다.

Queue()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import queue

data_queue = queue.Queue()


# 삽입
data_queue.put("funcoding")
data_queue.put(1)


# 사이즈 확인
data_queue.qsize()
'''
2
'''


# 추출
data_queue.get()
'''
'funcoding'
'''

LifoQueue()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
data_queue = queue.LifoQueue()


data_queue.put("funcoding")
data_queue.put(1)


data_queue.qsize()
'''
2
'''


data_queue.get()
'''
1
'''

PriorityQueue()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
data_queue = queue.PriorityQueue()


data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "china"))


data_queue.qsize()
'''
3
'''


data_queue.get()
'''
(5, 1)
'''


data_queue.get()
'''
(10, 'korea')
'''

용도

  • 운영체제에서 멀티 테스킹을 위해 프로세스 스케쥴링을 구현하기 위해 많이 사용된다.

구현

  • 파이썬의 리스트로 구현한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
queue_list = list()

def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data


for i in range(10):
    enqueue(i)


len(queue_list)
'''
10
'''


dequeue()
'''
2
'''
0%