Queue

Queue

Queue을 통해 사용하는 기능

push: 데이터를 큐에 추가한다.(큐의 전단부터 후단으로 차곡차곡 쌓는다.
pop: 큐의 가장 앞(전단) 데이터를 삭제한다.
size: 큐에 데이터가 몇 개 들어있는지 확인한다.
empty: 큐가 비어 있는지 확인한다.(데이터가 없는지 확인)
front: 큐의 가장 앞(전단) 데이터가 무엇인지 확인한다.
back: 큐의 가장 뒤(후단) 데이터가 무엇인지 확인한다.

\(\star\) 파이썬에서 queue를 사용하기 위해 deque라는 라이브러리를 이용한다. \(\to\) stack과 queue의 기능을 합친 것이다.

카드 2

\(N\)장의 카드가 있다. 각각의 카드는 차례로 \(1\)부터 \(N\)까지의 번호가 붙어 있으며, \(1\)번 카드가 제일 위에, \(N\)번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 \(N=4\)인 경우를 생각해 보자. 카드는 제일 위에서부터 \(1234\) 의 순서로 놓여있다. \(1\)을 버리면 \(234\)가 남는다. 여기서 \(2\)를 제일 아래로 옮기면 \(342\)가 된다. \(3\)을 버리면 \(42\)가 되고, \(4\)를 밑으로 옮기면 \(24\)가 된다. 마지막으로 \(2\)를 버리고 나면, 남는 카드는 \(4\)가 된다.

\(N\)이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

import sys
from collections import deque

# N = int(sys.stdin.readline())
N=6
queue = deque()
for i in range(N):
    queue.append(N-i)

while len(queue) > 1:
    queue.pop()
    queue.appendleft(queue.pop())
    
print (queue.popleft)

<built-in method popleft of collections.deque object at 0x7ff9ee947880>

queue

deque([4])

queue.popleft() \(\to\) dequeue의 전단을 삭제한다.
queue.pop() \(\to\) dequeue의 후단을 삭제한다.
queue.append(데이터) \(\to\) dequeue의 후단에 데이터를 삽입한다.
queue.appendleft() \(\to\) dequeue의 전단에 데이터를 삽입한다.

_queue = deque()

_queue.appendleft(3)
_queue.appendleft(2)
_queue.appendleft(1)

_queue

deque([1, 2, 3])

_queue.append(4)
_queue.append(5)

_queue

deque([1, 2, 3, 4, 5])

_queue.popleft()
_queue

deque([2, 3, 4, 5])

_queue.pop()
_queue

deque([2, 3, 4])

Queue

Queue을 통해 사용하는 기능

카드 2

Dummy