251104 언리얼엔진 본캠프 59일차 STACK과 QUEUE, DEQUE

STACK과 QUEUE, DEQUE

스택(STACK)과 큐(QUEUE), 덱(DEQUE)은 자료구조에 관한 개념으로서 여러 가지 자료구조 중에 선형 자료구조에 해당하는 대표적인 녀석들이다. 간단하다고 생각하고 대충 보고 넘어갈 수 있지만 기본적인 만큼 굉장히 중요한 녀석이기에 오늘 한번 다루어 보도록 하자.

 

Stack

스택은 말 그대로 쌓는 형식의 데이터 구조로서 후입선출(LIFO, Last In First Out)의 형태를 가지고 있다. 예컨데 큰 통에 블록을 일자로 차례대로 쌓는다 생각하자. 가장 먼저 들어간 블록은 가장 밑에 깔리게 되며 그 후로 들어오는 블록들이 차례대로 위로 쌓일 것이다. 이 상황에서 블록을 꺼내기 위해서는 위에서부터 차례대로 꺼내게 되어 사실상 들어간 순서의 역순으로 블록이 나오게 될 것이다. 스택도 이와 같다. 데이터를 먼저 들어오는 순서대로 쌓아두고 꺼낼 때 제일 나중에 들어온 데이터부터 순차적으로 꺼내서 쓰게 된다. 이를 좀 더 전문적으로 말하자면 스택은 데이터의 삽입과 삭제가 한 방향(통의 입구)에서만 이루어지게 된다. 스택에서는 가장 위에 있는 데이터, 즉 가장 최근에 들어온 데이터를 top이라고 부르며 데이터를 넣는 과정을 push, 빼는 과정을 pop이라고 부르게 된다. 이러한 형식의 스택 자료구조는 여러 곳에서 사용되는데 대표적인 게 실행취소(Ctrl + z)가 있다.

 

Queue

큐는 스택과는 다르게 선입선출(FIFO, First In First Out)을 가지고 있는데 말 그대로 먼저 들어온 데이터가 가장 먼저 나가게 되는 자료구조이다. 예컨데 원형 관에 바닥을 붙이고 블록을 넣은 다음 바닥을 제거하면 어떻게 될까? 가장 밑에 쌓인(가장 먼저 들어온 블록)이 먼저 아래로 떨어질 것이다. 이처럼 큐는 한쪽에서는 데이터의 삽입이 이루어지고 다른 한쪽에서는 데이터의 삭제가 가능한 형태로 구성되어 있다. 큐에서의 데이터 삽입은 Enqueque라고 하며 데이터의 삭제는 Dequeque라고 한다. 그리고 가장 먼저 저장된 데이터를 Front, 가장 최근에 추가된 데이터를 Rear라고 한다. 이러한 방식의 큐 자료구조는 프린터의 대기열과 같은 곳에서 사용된다.

 

Deque

덱은 큐 2개를 겹쳐놓은 것과 같은 구조를 가지고 있어 Double ended Queue라고 부르며 Deque는 이의 약자이다. 삽입과 삭제의 방향이 정해진 Queue와 다르게 Deque는 양 방향에서 모두 입, 출력이 가능한 자료구조가 된다.

 

오늘은 선형 자료구조의 형태만 다루어 보았지만 Queue만 하더라도 원형큐, 우선순위 큐와 같이 여러 형태가 존재한다. 이는 기회가 되면 다음에 다루어 보도록 하겠다.