큐

큐란?

큐의 ADT 

1. isfull: 큐가 꽉 차서 더 이상 데이터를 넣을 수 있는지 여부를 확인하는 함수
   • True: 큐가 꽉 찼음
   • False: 큐에 여유 공간이 있음
2. isempty: 큐가 비어 있는지 확인하는 함수
   • True: 큐가 비었음
   • False: 큐에 데이터가 존재함
3. push (enqueue): 큐의 rear(뒤쪽) 끝에 데이터를 추가하는 함수
4. pop (dequeue): 큐의 front(앞쪽) 끝에서 데이터를 제거하는 함수
5. front: 큐의 앞쪽 끝에 있는 데이터를 반환하는 함수(제거하지 않음)
6. rear: 큐의 뒤쪽 끝에 있는 데이터를 반환하는 함수(제거하지 않음)
7. data[maxsize]: 큐가 내부적으로 데이터를 저장하는 배열 또는 리스트와 최대 크기 maxsize

 

리스트를 큐처럼 -> 왼쪽에서 삽입, 삭제 가능

queue = []

# 큐에 데이터를 추가
queue.append(1)
queue.append(2)
queue.append(3)

print("Queue after enqueuing:", queue)  # [1, 2, 3]

# 큐에서 데이터를 제거 
first_item = queue.pop(0)
print("Dequeued item:", first_item)  # 1
print("Queue after dequeuing:", queue)  # [2, 3]

덱을 큐처럼 ->  양끝에서 삽입, 삭제 가능

from collections import deque

queue = deque()

# 큐에 데이터를 추가
queue.append(1)
queue.append(2)
queue.append(3)

print("Queue after enqueuing:", queue)  # deque([1, 2, 3])

# 큐에서 데이터를 제거
first_item = queue.popleft()
print("Dequeued item:", first_item)  # 1
print("Queue after dequeuing:", queue)  # deque([2, 3])

무엇보다 리스트로 큐를 구현하면 가장 왼쪽에 있는 값을 뽑아내는 것에 차이가 크다.

pop(0)과 popleft()의 연산 차이가 크므로, 큐를 사용해야 한다면 덱을 바로 떠올리는게 용이하다고 판단된다.

 

문제

'''
요세푸스 문제
1~n까지 수를 넣고, k번째 수를 빼고, 그다음 숫자에서 k번째 수를 빼는걸 반복해서 마지막에 남는 수 return
n=5,k=2, return =3

'''
from collections import  deque
def solution(n,k):
    dq=deque(range(1,n+1))
    while len(dq) != 1:
        for _ in range(k-1):
            dq.append(dq.popleft())
        dq.popleft()
    return dq[0]
print(solution(5,2))

 

기능개발

https://school.programmers.co.kr/learn/courses/30/lessons/42586

'''
progresses=[93, 30, 55]
speeds=[1, 30, 5]
return = [2,1]

'''
from collections import  deque
import math
def solution(progresses,speeds):
    list=[]
    list2=[]
    for i in range(len(progresses)):
        list.append(100-progresses[i])
    for i in range(len(speeds)):
        list2.append(math.ceil(list[i]/speeds[i]))
    max_day=list2[0]
    cnt=0
    answer=[]
    for i in range(len(progresses)):
        if list2[i]<=max_day:
            cnt+=1
        else:
            answer.append(cnt)
            cnt=1
            max_day=list2[i]
    answer.append(cnt)
    return answer
print(solution([93, 30, 55],[1, 30, 5]))

 

카드뭉치

https://school.programmers.co.kr/learn/courses/30/lessons/159994

for문&리스트

'''
cards1 = ["i", "drink", "water"]    , cards2 = ["want", "to"]  , gaol = ["i", "want", "to", "drink", "water"] , result ="Yes"

'''
from collections import  deque
def solution(cards1, cards2, goal):

    for _ in range(len(goal)):
        if cards1 and goal[0] == cards1[0]:
            cards1.pop(0)
            goal.pop(0)
        elif cards2 and goal[0] == cards2[0]:
            cards2.pop(0)
            goal.pop(0)
        else:
            break
    return "Yes" if not goal else "No"

print(solution(["i", "drink", "water"],["want", "to"],["i", "want", "to", "drink", "water"]))
print(solution(["i", "water", "drink"],["want", "to"],["i", "want", "to", "drink", "water"]))

 

while문&deque

'''
cards1 = ["i", "drink", "water"]	, cards2 = ["want", "to"]	, gaol = ["i", "want", "to", "drink", "water"]	, result ="Yes"

'''
from collections import  deque
def solution(cards1, cards2, goal):
    cards1 = deque(cards1)
    cards2 = deque(cards2)
    goal = deque(goal)
    while goal:
        if cards1 and goal[0] == cards1[0]:
            cards1.popleft()
            goal.popleft()
        elif cards2 and goal[0] == cards2[0]:
            cards2.popleft()
            goal.popleft()
        else:
            break
    return "Yes" if not goal else "No"

print(solution(["i", "drink", "water"],["want", "to"],["i", "want", "to", "drink", "water"]))
print(solution(["i", "water", "drink"],["want", "to"],["i", "want", "to", "drink", "water"]))