[알고리즘] 큐(Queue)

큐(Queue)

1. 구조

• 줄을 서는 행위와 비슷합니다.
• 가장 먼저 입력한 데이터를 가장 먼저 꺼낼 수 있는 구조입니다.
• FIFO(First In First Out), LILO(Last In Last Out)으로 스택과는 꺼내는 순서가 반대입니다.
  

2. 알아둘 용어

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

3. 어디에 가장 많이 사용될까?

• 멀티태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됩니다. 큐에 경우에는 특별히 언급되는 장단점이 없습니다.

4. 예제

https://www.acmicpc.net/problem/10845

import sys
queue = []
num = int(sys.stdin.readline())

for i in range(num):
    order = sys.stdin.readline().split()

    if order[0] == "push":
        queue.insert(0, order[1])

    elif order[0] == "size":
        print(len(queue))

    elif order[0] == "pop":
        if len(queue) != 0: 
        	print(queue.pop())
        else: 
        	print(-1)

    elif order[0] == "empty":
        if len(queue) == 0: 
        	print(1)
        else: 
        	print(0)

    elif order[0] == "front":
        if len(queue) == 0: 
        	print(-1)
        else: 
        	print(queue[len(queue) -1])

    elif order[0] == "back":
        if len(queue) == 0: 
        	print(-1)
        else: 
        	print(queue[0])

insert와 pop을 이용해서 queue의 기능을 사용하는 예시이다.