[TIL]자료구조-02.배열,리스트,스택,큐(2)

❌ 학부생 수준에서 작성된 글로 정확하지 않을 수 있습니다!
❌ 틀린 부분 피드백 미리 감사드려요..🥺

👩‍💻 순차적 자료구조

4. Queue

4.1. Queue

📍 정의: FIFO규칙의 순차적 자료구조. <-> Stack()
📍 지원 연산

• enque(): append와 같은 역할 수행. 큐의 가장 오른쪽에 값을 삽입
• deque(): 가장 왼쪽(맨 앞)에 있는 값을 삭제 후 반환
  => pop()과 동일한 역할 수행
• front(): 가장 왼쪽에 있는 값을 보여준다
  => top()과 동일한 역할 수행

📍 코드 구현

class Queue:
    def __init__(self):
        self.items = []
        self.front_index = 0

    def enque(self, val):
        self.items.append(val)

    def deque(self):
        if self.front_index == len(self.items): #원래 queue에 들어있는 item 수와 front_index의 값이 같아지면
            print('Queue is Empty') #다 비웠다
        else:
            x = self.items[self.front_index]
            self.front_index += 1 #deque()이후에는 front_index 크기를 하나씩 키운다
            return x

    def front(self):
        if len(self.items) == 0 or self.front_index == len(self.items):
            print('Queue is empty')
        else:
            return self.items[self.front_index]

    def __len__(self):
        return len(self.items) - self.front_index #전체 길이에서 front idx number를 뺀 것이다

    def isEmpty(self):
        return len(self)

❗️과제 1) Josephus game

1~n 명의 사람이 원형 테이블에 앉아있다. 1번부터 시작해서 k번째 사람이 탈락하는 게임을 한다. 마지막 생존자는?

📍 그림으로 풀이 설명하기

• queue의 성질을 이용한다면, 왼쪽 끝에 있는 item만 뽑아야 한다.
• 따라서 k-1번째까지의 item을 pop()한다음, 다시 큐 맨 뒤로 넣어야 한다.
• k번째의 item을 만나면 pop()하고 끝낸다.
• 이 과정을 마지막 하나가 남을때까지 반복한다.

✏️ 문제풀이

from stack_queue import Queue
def josephus(n,k):
    Q = Queue()

    for i in range(1, n+1):
        Q.enque(i)

    while len(Q) > 1:
        for i in range(1,k): #k번째 전까지는
            Q.enque(Q.deque()) #빼고 -> 뒤에 다시붙이고
        Q.deque() #k번째는 그냥 빼버리기

    return Q.deque() 

print(josephus(6,3))

✔️ 나는 두 번째 for문(for i in range(1,k))을 틀렸는데, 이 부분을 조건문으로 구현하려 했었다. 그런데 queue 의 특성상 리스트의 인덱스 넘버로 참조하려고 하니까 'not iterable' 객체로 인한 오류가 생겼다.

✔️ 반환값 또한, 그냥 'Q'로 하게 되면 객체의 주소값이 출력되므로 주의할것! Q.deque()를 하게 되면, 하나의 원소만 pop되므로, 괜찮다.

🤯 나머지 연산으로 while문 블럭 처리하는것도 생각해보기.. 자꾸 수행시간 에러가 뜬다..

while len(Q) > 1:
	index = Q.front()
    if (index % k) != 0:
    	Q.enque(Q.deque())
    else:
    	Q.deque()       

암튼 이런식으로 생각해봣는데.. 나머지 연산을 활용해볼 수 있는건 없을까..?

---

4.2. Dequeue

📍 정의: 왼쪽과 오른쪽 모두 삽입과 삭제가 가능한 큐. "Stack + Queue" 라고 생각하면 편하다!

📍 지원 연산

• append(): 큐의 가장 오른쪽에 값을 삽입
  => push() 와 같은 역할 수행.
• appendleft(): 큐의 가장 왼쪽에 값을 삽입
  => Queue의 enque() 와 같은 역할 수행.
• pop(): 가장 오른쪽에 있는 값 뽑고 삭제
• popleft(): 큐의 가장 왼쪽에 있는 값 뽑고 삭제
  => Queue의 deque() 와 같은 역할 수행.

Deque는 그림설명은 생략.. 스택과 큐의 성질을 모두 가진 자료구조라고 생각하면 굳이 필요 없다.
' 단, 파이썬에선 이미 collections라는 모듈에 dequeue가 있으니까 굳이 만들 필요가 없다! '

❗️과제 2) Palindrome check(회문 체크)

문자열을 입력받아 양쪽에서 하나씩 비교해보면서 똑같으면 True를 반환, 아니면 False를 반환한다.
ex) 'radar' --> True, 'salsa'--> False

✏️ 문제풀이

#Python 에는 이미 collections라는 모듈에 dequeue가 이미 구현됨

# deque없이 그냥 만든 회문체크!
def check_palindrome(s):
    palindrome = True
    reverse_s = []

    for i in range(1,len(s)+1):
        reverse_s.append(s[len(s)-i])

    if reverse_s == list(s):
        return palindrome
    else:
        palindrome = False
        return palindrome
        
#deque를 활용한 회문체크
from collections import deque

def check_palindrome_bydequeue(s):
    dq = deque()
    palindrome = True

    while len(dq) > 1: #홀수이면 1개가 남을 수 있으니까 1로 한다
        if dq.pop() != dq.popleft():
            palindrome = False

    return palindrome 

📌 출처 및 참고문헌
📎 매번 내 오류를 알려주는 'PythonTutor' http://www.pythontutor.com/visualize.html#mode=display
📎 iterable 자료형이 무엇인가
https://bluese05.tistory.com/55
📎 항상 좋은 강의 주시는 교수님 유튜브
https://www.youtube.com/watch?v=nqCNk_DmPio&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=11
👤 그리고 코딩 질문 귀찮아하지않고 받아주는 익명의 컴공 친구에게 감사인사..👏