[알고리즘] 자료구조 개념 / 스택, 큐, 덱, 힙 ( Stack, Queue, Deque, Heap)

 

자료구조 개념

 

 

자료구조란? 데이터를 구조적으로 활용하기 위해 표현하는 것을 말한다.

자료구조는 알고리즘 공부 전 필수적으로 알고 넘어가야 하는 부분이며, 알고리즘 문제의 대부분은 자료구조를 사용하여 풀어나가는데 이 때 어떤 자료구조를 사용하냐에 따라 문제의 난이도가 바뀔 수 있다.

 

 

 

 

자료구조의 목차를 오른쪽에 간략하게 표현해보았다. 자료구조에서는 이번 글에서 다루는 스택, 큐, 덱, 힙과 같이 지식이 필요한 부분들 이외에도 평상시에  배우는 언어에 기본적으로 존재 하는 배열(리스트)와 같이 기본적인 자료의 표현도 자료구조라고 할 수 있다.

 

 

 

알고리즘을 공부하기 위해서는 선행적으로 자료구조의 이해는 필 수 이다. 한 알고리즘에 한 가지의 자료구조 또는 여러 가지의 자료구조가 조합되어 사용되기 때문이다.

왼쪽과 같이 깊이우선탐색(DFS)은 그래프의 자료구조에서 스택(Stack) 자료구조를 활용하여 깊이를 우선으로 탐색하는 알고리즘이고, 넓이우선탐색(BFS)는 큐(Queue) 또는 덱(Deque)를 활용하여 넓이를 우선으로 탐색하는 알고리즘이다. 이와 같이 알고리즘 공부를 하기위해서는 선행적으로 자료구조의 학습이 필요하다는 것을 알 수 있다.

 

 

 

스택 (Stack)

 

스택(Stack) 후입선출(Last In Frist Out - LIFO)의 특성을 가지는 자료구조이다. 

스택은 Push(입력)과 Pop(출력) 두 가지의 기능을 가지고 있으며, Pop시에 스택에 제일 늦게 입력한 부분이며 위쪽인 Top에서 Pop하여 출력한다.

 

 

스택을 이해하기 위한 예시로

책상에 책을 쌓아둘 때와 같이 하나 하나 위로 점점 쌓아가고 ( Push / 입력 ),

책을 꺼낼 때에는 맨 위(Top)에서 부터 하나씩 꺼내 읽는다( Pop / 출력 ).

 

 

 

스택은 선형구조이고 입력 시 차곡차곡 쌓아올리며, 출력할 때에는 마지막으로 쌓아올린 맨위에 있는 것을 꺼내 사용한다.

스택의 코드 구현은 백준의 1874번 스택의 문제를 통해 설명하겠다.

 

[백준] 10828번 스택 ( 파이썬 / c언어 )

 

 

큐 (Queue)

 

큐(Queue)는 선입선출(First In First out - FIFO)의 특성을 가지는 자료구조이다.

큐는 Push(입력)과 Pop(출력) 두 가지의 기능을 가지고 있으며, Push 동작에는 Rear라고 불리는 가장 마지막 부분에 삽입하고, Pop 동작에는 Front라 불리는 가장 먼저 입력된 자료가 있는 앞쪽에서 출력한다.

 

 

 

Queue의 뜻은 표 같은것을 구매하기 위해 줄 서는 것을 의미하는데, 줄을 서려면 맨 마지막 줄 선 사람 뒤(Rear)에 서는데 이것을 Push(입력)이라 할 수 있고, 가장 먼저 줄을 선 사람(Front)이 표를 구매하고 줄을 나가는 것을 Pop(출력)이라고 할 수 있다.

큐를 이해하기 위한  다른 예시로 터널을 생각하면 이해가 쉽다. 터널은 한 쪽으로 통행하는데 차량이 통과할  때 한 쪽 입구(Rear) 로 들어가고(Push),  다른 출구(Front)로 나오게 된다(Pop).

 

 

 

큐는 터널예시와 같이 한 쪽 방향으로 진행하는 선형구조라고 이해하면 쉽다. 스택과 반대로 출력시에 Last-In이 아닌 First-In이다. 

큐의 코드 구현은 백준의 10845번 큐의 문제를 통해 설명하겠다.

 

[백준] 10845번 큐 ( 파이썬 / c언어)

 

덱 (Deque)

 

 

 

덱(Deque)은 앞뒤로 모두 입력, 출력이 가능한 (Double-ended Queue)로써 큐를 활용하여 만들어진 자료구조이다.

덱은 Push(입력)와 Pop(출력)이 Front 와 Rear 에서 모두 가능하다.

 

 

덱(Deque)은 Push와 Pop이 비교적 자유롭다는 장점을 활용하여, 스택과 큐 구현이 모두 가능하다.

덱의 제일 큰 장점은 활용 가능 범위가 넓다는 것이다. Rear에서 Push연산과 Pop연산만 시행할 시에 스택(Stack)을 구현할 수 있고, Rear에서 Push연산과 Front에서 Pop연산시 큐(Queue)를 구현 할 수 있다.

 

 

스택과 큐의 장점과 특성들이 필요할 때 덱의 특성인 Push와 Pop이 비교적 자유롭기에 덱(Deque)를 사용한다.

 

덱의 코드 구현은 백준의 10866번 덱의 문제를 통해 설명하겠다.

[백준] 10866번 덱 ( 파이썬 / c언어 )

 

 

힙 ( Heap)

 

 

 

 

힙(Heap)은 스택(Strack), 큐(Queue), 덱(Deque)처럼 선형구조가 아닌 트리의 일종으로 비선형 구조이다.

힙(Heap)은 최대 힙(Max-Heap), 최대 힙(Min-Heap)으로 분류할 수 있는 완전이진트리이다.

 

 

 

힙(Heap)은 스택(Strack), 큐(Queue)와 같이 자료가 입력된 순서와 출력시 먼저입력이 된 자료거나 나중에 입력이 된 자료와 같이 순서가 중요한것이 아닌, 최댓 값 또는 최솟 값을 찾을 때 유용하게 활용된다.

꼭  최댓 값 또는 최솟 값을 찾을 때 이외에도 자료에서 정렬시에 "몇번째 원소" 등을 찾는것에 유용하다.

 

 

 

힙(Heap)의 단점으로는 스택(Strack), 큐(Queue)와 같이 순서변화가 없어 입출력에서 단순한 구조가 아닌, 입/출력 시에 다시 재 정렬 해야한다는 단점이 있다. 

위의 그림을 예시로 최대 힙인 자료구조에서 원소 15를 삭제 또는 출력을 하면, 전체적인 구조의 재정렬과  완전 이진트리의 구조가 바뀌면서 많은 연산을 수행하게 된다.

 

 

이처럼 덱(Deque)은 원소의 입출력이 잦은 경우 보다는 입출력이 적고 최대, 최소와 같이 자료의 Level이 필요 할 때 사용하면 유용한 자료구조이다. 

 

 

덱의 코드 구현은 백준의 11279번 최대 힙의 문제를 통해 설명하겠다.

[백준] 11279번 최대 힙 ( 파이썬 )