[Python] 큐와 스택(queue, stack)

큐

큐는 선입선출 방식의 자료구조이다. 예를 들어 버스를 타려고 승강장에 도착한 승객들은 차례대로 줄을 서게된다.

승객들은 먼저 온 순서대로 버스에 탑승하게 된다.

 

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

 

스택

스택은 접시를 쌓는것처럼 차곡차곡 쌓는 방식의 자료구조이다. 예를 들어 접시를 쌓아올릴 때 차곡차곡 접시를 쌓고 설거지를 할 때 맨 밑의 접시부터 닦는게 아니라 마지막으로 쌓은 접시부터 닦게 된다.

 

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

 

큐와 스택을 이용한 회문찾기 알고리즘

def palindrome(s):
    qu = []
    st = []

    for x in s:
        if x.isalpha():
            qu.append(x.lower())
            st.append(x.lower())

    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."))

결과
True
True
False

 

참고

isalpha()함수는 알파벳 문자인지 아닌지 확인하는 함수이다. 이를 통해 공백, 숫자, 특수문자등을 걸러준다.

 

lower()함수는 알파벳을 소문자로 바꿔준다.