자료구조 디큐 dequeue / deque, 팰린드롬 함수 구현

디큐 Dequeue / deque

dequeue는 Stack과 Queue를 합친 자료구조로, 왼쪽과 오른쪽에서의 삽입과 삭제가 모두 가능하다.

파이썬에는 collections 모듈에 deque 클래스로 구현되어 있다. 

 

from collections import deque

 

오른쪽에 값 넣을 때 = append / 왼쪽에 값 넣을 때 = appendleft

가장 오른쪽 값을 삭제할 때 = pop / 가장 왼쪽 값 삭제할 때 = popleft

 

 

디큐 활용 예: Palindrome

문자열 s와 s를 거꾸로 뒤집은 문자열이 서로 같다면 Palindrome

ex) 기러기, salsa, 다시합창합시다

(디큐를 쓰지 않고도 Palindrome 판별 코드를 작성할 수 있음.)

 

디큐를 쓰지 않은 코드

s = input('단어를 입력하세요: ')

if s == ''.join(reversed(s)):
    print('해당 단어는 팰린드롬입니다.')
else:
    print('해당 단어는 팰린드롬이 아닙니다.')

 

디큐를 쓴 코드 1 (파이썬 deque 클래스 활용)

# deque 활용하기
# 양쪽 값들이 같은지 보면 됨. pop과 popleft를 이용하여 두 개가 같은지 확인

from collections import deque

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

    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            palindrome = False

    return palindrome


s = input()
print(check_palindrome(s))

초기에는 변수 palindrome의 상태를 True로 설정. 

dq에 있는 문자열의 양 끝값을 비교한다. 만약 두 값이 같지 않다면 palindrome은 False로 바뀐다. 

 

 

디큐를 쓴 코드 2 (deque 클래스를 직접 구현)

class deque():
    def __init__(self, s):
        self.items = list(s)

    def append(self, c):
        self.items.append(c)

    def appendleft(self, c):
        self.items.insert(0, c)

    def pop(self):
        return self.items.pop()

    def popleft(self):
        return self.items.pop(0)

    def __len__(self):
        return len(self.items)

    def right(self):
        return self.items[-1]

    def left(self):
        return self.items[0]


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

    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            palindrome = False

    return palindrome


s = input()
print(check_palindrome(s))