[Data Structure] 자바스크립트로 스택 (Stack) & 큐(Queue) 구현하기

June hyoung Park·2020년 10월 21일
0

자료구조

목록 보기
1/3
post-thumbnail

자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 효율적인 프로그램을 작성하기 위해선 저장공간의 효율성과 실행시간의 신속성이 매우 중요하므로 자료구조에 대한 어느정도의 이해는 꼭 필요하다고 한다.

Stack

스택은 자료구조에서 매우 기본적인 개념이고, 스택을 포함하는 다른 자료 구조들도 존재하기에 (ex. DFS) 매우 중요한 개념이다. 먼저 스택(stack)이란 쌓아 올린다는 것을 의미한다. 즉 스택이란 책을 쌓는 것처럼 차곡 차곡 쌓아 올린 형태의 자료구조를 의미한다.

스택은 후입선출 (LIFO - Last In First Out)이란 구조적 특징을 갖고있기때문에 자료가 추가 될때 마다 최 상단(top)의 자료의 위에 쌓이게 된다. 또한 삭제시에도 top을 통해서만 가능하며, 스택에 데이터를 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'라 한다. (자바 스크립트 내장 메서드 push, pop)과 동일한 기능을 한다.

구현

배열을 사용하지않고, 객체와 함께 numeric key를 이용해서 구현했으며, Stack이란 생성자 함수를 만든뒤 size() 메서드는 현재의 top 값을 반환하고, push메서드는 인자로 element를 받은 뒤, storage라는 객체에 증가된 top값을 키로 갖는 element를 추가한다. 또한 pop() 메서드는 우선 현재 최 상단의 데이터를 변수에 저장한뒤 객체의 마지막 프로퍼티를 제거한 후 이를 반환해주는 방식으로 구현하였다.

Queue

큐는 스택과 매우 흡사한 구조를 갖고있지만, 큰 차이점이있다. 이는 바로 스택과는 달리 선입선출(FIFO - First in first out)적인 구조적 특징을 갖고있다는 것인데, 이는 마치 매표소에서 줄을 기다리는 것처럼 먼저 들어온것이 먼저 나가는 형태를 갖고있다.

정해진 곳(top)에서만 데이터의 삽입 및 삭제가 이루어지는 스택과는 달리, 삭제만 수행되는 프론트(front)와 삽입만 수행되는 리어(rear)로 나뉘어져 양 끝에서 작업이 이루어진다. 이때, 큐의 리어(rear)에서 이루어지는 삽입 작업을 enQueue, 프론트(front)에서 이루어지는 삭제 작업을 디큐(dnQueue)라고 한다.

구현

큐 또한 배열을 사용하지않고, 객체와 함께 numeric key를 이용해서 구현 했으며, 사이즈를 출력하는 size 메서드 호출 시 현재 front값을 반환하게끔 해줬다. 또한 큐이기 때문에 스택과는 달리 enQueue 시 첫번째 삽입은 storage에 넣고, 두번째 삽입부터 Object.values() 메서드를 이용해서 값들을 배열로 만든 뒤 element가 unshift 메서드를 통해 최근 데이터의 뒤에 쌓이게끔 구현했다. 그후엔 storage를 비워준 후 반복문을 통해 위치가 역순으로 변한 valuse 배열을 다시 storage에 넣어주는 식이다.

실제 큐의 작동 방식처럼 삽입한 데이터가 최근 데이터의 뒤로 삽입되며, 데이터 삭제는 front에서만 이뤄진다.

profile
Take me home~~~~

0개의 댓글