2회문 찾기 알고리즘

 

앞에서 자료 값 1, 2, 3, 4가 들어 있는 큐와 스택에서 차례로 자료를 빼내면 각각 1, 2, 3, 4 와 4, 3, 2, 1 순서로 자료가 나온다고 배웠습니다. 이것이 바로 회문을 판단하는 데 필요한 큐와 스택의 특징입니다.

주어진 문장의 문자들을 하나하나 큐와 스택에 넣은 다음 큐와 스택에서 하나씩 자료를 꺼낸다고 생각해 봅시다. 큐는 들어간 순서 그대로, 스택은 들어간 순서와 정반대로 문자들이 뽑혀 나옵니다.

회문은 거꾸로 읽어도 같은 글자가 나와야 합니다. 따라서 큐에서 꺼낸 문자들(원래 순서)이 스택에서 꺼낸 문자들(역순)과 모두 같다면 그 문장은 회문입니다.

 

그림 13-4 큐와 스택에서 차례로 꺼낸 값이 모두 같으면 회문