파이썬 알고리즘 인터뷰 스택, 큐 간단 정리

스택, 큐

• 스택 요소를 컬렉션에 추가하는 push()와 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거하는 pop() 을 주요 연산으로 지원하는 요소의 컬렉션으로 사용되는 추상 자료형 후입선출로 처리됨 리스트가 스택 지원 연결 리스트로도 구현 가능
  • 스택 오버플로 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것
• 큐 시퀸스 한쪽 끝에 엔티티를 추가하고 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션 선입선출로 처리됨 Deque 로 좋은 성능 냄 리스트도 지원하지만 동적 배열이라 큐의 연산에 효율적이지 않음 deque, 우선순위 큐, BFS, 캐시 등을 구현할때 널리 사용
  • 원형 큐 후입선출 구조 마지막 위치와 시작 위치가 연결되는 구조 가짐 기존의 큐가 공간이 꽉 차거나 앞쪽의 요소들이 빠져서 충분한 공간이 남게되어도 그쪽으로 추가할 수 있는 방법이 없어서 공간을 재활용하기 위해 만들어 짐