강좌 / 프로그래머스 / 자료구조와 알고리즘 - 3

자료구조와 알고리즘 - 3

14강. 큐(Queues)

큐는 Stack과 달리 선입선출(FIFO; First-In First-Out) 의 순서로 제어됩니다. 리스트 속에 데이터들의 시작과 끝의 포인터가 존재합니다. 입력(enqueue)시, 리스트의 rear pointer에 추가되며 출력(dequeue)시, 리스트의 front pointer 부분을 꺼내게 됩니다.

실습

목표: 배열과 양방향 연결 리스트 구현시, 연산 복잡도 확인

배열 - 출력시, 모든 개체의 위치를 옮기는 과정에서 O(n) 가 소요
양뱡향 연결 리스트 - 포인터만 변경하게 됨으로 O(1) 소요

15강. 환형 큐(Circular Queue)

dequeue 과정에서 발생한 front pointer 앞의 공간을 재사용하지 못하는 큐의 단점을 개선하여 리스트의 시작과 끝을 이음으로써 재사용 가능