[자료구조 공부] 자바스크립트 스택(stack) & 큐(Queue) #5

☘️ 스택(stack)

스택은 LIFO(Last In First Out) 로 "나중에 들어간 것이 먼저 나온다" 라는 개념을 가진 선형 자료구조이다.

예를 들어 아래부터 1, 2, 3, 4, 5 상자를 순서대로 넣으면, 뺄 때 순서대로 5, 4, 3, 2, 1 이렇게 되는 구조이다.

 

 

 

여기서 요소를 넣는 것을 Push, 빼는 것을 Pop 이라고 하며, 제일 위에 있는 요소를 Top이라고 한다.

 

☘️ 자바스크립트에서 스택(stack) 구현

자바스크립트에서 스택을 구현하기 위해 배열(Array)를 사용할 수 있다.

이미 배열에 push와 pop 함수가 구현되어 있어서 보다 편리하다.

 

그래서 아래 코드와 같이 배열을 사용하여 스택을 구현할 수 있다.

 

코드 실행 결과

코딩 테스트에서 스택을 사용하는 경우로는 짝을 맞춰야 하는 문제, 단조 스택, DFS 등이 있다고 한다.

---

☘️ 큐(Queue)

큐는 FIFO(First In Firt Out) 으로 "먼저 들어간 것이 먼저 나온다 / 나중에 들어간 것이 나중에 나온다" 라는 개념을 가진 선형 자료구조이며,

대기열이라고 부를 수 있다.

큐의 앞부분을 Front, 뒷부분을 Rear(Back) 라고 부르며

요소를 넣는 것을 Enqueue, 요소를 빼는 것을 Dequeue 라고 한다.

 

큐의 종류에는 Liner(선형) Queue, Circular(환형) Queue가 있고,

Ciricular Queue 는 Front 와 Rear가 이어져 있으며, 코딩테스트에서는 환형 큐를 사용하는 경우가 별로 없다고 하여

해당 게시물은 선형 큐만 다룬다.

 

 

 

 

 

☘️ 자바스크립트에서 큐(Queue) 구현 - 배열

자바스크립트에서 선형 큐를 구현할 때엔 배열 또는 연결 리스트(Linked List)를 사용한다.

 

선형 큐를 배열로 구현을 한다면 Dequeue를 할 때 빈공간이 메꿔지지 않고,

계속 Enqueue를 하면 배열의 공간이 꽉 찰 수 있다. (자바스크립트에서는 큰 문제X) 

만약 빈공간을 메꾸고 싶으면 선형 시간 O(n)이 소요된다.

 

그래서 자바스크립트에서 큐를 배열로 다음과 같이 구현할 수 있다.

 

코드 실행 결과

💡 추가사항

자바스크립트 배열로 큐를 구현할 때, shift 함수를 사용하는 것을 추천하지 않는다.

왜냐하면 shift 함수를 사용하면, 값이 제거된 빈 공간을 메꿔주어 선형 시간 O(n) 이 소요되기 때문이다.

 

그러나 요소가 많지 않을 경우에 shift와 push를 사용해서 간단하게 큐를 구현할 수 있다.

 

☘️ 자바스크립트에서 큐(Queue) 구현 - 연결 리스트

 

위에 실행 결과를 보면 Dequeue를 했을 때, 공간이 메꿔지지 않는 것을 볼 수 있다.

 

이러한 문제를 해결하기 위해 연결 리스트를 사용한다.

그러면 연결 리스트의 Head는 큐의 Front가, 연결 리스트의 Tail은 큐의 Rear가 된다.

 

그러나 연결 리시트는 배열보다 구현하는 것이 어려울 수 있어 코딩테스트에서는 배열을 사용하는 것이 좋다고 한다.

 

코드 실행 결과

 

---

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript