스택1 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) 온라인 알고리즘 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘. 입력의 크기가 너무 커서 프로그램상에 올려놓을 수 없을 때 사용한다. 2019. 8. 27. 728x90 이전 1 다음
