1. 큐와 스택

큐와 스택은 컴퓨터 과학에서 다루는 여러 가지 자료 구조 중에서도 가장 기본적인 것이다. 두 자료 구조는 '자료를 넣는 동작'과 자료를 빼는 동작'을 할 수 있으며 들어간 자료가 일렬로 보관된다는 공통점이 있다. 하지만 자료를 넣고 뺄 때 동작하는 방식이 서로 다르다.

큐 (Queue)

큐는 '줄서기'에 비유할 수 있다. 택시를 타기 위해서 줄을 서는 과정을 생각해보자. 새로 택시 정류장에 도착한 사람은 맨 뒤로 가서 줄을 서고, 택시가 도착하면 그 줄의 맨 앞에 선 사람이 줄을 빠져나가 택시를 탄다. 가장 먼저 줄을 선 사람이 가장 먼저 택시를 타게 된다. (First In Fist Out)

큐에 자료를 한 개 집어넣는 동작을 '인큐(enqueue)', 큐 안에 있는 자료 한 개 꺼내는 동작 '디큐(dequeue)'라고 표현한다.

스택 (stack)

스택(stack)은 '접시 쌓기'에 비유할 수 있다. 식당에서 접시를 차곡차곡 쌓다가 하나씩 꺼내 설거지하는 과정을 생각해보자. 다 먹은 접시를 쌓을 때는 쌓은 접시 맨 위에 올려놓는다. 설거지하려고 접시를 꺼낼 때도 맨 위에 있는 접시부터 꺼낸다. 바꿔 말하면 가장 마지막에 들어간 자료를 가장 먼저 꺼내는 것을 의미한다. (Last In First Out).
맨 아래에 있는 접시를 꺼내려면 맨 위에 있는 접시부터 하나하나 꺼내야 한다는 것도 쉽게 이해할 수 있다.

스택에 자료를 하나 집어넣는 동작을 '푸시(push)', 스택 안에 있는 자료를 하나 꺼내는 동작을 '팝(pop)'이라고 한다.

아래 그림을 보면 큐와 스택에는 둘 다 1, 2, 3, 4라는 자료가 보관되어 있다. 큐와 스택에서 각각 자료를 차례로 빼내면 어떻게 될까?

큐에서 자료를 꺼내면(dequeue) 들어간 순서 그대로, 즉 1, 2, 3, 4 순서로 자료가 나온다. 하지만 스택은 자료를 꺼내면 (pop) 들어간 순서와 정반대인 4, 3, 2, 1 순서로 자료가 나온다.

리스트로 큐와 스택 사용하기

큐와 스택은 자료를 일렬로 보관하는 특징이 있다. 따라서 파이썬의 리스트를 이용해서 쉽게 만들어 볼 수 있다. 이 책에서는 아래 표와 같은 방식으로 리스트를 사용해 큐와 스택을 만들어 보자.

2. 회문 찾기 알고리즘

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

# 주어진 문장이 회문인지 아닌지 찾기(큐와 스택의 특징을 이용)
# 입력: 문자열 s
# 출력: 회문이면 True, 아니면 False


def palindrome(s):
    # 큐와 스택을 리스트로 정의
    qu = []
    st = []
    # 1단계: 문자열의 알파벳 문자를 각각 큐와 스택에 넣음
    for x in s:
        # 해당 문자가 알파벳이면(공백, 숫자, 특수문자가 아니면)
        # 큐와 스택에 각각 그 문자를 추가
        if x.isalpha():
            qu.append(x.lower())
            st.append(x.lower())
    # 2단계: 큐와 스택에 들어 있는 문자를 꺼내면서 비교
    while qu:  # 큐에 문자가 남아 있는 동안 반복
        if qu.pop(0) != st.pop():  # 큐와 스택에서 꺼낸 문자가 다르면 회문이 아님
            return False
    return True

print(palindrome("Wow"))
print(palindrome("Madam, I'm Adam."))
print(palindrome("Madam, I am Adam."))

isalpha() 함수는 주어진 문자가 알파벳 문자에 해당하는지 확인하는 기능을 한다. 공백, 숫자, 특수문자는 isalpha() 함수로 걸러 낸다.
lower() 함수는 주어진 알파벳을 소문자로 바꾸는 기능을 한다. 문자를 모두 소문자로 바꿔 큐와 스택에 추가하므로 대문자와 소문자를 구분하지 않고 회문인지 아닌지 판단할 수 있다.