자바스크립트로 하는 자료구조와 알고리즘(12장) - 스택과 큐

스택

 

마지막에 삽인된 항목만을 제거하고 접근할 수 있다.

후입 선출(LIFO)

자바스크립트 배열에는 pop과 push라른 메소드가 있다. 이 메소드를 사용하면 스택을 쉽게 구현가능

 

들여다보기

= 마지막에 추가된 항목을 들여다 보는 것

= 마지막에 추가된 항목을 스택 자료구조에서 제거하지 않고 반환하는 것을 의미.

 

삽입

push()함수를 사용.

시간복잡도 O(1)

 

삭제

pop()함수를 사용

O(1)

 

접근

n번째 노드에 접근하기 위해선 pop을 n번 호출해야한다.

O(n)

 

검색

pop이 버퍼 스택에 대해 호출될 수 있도록 버퍼 스택을 만들어야함!

원래 스택으로부터 어떤 항목도 제거되지 않도록 원래 스택은 건드리지 않는다.

O(n)

 

 

큐

 

첫번째로 추가된 항목만을 제거할 수 있는 자료구조

선입선출 (FIFO)

shift() push()메소드를 활용

큐에 항목을 추가하는 것을 인큐(enqueue) , 제거하는것을 디큐(dequeue)라고 한다.

 

들여다보기

첫번째 항목을 제거하지 않고도 첫번째 항목을 반환한다.

스택은 마지막 , 큐는 처음!

 

삽입

push를 사용해 구현 가능

O(1)

 

삭제

shift()를 사용해 구현 가능

O(n)

전체 항목의 인덱스가 변경 되어야 하기 때문에(가운데 하나가 비어버리면 그것을 다 옮겨줘야함)

 

접근

n번째 마지막으로 추가된 노드에 접근하기 위해서는 디큐를 n번 호출

원래 큐에 변경이 생기지 않도록 버퍼가 필요함!

O(n)

 

검색

버퍼 큐를 우선 생성하고 해야함 (큐가 변경되지 않게 하기 위해)

O(n)