스택(Stack)과 큐(Queue)

스택(Stack)과 큐(Queue)

이미지 출처 - yhdc.log

오늘은 데이터 자료구조 - 스택과 큐에 대해서 정리해보고자 한다.

---

스택(Stack)

스택 예시 이미지 (이미지 출처 - 튜나의 개발일기)

스택(Stack)이란 문자 그대로 '쌓아 올린다는 것'을 의미한다.

스택이라는 자료구조 또한 책을 쌓는 것과 같이 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

특징

스택은 위 이미지와 같이 같은 구조의 데이터를 정해진 방향으로만 쌓을 수 있으며 top으로 정한 곳을 통해서만 접근 가능하다.

top은 가장 위에 있는 자료, 즉 가장 최근에 들어온 자료를 가르키고 있으며 사입되는 새 자료는 기존 top이 가리키던 자료의 위에 쌓이게 된다.

스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.

스택에서 top을 통해 삽입하는 연산을 'push', 삭제하는 연산을 'pop'이라고 한다.

 

따라서 스택은 시간 순서에 따라 자료가 쌓이게되며 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 지닌다.

이러한 스택의 구조를 후입선출(LIFO - Last In First Out)구조라 한다.

활용 사례

1. 웹 브라우저 방문기록(뒤로가기)
2. 실행 취소(undo)

 

 

큐(Queue)

큐 예시 이미지 (이미지 출처 - 튜나의 개발일기)

큐(Queue)는 사전적으로 '줄', 혹은 '줄을 서서 기다리는 것'을 의미한다.

데이터 자료구조에서의 큐 역시 이와 같이 줄을 서서 차례로 데이터를 처리하는 선입선출(FIFO - First In First Out)방식의 자료구조를 의미한다.

특징

top을 통해서만 삽입, 삭제가 이뤄지는 스택과 달리 큐는 한쪽 끝에서는 삽입이, 다른 쪽 끝에서는 삭제가 이뤄진다.

이때 삭제 연산이 수행되는 곳을 프론트(Front), 삽입 연산이 이뤄지는 곳을 리어(Rear)라 칭한다.

이를 따라 큐의 가장 첫 원소를 프론트, 가장 끝의 원소를 리어라 부른다.

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, 리어 원소는 가장 늦게 들어온 마지막 원소가 되는 것이다.

활용

1. 은행업무
2. 프린터의 인쇄 대기열

---

Reference

개발자 Miro - [자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!

튜나의 개발일기 - [자료구조] 스택(STACK), 큐(QUEUE) 개념/비교/활용 예시