자료구조 디큐(dequeue)

 이번 포스팅에서는 디큐에 대해서 알아보도록 하겠습니다.

1. 디큐란?

• 왼쪽과 오른쪽에서 모두 삽입과 삭제가 가능한 큐입니다. 그래서 두 가지 버전의 push와 pop연산을 하게 되고, 나머지 연산은 스택과 큐랑 유사합니다.
• Python에서는 collections라는 모듈에 deque라는 클래스로 dequeue가 이미 구현되어 있습니다.

양방향 큐

2. 디큐 코드 구현 연습(Palindrome Check)

 코드를 통해 디큐를 구현해보고 디큐를 활용하여 문제를 풀어보도록하겠습니다. Palindrome은 문자열이 좌우 대칭인 것입니다. radar같은 문자열을 입력받으면 True를 출력하고, Palindrome이 아닌 문자열은 False를 출력하는 함수를 만들어보도록 하겠습니다.

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]

s = input()
def check_palindrome(s):
	dq = deque(s)
	palindrome = True
	while len(dq) > 1:
		if dq.left() != dq.right():
			return False
		else:
			dq.popleft()
			dq.pop()
	
	return palindrome

print(check_palindrome(s))

• deque 클래스 코드를 살펴보시면 큐를 양방향으로 구현해놓은 것을 알 수 있습니다.
• palindrome검사할 시 문자열을 deque에 집어넣고 양끝값을 꺼내서 서로 비교해가면 해당 문자열이 palindrome인지 아닌지 알 수 있습니다.

 궁금하시거나 잘못된 내용 있으면 댓글로 알려주시면 감사하겠습니다~