목차

1. 큐(Queue) 개념
   • 큐 특징
   • 삽입(Enqueue)과 삭제(Dequeue)
2. 큐 구현
   • 연결 리스트 활용
   • 파이썬 덱 활용
   • 파이썬 덱을 큐처럼 활용

---

1. 큐(Queue) 개념

이미지 출처

• 큐: 줄 서기(순서를 지키기 위해), 영한사전에서도 '대기줄'이라고 번역된다.
• 실생활 예시: 빠른 길 찾기, 일방통행, 은행 업무 대기 줄 서기, 프린트의 출력 처리, 윈도우 메시지 처리

큐 특징

✌️스택과의 가장 큰 차이점,✌️ 스택은 순서를 무시하고 나중에 들어온 애를 먼저 처리한다.

• 선입선출, FIFO(First-In First-Out): 먼저 들어간 애가 먼저 나오는 데이터 입출력 방식

큐 구조

• Front(맨 앞)
• Rear(맨 뒤)
• 큐의 크기

삽입(Enqueue)과 삭제(Dequeue)

• 인큐(Enqueue)
  - 큐에 데이터 삽입하는 연산 작업
  • 큐의 맨 뒤(rear)에 새로운 데이터 추가
• 디큐(Dequeue)
  - 큐에서 데이터 삭제하는 연산 작업
  • 큐의 맨 앞(front)에서 데이터 꺼냄

✌️스택과의 차이점✌️은, 스택은 한 쪽(top)에서만 입출력이 가능하고, 큐는 입출력이 양 쪽(입력은 rear로, 출력은 front에서)에서 따로 처리된다는 점이다.

• 데이터 삽입/삭제에 O(n)이 걸리는 스택과 달리 큐는 삽입, 삭제 모두 O(1)의 시간 복잡도 안에서 처리할 수 있다는 장점이 있다.

2. 큐 구현

연결리스트를 이용한 큐 구현(__init__)

LinkedListQueue 구현

• no: 큐에 들어있는 데이터의 개수 (= 노드 개수)

• front: 큐에서 가장 오래 전에 추가된 데이터가 들어있는, 삭제가 용이한 front 노드에 대한 참조

• rear: 큐의 가장 최근에 추가된 데이터가 들어있는, 새로운 데이터 삽입이 용이한 rear 노드에 대한 참조

• __init__(): 생성자

• __len__(): 큐의 크기를 리턴

• is_empty(): 큐가 비어있다면 True 리턴

• ✌️스택과의 차이점✌️은, 스택은 입출력이 모두 top에서만 이루어지므로 front, rear 대신에 top 속성 하나만으로 구현이 가능하다는 것이다.
  
  @D2Coding

연결리스트를 이용한 큐 구현(enqueue())

• enqueue(): # O(1)
  - 큐가 비어있다면, 삽입 후 front와 rear 모두 같은 노드를 참조
  • 큐가 비어있지 않다면, rear노드 다음에 새 노드를 추가한 후에 rear 갱신
    

연결리스트를 이용한 큐 구현(dequeue())

• dequeue(): # O(1)
  - 큐가 비어있지 않으면, 큐의 프런트 노드의 데이터를 저장한 후, 프런트를 다음 노드에 참조하고, 노드의 개수를 하나 줄인 뒤 삭제한 데이터를 리턴한다.
  • 큐가 비어있으면 IndexError를 일으킨다.
    

연결리스트를 이용한 큐 구현(peek())

• peek(): O(1)
  - 큐가 비어있지 않으면, 큐의 프런트 노드의 데이터를 리턴
  • 큐가 비어있다면, IndexError를 일으킴
    

연결리스트를 이용한 큐 구현(print())

• print():
  - 큐에 있는 모든 데이터를 출력하는 메소드
  - 연결리스트, 스택과 유사하나 ✌️차이점✌️은 front, rear이 있고 없고의 차이
  

연결리스트를 이용한 큐 구현(clear())

• clear():
  - 큐에 있는 모든 데이터 삭제
  
  

연결리스트를 이용한 큐 구현(7)

• 왜 clear가 없다고 하는 것인 지 모르겠다.😥

3. 파이썬 덱(deque) 활용

덱을 이용한 큐 클래스 구현(1)

Problem.

• 파이썬 리스트로 큐를 구현할 때의 단점
  - 파이썬 리스트로 프런트 데이터를 제거하는 데 오래 걸림
  리스트의 pop(0)연산의 시간복잡도가 O(N)이다.
  (이는 파이썬 리스트의 멤버변수가 오른쪽 끝이기 때문이다.)
  

Solution.

• 덱 자료구조(연결 리스트의 일종)
  

• 덱은 노드들이 2중으로 연결되어 있다.

• 덱은 양방향 모두 삽입/삭제가 O(1)이다.

• popleft()연산을 이용하면 O(1)에 프런트 데이터를 삭제할 수 있다.

• 덱의 실생활에서의 쓰임:
  웹 페이지 스크롤
  
  스크롤을 내리면 페이지 상단의 정보는 삭제되고, 페이지 하단의 정보가 새롭게 삽입되는 것의 연속이다.

• ✌️연결리스트와 덱의 차이✌️는 단방향, 양방향이다.

덱을 이용한 큐 클래스 구현(2)

• 파이썬에 덱(deque)이라는 자료형이 있는데 collections라이브러리를 다운받아 사용할 수 있다.
• ✌️연결 리스트, 스택과 달리✌️ 생성자는 빈 덱만 생성해주면된다.
  
• 리스트와 마찬가지로 append()함수를 사용해 데이터를 삽입하는 enqueue()메서드를 구현한다.
  
• ✌️리스트와 달리✌️, 덱은 popleft()메소드를 사용할 수 있다. pop()과 비슷하지만 왼쪽(주로 front 노드가 위치한)의 요소를 삭제하는 기능이 있다.
  
• front 노드의 데이터를 엿보는 peek()메소드는 리스트와 마찬가지로 슬라이싱을 통해 구할 수 있다.
  
• 파이썬 내장 함수인 print()를 사용해서 덱의 모든 데이터를 출력할 수 있다.

deque([1, 2])

와 같이 출력된다.

4. 파이썬 데크를 큐처럼 이용

5. 큐를 활용한 문제 풀이

카드 버리기 문제

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

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

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.
N이 주어졌을 때 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.
"""

✏️ 풀이: deque자료형을 이용해 삽입,삭제,출력 연산을 수행한다.
삽입은 append(), 삭제는popleft(), 출력은 print(), front 노드 데이터 확인은 deque[0]슬라이싱으로 구현이 가능하다.

from collections import deque

먼저 파이썬 deque 자료형을 사용할 수 있는 collections 라이브러리를 가져와 deque를 import한다.

n = 5

디버깅을 위해 작성해둔 것으로 무시해도 된다.

💡함수를 작성할 때에는 중간중간 확인이 어렵기 때문에 처음부터 def안에 코드를 작성하기보다는 밖에 작성하고, 입력값에 직접 testcase를 지정해서 테스트해보는 것이 좋다.

def dis_card(n:int) -> Any:

함수 이름은 '버리다'의 뜻을 가지고있는 discard로 언어 유희를 해보았다. card를 discard하다.🤣 입력값은 카드의 장 수인 int형식의 n이다. -> Any는 출력값의 형식이 어떤 것이든 상관없다는 뜻이다.

	c = deque()

card의 앞 자를 따서 c라는 이름의 인스턴스를 생성해주었다. 변수(인스턴스)c에 빈 덱을 저장했다.

	for i in range(1,n+1):
    	c.append(i)

빈 덱 c에 1부터 n까지의 숫자를 append해주었다. 이제 c에는 deque([1,2,3,4,...n])과 같이 데이터가 들어있게 된다.

	while len(c) > 1:
    	c.popleft()
        c.append(c.popleft())

카드가 1장이 될 때까지 while True문으로 반복한다.
popleft() 함수를 활용해서 c의 front에 위치한 데이터를 하나 삭제해준다.

💡이 때 c.popleft()는 삭제만 하지만, 삭제한 데이터를 return하기 때문에 print(c.popleft()) 또는 data = c.popleft()와 같이 삭제된 데이터를 출력하거나 다른 변수에 넣어 살릴 수 있다.

print(c[0])

슬라이싱을 통해 front에 위치한 c의 데이터를 print()문으로 출력할 수 있다. 마지막 남은 하나의 데이터를 출력한다는 의미이다.

공주 구하기 문제

"""
어느 왕국의 이웃 나라 외동딸 공주가 숲 속의 괴물에게 잡혀갔습니다.
왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매기고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가게 동그랗게 앉게 합니다. 그리고 1번 왕자부터 시계 방향으로 돌아가며 1부터 시작하여 번호를 외치게 합니다. 한 왕자가 K(특정 숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 됩니다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외칩니다.

이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있습니다. 마지막에 남은 왕자의 번호는 무엇인가요?

n과 k가 주어 졌을 때, 마지막에 남은 왕자의 번호를 리턴하는 함수를 작성하시오.
"""

✏️ 풀이: 이 문제는 큐로 푸는 문제이다. 큐를 동그랗게 말아서 시작과 끝이 만나게 한 형태로 이해할 수 있다. 큐는 front에서만 삭제가 가능하므로 원탁에 N개의 의자를 두고, 왕자를 시계방향으로 K번 돌게 하면 1번 의자(front)에 앉은 왕자를 빼는 문제로 재정의할 수 있다.

def save_princess(n: int, k: int) -> int:

공주 구하기 대작전이라 함수명을 save_princess로 했는데 직관적이고 잘 만든 것 같다. 교수님 코드도 save_princess였다.😊 입력값은 n과 k로 두 개이며 모두 정수형으로 지정해줬다. 출력값도 정수형(integer)이다.

	p = LinkedListQueue()

앞서 만들어 놓은 연결리스트로 구현한 큐 코드를 사용하였다. 공주를 구하러 갈 왕자도 prince, p로 시작하므로 인스턴스 명을 p로 지정했다. 이제 이 p가 LinkedListQueue()클래스 내의 모든self 자리에 들어가 작동할 것이다.😊

	for i in range(1,n+1):
    	p.enqueue()

앞서 카드 버리기 문제에서는 append()함수를 사용해 삽입을 해주었는데, 이 경우 클래스에서 이미 구현한 enqueue()메소드가 있기 때문에 사용해 주었다. for문을 활용해 1부터 n까지의 숫자를 순서대로p에 입력해주었다. 이는 왕자의 id로서의 역할을 한다.

	while len(p) > 1:

앞서 카드 버리기와 마찬가지로 한명만 남을 때까지 while True문을 통해 반복적으로 왕자들의 자리를 바꿔줄 것이다.

		for _ in range(k-1):
        	p.enqueue(p.dequeue())
        p.dequeue()

for문에서 _를 넣는 경우는 단순 반복일 때이다. k-1번 반복적으로 front 자리에 앉을 왕자의 id를 바꾸어줄 것이다. 왕자가 모두 반시계 방향으로 돌면서 한 칸씩 자리를 옮기는 것은 곧 맨 앞(front)의 왕자가 맨 뒤(rear)으로 간다는 의미이다. 이렇게 되면 2번 왕자가 front에 가는 것과 같다. 참조 구현하는 방법은 디큐(맨 앞의 왕자 삭제)와 인큐(맨 뒷자리에 삭제한 왕자 삽입)를 반복하는 것이다.k-1번 반복하면k인 왕자가 front에 앉게된다. 이 때 for문에서 빠져나오게 되는데 dequeue()메소드를 사용해주면 front에 있는 애를 바로 삭제해줄 수 있다.

💡k번 반복이 아닌 k-1번 반복인 이유는?!
왕자가 3명이라고 했을 때, 한 번 디큐-인큐를 반복하면 2번 왕자가 front 자리에 가기 때문이다. 두 번째로 반복하면 3번 왕자가 front에 간다. k번째 반복하면 k+1번째 왕자가 front에 가는 것임을 알 수 있다. 따라서 k번째 왕자가 front에 오는 시점은 k-1.

	return p.peek()

front의 데이터를 출력해주는 peek()메서드를 통해 return으로 p의 마지막 남은 하나의 데이터를 반환할 수 있다.