자료구조를 공부할때 가장 먼저 접하는것은 “스택(Stack)”과 “큐(Queue)” 입니다. 제가 느끼기에는 우리 생활에서 가장 많이 사용하고 있는 자료구조가 아닐까? 라는 생각을 합니다.
이 글에서는 스택과 큐의 간단한 개념과 관련된 용어 그리고 실제로 어디서 쓰이고 있는지를 알아보려고 합니다.
1. Stack
Stack의 경우 후입 선출 즉 “Last In First Out”, “가장 먼저 들어간 것이 가장 마지막에 나온다”는 알고리즘 입니다. 더 쉽게 이야기 하자면, 차곡차곡 쌓아 올린 구조라고 할수 있습니다.
JavaScript에서 Array에서 배열에 어떠한 요소를 삽입하는 API로 “push()”를 많이 사용하는데요. 이 연산을 사용하면 기존 배열의 맨 끝에 요소를 추가해줍니다. 또한, pop이라는 메소드를 이용해서 배열의 가장 마지막 요소를 제거 할 수 도 있습니다. 즉, 배열에 이런 요소들을 push하고 pop하는 방식을 스택에서 요소를 삽입하고 삭제하는 연산과 동일 합니다.
정리하자면, 스택을 통해서 요소를 넣고 빼는 것은 한군데 top을 통해서만 가능하고 이렇게 요소를 삽입하고 삭제하는 연산을 push와 pop이라고 부릅니다.
비어있는 스택에서 원소를 추출할때는 Stack Underflow라고 말하고, 스택이 넘치는 경우를 stack Overflow라고 말합니다. 잘못된 재귀 연산을 통해 끝나지 않은 함수를 무한으로 호출할 경우 JavaScript의 스택오버플로우 에러가 발생하는것과 동일합니다.
활용 예시
- Git Stash ⇒ 변경 사항을 임시로 저장하고 싶을때 사용하는 명령어 인데, 이때 스택 자료구조를 이용해서 저장합니다. git stash pop 명령어를 입력할때, 가장 최근에 삽입한 변경사항이 리턴 되는 것과 동일합니다.
- 웹 브라우저의 방문 기록 : 웹 브라우저는 페이지를 새로 이동 (push) 했을 때와 뒤로가기(pop)할때 스택 자료구조를 사용합니다.
- 자바스크립트의 Call Stack 도 이런 스택 자료구조를 이용합니다.
1. Queue
큐의 경우 선입 선출 ‘First in First out’로 요소를 삽입, 삭제 합니다. 즉 “먼저 들어간 것이, 가장 처음으로 나온다”라는 의미입니다.
큐에서 요소를 삽입하고 삭제하는 용어는 스택과 다른데요. 삽입 연산 : enQueue라고 부르고, 삭제 연산을 : deQueue라고 합니다. 또한, 삽입이 이루어지는 곳을 Rear(리어), 그리고 삭제가 일어나는 곳을 (Front)라고 합니다.
활용 예시
- 자바스크립트에서 처리해야 할 일을 순서대로 담아 놓는 역할을 하는 태스크 큐가 이런 자료구조를 사용합니다.
- 우리가 테이블링/ 캐치테이블과 같은 어플에서 식당에 대기줄을 서는 것도 Queue라고 할 수 있습니다.
공부하면서, 스택과 큐라는 자료구조가 실제로는 우리 실생활에서 많이 사용되고 있는 형태라는것을 알 수 있습니다.
