[Data Structure] Javascript를 이용한 stack, queue 이해하기

이번에는 javascript를 이용해서 여러 가지 자료구조 중 stack과 queue에 대해서 알아보겠습니다.

1. Stack(스택)
   stack에 개념에 대해서 알아보겠습니다.

게임을 해보신 분들이라면 스택이 쌓인다 라는 말을 들어보신 적이 있으실 겁니다. stack은 '쌓다'라는 뜻을 갖고 있습니다.

그럼 자료구조에서 stack이라고 하면 어떤 느낌으로 자료를 보관하고 있는지 감이 오시나요? 다음의 그림을 보시죠.

제가 그렸지만 참 잘 그렸습니다.

스택의 구조는 위의 그림과 같습니다. 밑에부터 차곡차곡 쌓여 먼저 저장한 데이터는 가장 마지막에 나오게 됩니다.

우리는 이것을 First In, Last Out을 줄여서 FILO라고도 부릅니다.

Javascript에서 stack의 구조에 사용되는 Property와 method를 알아봅시다.

Property

• top : top은 말 그대로 stack에 가장 위에 쌓여있는 데이터를 나타냅니다. 정확히는 그 데이터의 위치(index) 값입니다.

• maxSize : maxSize는 해당 저장소의 최대 크기를 나타냅니다.

• stackArray : stackArray는 해당 저장소 자체입니다.

Method

• push() : push()는 배열(Array) 메소드로 배열의 가장 뒤에 값을 추가시키는 메소드입니다.

• pop() : pop() 또한 배열(Array) 메소드로 push()와는 반대로 배열의 가장 뒤의 값을 삭제하는 메소드입니다. pop()으로 꺼낸 값은 출력하거나 다른 곳에 할당할 수 있습니다.

• empty() : empty()는 저장소가 비어있는지 확인합니다. 저장소의 비움 여부에 따라 boolean(true/false)으로 값을 반환합니다.

• size() : size()는 현재 저장소에 저장되어있는 데이터가 몇 개 인지 체크합니다

2. Queue(큐)
   이번에는 queue에 대해 알아보겠습니다.

큐는 우리가 일상에서 가장 흔하게 접할 수 있는 형태의 구조라고 생각합니다.

'선입선출' 다들 들어보셨죠? 무언가를 구매하기 위해 줄을 기다리거나 할 때의 형태가 바로 queue입니다.

큐는 First In, First Out을 줄여서 FIFO라고 불립니다.

다시 제가 그린 기깔난 그림을 보시죠.

그림만 봐도 바로 이해가 되시죠?

처음에 저장된 데이터가 가장 먼저 나가고, 나중에 들어온 데이터가 마지막에 나가는 구조입니다.

바로 property와 method에 대해 알아보겠습니다.

property

• front : 가장 먼저 들어온 데이터의 위치(index)를 나타냅니다.

• rear : 새로운 데이터가 들어갈 위치(index)를 나타냅니다.

• queueArray : queue저장소를 나타냅니다.

method

• push() : queue도 stack과 동일하게 가장 마지막의 위치에 데이터가 쌓이기 때문에 push()를 사용합니다.

• shift() : shift() 메소드는 배열의 가장 앞에 있는 값을 삭제하는 메소드입니다. 데이터를 꺼내는 위치만 다를 뿐 pop()메소드와 동일하게 다른 곳에 꺼낸 값을 출력하거나 할당할 수 있습니다.

• empty : empty()는 저장소가 비어있는지 확인합니다.

• size : size()는 현재 저장소에 저장되어있는 데이터가 몇 개 인지 체크합니다

#pseudo code
마지막으로 stack과 queue가 어떻게 작동하는지 pseudo code를 통해 살펴보겠습니다.

Stack

• top을 0으로 초기화해줍니다.

• push()

1. stackArrary를 확인해서 stackArray가 가득 차있지 않다면 마저 진행하고, 가득 차있다면 "stackArray is full!"을 출력합니다.

2. top위치에 push()로 넣은 값을 삽입합니다.

3. top의 값을 1 증가시킵니다.

• pop()

1. stackArrary를 확인해서 stackArray에 값이 있다면 마저 진행하고, 값이 없다면 "stackArray is empty!"를 출력합니다.

2. top의 위치에 있는 데이터를 내부 변수에 저장하고 해당 데이터를 삭제합니다.

3. top의 값을 1 감소시킵니다.

• empty()

stackArray의 0번째 요소부터 top까지 반복문을 돌면서 반복문의 index값이 1보다 커지면 false를 반환합니다. 아니라면 true를 반환합니다.

• size()

stackArray의 0번째 요소부터 top까지 반복문을 돌면서 마지막 요소의 index값 +1을 반환합니다.

Queue

• front와 rear를 0으로 초기화합니다.

• push()

1. queueArrary를 확인해서 queueArray가 가득 차있지 않다면 마저 진행하고, 가득 차있다면 "queueArray is full!"을 출력합니다.

2. rear위치에 push()로 넣은 값을 삽입합니다.

3. rear의 값을 1 증가시킵니다.

• shift()

1. queueArrary를 확인해서 queueArray에 값이 있다면 마저 진행하고, 값이 없다면 "queueArray is empty!"를 출력합니다.

2. front의 위치에 있는 데이터를 내부 변수에 저장하고 해당 데이터를 삭제합니다.

3. front의 값을 1 증가시킵니다.

• empty()

queueArray의 0번째 요소부터 top까지 반복문을 돌면서 반복문의 index값이 1보다 커지면 false를 반환합니다. 아니라면 true를 반환합니다.

• size()

queueArray의 0번째 요소부터 top까지 반복문을 돌면서 마지막 요소의 index값 +1을 반환합니다.