[자료구조] 스택 Stack, 큐 Queue, 덱 Deque

새로운 시리즈는 자료구조이다.
진즉좀 정리 해 둘걸,,, 다 아는 내용이어도 이렇게 정리하려고 하니 참 시간도 꽤 걸리고 더 깊게 공부해야 하기도 하고,,,

암튼 자료구조 시리즈의 첫번째 포스팅은 스택, 큐, 덱 삼인방이다!

스택 Stack

먼저 스택은 한 쪽 끝에서만 자료를 넣고 빼는 작업이 이루어지는 자료구조이다. LIFO (Last In First Out) 방식으로 동작하며 가장 최근에 스택에 삽입된 자료의 위치를 top 이라 한다.

스택의 stack.push 는 top 에 새로운 데이터를 추가하고, stack.pop 은 가장 최근에 삽입된 데이터가 스택에서 삭제된다.

스택의 맨 위 요소, top 에만 접근이 가능하기 때문에 top 이 아닌 위치의 데이터에 대한 접근, 삽입, 삭제는 모두 불가능하다.

스택이 비어있을 때 stack.pop을 시도하는 것을 stack underflow 라 하고 스택의 크기가 비어있을 때 stack.push 를 시도할 때 stack overflow 가 발생한다.

시간 복잡도

top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.

장단점

• top 을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다
• top 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능하다. 탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.

활용

• 재귀 알고리즘
• DFS 알고리즘
• 작업 실행 취소와 같은 역추적 작업이 필요할 때
• 괄호 검사, 후위 연산법, 문자열 역순 출력 등

큐 Queue

한쪽에서만 데이터의 삽입 삭제가 이루어졌던 스택과 달리 큐는 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다. FIFO (First In First Out) 으로 동작하며 데이터가 삽입되는 곳을 rear, 데이터가 제거되는 곳을 front 라 한다. 데이터를 삭제하기 전에는 큐가 empty 한지, 큐에 데이터를 추가하려 할 때는 큐가 full 인지 확인 후 진행해야 한다.

선형 큐 Linear Queue

• 선형 배열을 사용하여 구현된 큐
• 삽입을 위해서는 계속해서 요소들을 이동시켜야 함
• front, rear 는 증가만 하는 방식, 실제로는 front 앞쪽에 공간이 있더라도 삽입할 수 없는 경우가 발생할 수 있음

원형 큐 Circular Queue

• 선형 큐의 단점을 보완
• front = 맨 첫번째 요소 바로 앞을 가리킴
• rear = 마지막 요소 가리킴
• 큐 empty 상태 : front == rear
• 큐 full 상태 : front == (rear+1) % MAX_QUEUE_SIZE
• 공백 상태와 포화 상태를 구분하기 위해 하나의공간을 비워둠

시간 복잡도

큐 역시 front, rear 의 위치로 데이터 삽입 삭제가 바로 이루어지기 때문에 원소 삽입, 삭제의 시간 복잡도는 O(1) 이다.

장단점

• 데이터 접근, 삽입, 삭제가 빠르다.
• 큐 역시 스택과 마찬가지로 중간에 위치한 데이터에 대한 접근이 불가능하다.

활용

• 데이터를 입력된 순서대로 처리해야 할 때
• BFS 알고리즘
• 프로세스 관리
• 대기 순서 관리

덱 Deque

Deque 는 Double - Ended Queue 의 줄임말이다!
한쪽에서만 삽입, 다른 한쪽에서만 삭제가 가능했던 큐와 달리 양쪽 front, rear 에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조이다.

연속적인 메모리를 기반으로 하는 시퀀스 컨테이너 이고 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다.

또한 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다. vector 보다는 좋은 성능을 가지지만 앞, 뒤에서의 삽입 삭제 성능에 비해 중간에 삽입 삭제 하는 것은 성능이 좋지 않다!

시간 복잡도

삽입 삭제 연산은 마찬가지로 O(1) 의 시간 복잡도를 가지고, 스택/큐와 달리 index 를 통해 요소들에 탐색이 가능하므로 이 역시 O(1) 의 시간 복잡도를 가진다.

장단점

• 데이터의 삽입 삭제가 빠르고 앞, 뒤에서 삽입 삭제가 모두 가능하다
• 가변적 크기
• index 를 통해 임의의 원소에 바로 접근이 가능하고
• 새로운 원소 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
• 중간에서의 삽입 삭제가 어렵고
• 스택, 큐에 비해 비교적 구현이 어렵다.

💡 vector 에 비해 deque가 메모리 추가 할당이 더 저렴한 이유!
vector는 데이터를 저장하는 버퍼를 1차원 배열 형태로 관리하기 때문에 vector 는 메모리를 추가로 할당할 경우 기존 메모리 영역의 2배만큼 메모리를 추가로 할당하고 기존의 요소를 복사한다.


deque 는 chunk 를 이용해 관리한다. chunk 는 메모리 영역 군데군데에 흩어져 있고 컨테이너에서 내부적으로 chunk 에 바로 접근이 가능하도록 인터페이스를 제공한다. 때문에 처음에 할당받은 chunk 를 모두 사용중이라면 deque 는 새로운 chunk 를 하나 만드는 것 만으로 메모리 추가 할당이 완료된다!

활용

• 데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
• 데이터의 크기가 가변적일 때

Reference

Deque
[자료구조] 스택(Stack), 큐(Queue), 덱(Deque)
[자료구조] 큐 Queue, 선형 큐, 원형 큐 구현