스택과 큐

자료구조 중 스택과 큐는 많이 들어보았지만, 

항상 뭐가 뭔지 헷갈렸다.

이번 기회에 제대로 확실히 정리해보고자 한다!

 

일단 자료구조란 배열처럼 데이터를 저장하고 관리할 수 있는 것이다.

스택과 큐는 데이터를 어떻게 저장하고 관리하는지 알아보자 ! 

 

• 스택은 후입선출

js에서 push()는 삽입, pop()은 삭제 함수이다.

ex) 인터넷의 뒤로가기(그동안 쌓였던 것들의 뒷부분 부터 차례로 뒤로가기 됨)

• 큐는 선입선출

queue에 삽입하는 것은 enqueue라 하고, 삭제하는 것은 dequeue라고 한다.

마찬가지로 push()는 삽입, shift()는 가장 앞의 것 삭제 함수이다.

ex) 은행창구 번호표(들어온 순서대로 나감)

 

시간복잡도에 대해 이야기 하자면

push()와 pop()은 O(1)의 시간복잡도를 가진다.

반면에 shift()와 unshift()(shift()의 반대로 맨 앞에 삽입)은 O(n)의 시간 복잡도를 가진다.

왜냐하면, shift()로 맨 앞의 값을 빼면 뒤의 값들이 한 칸씩 땡겨야 하기 때문

반면에 pop과 push는 뒤에서 위치 이동 필요없이 삽입 삭제가 가능하다.