🌿 스택 (Stack)
LIFO(Last In First Out), 후입선출 형태의 자료구조입니다.
상자 위에 물건을 차곡차곡 쌓는 형식이죠.
스택은 기본적으로 한 방향에서만 데이터를 넣고 꺼내는게 가능합니다.
가장 먼저 들어간 데이터가 나중에 들어온 데이터들의 아래에 깔리고, 순서대로 나갈 때는 가장 마지막에 추출되죠.
JavaScript에서 스택은 굳이 별도로 구현하지 않아도 사용 가능하긴 합니다.
Array (배열) 자료형에 이미 기능들이 구현되어있거든요.
하지만 알고리즘을 구현하는 것과 배열을 가져다만 쓰는 것은 차이가 있으니 짚고 넘어가봅니다.
아래 구현 구조는 스택의 기본 동작에 대한 이해를 돕습니다.
- 기본 구현 구조
-
push(element): 빈 스택에 데이터를 집어넣습니다. -
pop(): 가장 마지막 데이터를 추출하고 해당 값을 리턴합니다. -
isEmpty(): 스택이 비어있는지 여부를Boolean값으로 리턴합니다. -
peek(): 가장 마지막 데이터를 리턴합니다.pop()과는 달리 데이터를 추출하지는 않습니다. -
size(): 스택의 데이터 개수, 즉 크기를 리턴합니다. -
indexOf(element): 스택 내에서element의 위치를 리턴합니다. -
includes(element): 스택 내에element데이터가 존재하는지 여부를Boolean값으로 리턴합니다.
🌿 큐 (Queue)
FIFO(First In First Out), 선입선출 형태의 자료구조입니다.
티켓을 사기 위해 줄을 서있는 모습을 떠올려보세요.
큐는 스택과 달리 양방향으로 데이터가 추가되고, 삭제됩니다.
단지 동일한 점은 데이터가 하나씩 추가 및 삭제된다는 점이겠군요.
❗️주의할 점은 양 방향이 추가와 삭제를 모두 담당하는 것은 아닙니다.
한쪽은 추가(enqueue) 를 담당하고, 다른 한쪽은 삭제(dequeue) 를 담당해요.
아래 그림처럼 뒤쪽에서부터 데이터를 추가하고, 앞쪽에서부터 데이터가 추출됩니다.
따라서 구현할 때는 front 와 back 을 나타내는 인덱스가 있어야하죠.
- 기본 구현 구조
-
enqueue(element): 큐의 뒤쪽에 데이터를 추가합니다. -
dequeue(): 큐의 앞쪽에서 데이터를 추출 후 리턴하며, 빈 자리를 처리하기 위해front의 인덱스를 조정합니다.
따로 기재되지 않은 isEmpty(), size() 메서드는 스택과 동일한 기능을 수행합니다.
마찬가지로 배열 데이터 타입으로 구현해봤습니다.
