[자료구조] 스택(Stack) , 큐(Queue)에 대해 파헤쳐보자!

개발 지식을 쌓다보면 자연스레 접하게 되는 스택(Stack), 큐(Queue).

개발자라면 무조건 알아야하는, 아주 중요한 데이터 구조인데

사실 이들은 실제로 프로그래밍 언어들에서 존재 하지 않는, 일종의 '규칙'이다.

 

◼ 스택(Stack)

 

Stack의 정의 / 출처 : http://www.incodom.kr/%EC%8A%A4%ED%83%9D

 

스택은 차곡차곡 쌓아 올린다는 것을 의미하는 단어이다.

즉, 자료구조에서 말하는 스택은 위의 이미지처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말하며,

시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가진다.

 

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

 

◼ 스택의 활용 예시

 

- 웹 브라우저 방문 기록 / 뒤로 가기 : 가장 나중에 열린 페이지부터 다시 보여준다.

- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.

- 실행 취소(Ctrl + Z) : 가장 나중에 실행된 것부터 실행을 취소한다.

- 후위 표기법 계산

- 수식의 괄호 검사 ( 연산자 우선순위 표현을 위한 괄호 검사)

 

◼ 큐(Queue)

 

큐(queue)는 스택과는 반대로, 먼저 입력된 데이터가 먼저 나오는 선입선출(FIFO : First-In-First-Out)의 구조로

저장되는 형식을 말한다.

 

FIFO(First In First Out) 방식. 출처 : https://devuna.tistory.com/22

정해진 한 곳을 통해서 삽입, 삭제가 이루어지는 스택(Stack)과는 달리

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여

각각의 연산작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)

프론트에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.

 

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
• 접근방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

 

◼ 큐의 활용 예시

 

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

출처: https://devuna.tistory.com/22 [튜나 개발일기]