JS Stack and Queue

자바스크립트 스택과 큐

스택(stack)

스택은 마지막에 삽입된 항목만을 제거하고 접근할 수 있다. (후입선출 ; LIFO ; Last In First Out)

배열과 다르게 마지막에 추가된 항목 외에는 직접 접근할 수 없다. 초반에 추가된 항목에 접근하기 위해서는 이후에 추가된 항목들을 제거해야 한다. 인덱스를 통해 항목들에 접근할 수 없다.

Peeking

스택의 마지막에 추가된 항목을 들여다 보는것, 마지막에 추가된 항목을 스택에서 제거하지 않고 반환하는 것을 의미한다. 다른 변수와 비교해 마지막에 추가된 항목을 자료 구조에서 제거해야 할지 결정하기 위해 주로 사용된다.

• 시간 복잡도: $O(1)$

삽입

자바스크립트 배열의 메소드인 push()를 사용해 삽입한다.

• 시간 복잡도: $O(1)$

삭제

자바스크립트 배열의 메소드인 pop()를 사용해 삭제한다.

• 시간 복잡도: $O(1)$

접근

n번째 노드에 접근하기 위해서는 pop()을 n번 호출해야 한다. 버퍼 스택을 사용해 접근하는 것이 안전하다.

• 시간 복잡도: $O(n)$

검색

버퍼 스택을 만들어 원본 스택을 변경하지 않고 pop()을 사용해 제거하며 검색한다.

• 시간 복잡도: $O(n)$

큐(queue)

큐는 첫 번째로 추가된 항목만을 제거하고 접근할 수 있다. (선입선출 ; FIFO ; First In First Out)

스택과 마찬가지로 한 번에 한 개의 항목만 접근할 수 있고 처음 추가된 항목 외에는 접근할 수 없다. 인덱스를 통해 항목들에 접근할 수 없다.

Peeking

큐에서 첫 번째 항목을 제거하지 않고도 첫 번째 항목을 반환해야 한다.

• 시간 복잡도: $O(1)$

삽입(enqueue ; 인큐)

큐에서 삽입은 인큐라 부른다. 자료 구조의 마지막 삽입해야 하기 때문에 push()를 사용해 추가한다.

• 시간 복잡도: $O(1)$

삭제(dequeue; 디큐)

큐에서 삭제는 디큐라 부른다. 첫 번째 항목을 제거하고 반환해야 하기 때문에 shift() 메소드를 사용한다.

• 시간 복잡도: $O(n)^3$

접근

n번째 노드에 접근하기 위해서는 dequeue를 n번 호출해야 한다. 버퍼 큐를 사용해 접근하는 것이 안전하다.

• 시간 복잡도: $O(n)$

검색

버퍼 큐를 만들어 원본 큐을 변경하지 않고 shift()를 사용해 제거하며 검색한다.

• 시간 복잡도: $O(n)$