9장. 스택, 큐

스택은 LIFO(후입선출), 큐는 FIFO(선입선출)로 처리된다. 파이썬은 리스트가 스택과 큐의 모든 연산을 지원한다. 다만, 리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서는 데크라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다.

스택

• 스택은 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다.
• push(): 요소를 컬렉션에 추가한다.
• pop(): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다.

문제 리스트

큐

• 큐는 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션이다.

• 큐는 스택에 비해서는 쓰임새가 적다
• 그러나 데크나 우선순위 큐 같은 변형들은 여러 분야에서 유용하게 쓰인다.
• 이외에도 너비 우선 탐색이나 캐시 등을 구현할때도 널리 사용된다.

• 사실상 파이썬의 리스트는 큐의 모든 연산을 지원하기 때문에 그대로 사용해도 무방하다
• 그러나, 좀 더 나은 성능을 위해서는 이후에 살펴볼 양방향 삽입, 삭제가 모두 O(1)에 가능한 데크를 사용하는 편이 가장 좋다.

문제 리스트