19. [스택, 큐, 데크] 간단 정리

구현

1. 연결리스트

• O(1) : 리스트 양쪽 끝에 추가와 삭제
• O(N) : 임의의 노드의 할당, 삭제, 포인터 따라가기(traveling)

2. 동적 배열

 

• 스택 : 추가, 삭제 O(1)
• 큐 : rear(뒤) 부분 추가, 삭제 O(1) / front(앞) 부분 추가, 삭제 O(N)

  따라서 circular queue(혹은 circular buffer)를 만들기도 함. (추가, 삭제 발생시 head와 tail을 변경) : O(1)

• 데크 : 둘다 O(1)

온라인 알고리즘

전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘.

입력의 크기가 너무 커서 프로그램상에 올려놓을 수 없을 때 사용한다.