IT-garden

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력과 출력

알고리즘 분류

큐

정답

import sys

def push(c):
    b.append(c)

def pop():
    if len(b) == 0:
        print(-1)
    else:
        print(b.pop(0))

def size():
    print(len(b))

def empty():
    if len(b) == 0:
        print(1)
    else:
        print(0)
        
def front():
    if len(b) == 0:
        print(-1)
    else:
        print(b[0])

def back():
    if len(b) == 0:
        print(-1)
    else:
        print(b[-1])

n=int(input())
b=[]
    
for i in range(n):
    c=sys.stdin.readline().strip()
    a=c.split(' ')

    if a[0] == 'push':
        push(a[1])
    elif a[0] == 'pop':
        pop()
    elif a[0] == 'size':
        size()
    elif a[0] == 'empty':
        empty()
    elif a[0] == 'front':
        front()
    elif a[0] == 'back':
        back()

백준 알고리즘 10845번 : www.acmicpc.net/problem/10845

큐는 FIFO(First-In First-Out) 형식을 가집니다.

큐의 예는 매표소에서 표 구매, 은행 창구에서 순서 기다리는 것이 있습니다.

매표소에서 표를 사기 위해서는 사람들이 줄을 서고 줄을 선 순서대로 표를 살 수 있습니다.

즉, 가장 먼저 줄을 서서 앞에 있는 사람이 먼저 표를 사게 되는 방식입니다.

큐의 삽입과 삭제는 다른 쪽에서 일어납니다.

삽입이 일어나는 곳은 후단(rear)이라 하고 삭제가 일어나는 곳은 전단(front)라고 합니다.

큐에서는 Enqueue와 Dequeue를 알아야 합니다.

Enqueue은 큐의 요소를 추가하는 연산으로 큐의 가장 뒤에 새로운 요소를 추가합니다.

Dequeue은 큐의 가장 앞에 있는 요소를 반환합니다.

큐는 파이썬 라이브러리 Queue()를 사용해 구현할 수 있습니다.

큐에는 여러 연산이 있습니다.

push : 큐의 가장 뒤에 데이터 넣기

pop : 큐의 가장 앞에 데이터 제거

front : 큐의 가장 앞의 값 확인

empty : 큐가 비었는지 확인

큐의 파이썬 코드입니다.

import queue

que = queue.Queue()

que.put(1)
que.put(2)
que.put(3)
que.put(4)
que.put(5)

# 출력>>deque([1, 2, 3, 4, 5])
print(que.queue)

que.get()
# 출력>>deque([2, 3, 4, 5])
print(que.queue)

que.get()
# 출력>>deque([3, 4, 5])
print(que.queue)

que.get()
# 출력>>deque([4, 5])
print(que.queue)

파이썬 라이브러리 Queue()를 사용해 기본적인 큐 외에도 다양한 큐를 구현할 수 있습니다.

LifoQueue() : 기존 큐와 다르게 LIFO(last-In First-Out) 형식을 가지는 큐입니다.

즉, 스택과 같은 구조를 가집니다.

LifoQueue의 파이썬 코드입니다.

import queue

lque = queue.LifoQueue()

lque.put(1)
lque.put(2)
lque.put(3)
lque.put(4)
lque.put(5)

# 출력>>[1, 2, 3, 4, 5]
print(lque.queue)

lque.get()
# 출력>>[1, 2, 3, 4]
print(lque.queue)

lque.get()
# 출력>>[1, 2, 3]
print(lque.queue)

lque.get()
# 출력>>[1, 2]
print(lque.queue)

PriorityQueue() : 데이터마다 우선순위를 넣어 우선순위가 높은 순으로 출력되는 형식을 가진 큐입니다.
(우선순위, 데이터) 형식의 튜플로 넣어야 합니다.
또한 데이터는 튜플로 저장됩니다.

PriorityQueue의 파이썬 코드입니다.

import queue

pque = queue.PriorityQueue()

pque.put((1,1))
pque.put((3,2))
pque.put((2,3))
pque.put((4,4))
pque.put((5,5))

# 출력>>[(1, 1), (3, 2), (2, 3), (4, 4), (5, 5)]
print(pque.queue)

pque.get()
# 출력>>[(2, 3), (3, 2), (5, 5), (4, 4)]
print(pque.queue)

pque.get()
# 출력>>[(3, 2), (4, 4), (5, 5)]
print(pque.queue)

pque.get()
# 출력>>[(4, 4), (5, 5)]
print(pque.queue)