저번에 자료구조 중 스택에 대해 공부를 했었다.
이번에는 자료구조 삼인방 스택, 큐, 덱 삼인방 중 큐 (Queue), 덱 (Deque)에 대해서 공부를 하였다!
큐(Queue)
한쪽에서만 데이터의 삽입 삭제가 이루어졌던 스택과 달리 큐는 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다.
FIFO (First In First Out) 으로 동작하며 데이터가 삽입되는 곳을 rear, 데이터가 제거되는 곳을 front 라 한다.
데이터를 삭제하기 전에는 큐가 empty 한지, 큐에 데이터를 추가하려 할 때는 큐가 full 인지 확인 후 진행해야 한다.
큐의 핵심 연산
1. enqueue(x) : 큐에 데이터를 넣는 연산. 주어진 요소 x를 큐의 맨 뒤에 추가한다.
2. dequeue() : 큐가 비어있지 않으면 맨 앞에 있는 요소를 삭제하고 반환한다.
선형 큐 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 - Endend Queue 의 줄임말이다.
한쪽에서만 삽입, 다른 한쪽에서만 삭제가 가능했던 큐와 달리 양쪽 front, rear 에서 삽입 삭제가 모두 가능한 큐를
의미하는 자료구조이다.
연속적인 메모리를 기반으로 하는 시퀀스 컨테이너이고 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다.
또한 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다.
vector 보다는 좋은 성능을 가지지만 앞, 뒤에서의 삽입 삭제 성능에 비해 중간에 삽입 삭제하는 것은 성능이 좋지않다!
덱의 연산
1. addFront(e) : 주어진 요소 e를 덱의 맨 앞에 추가한다.
2. deleteRear() : 덱이 비어있지 않으면 맨 뒤에 있는 요소를 삭제하지 않고 반환한다.
3. getFront/Rear() : 덱이 비어있지 않으면 맨 앞/ 맨 뒤에 있는 요소를 삭제하지 않고 반환한다.
시간 복잡도
삽입 삭제 연산은 마찬가지로 O(1) 의 시간 복잡도를 가지고, 스택/큐와 달리 index를 통해 요소들에 탐색이 가능하므로 이 역시 O(1) 의 시간 복잡도를 가진다.
장단점
- 데이터의 삽입 삭제가 빠르고 앞, 뒤에서 삽입 삭제가 모두 가능하다.
- 가변적크기
- index를 통해 임의의 원소에 바로 접근이 가능하고
- 새로운 원소 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
- 중간에서의 삽입 삭제가 어렵다.
- 스택, 큐에 비해 비교적 구현이 어렵다.
활용
- 데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
- 데이터의 크기가 가변적일 때
참고
[자료구조] 스택 Stack, 큐 Queue, 덱 Deque
새로운 시리즈는 자료구조이다. 진즉좀 정리 해 둘걸,,, 다 아는 내용이어도 이렇게 정리하려고 하니 참 시간도 꽤 걸리고 더 깊게 공부해야 하기도 하고,,, 암튼 자료구조 시리즈의 첫번째 포스
velog.io
https://nul-problg.tistory.com/20
[자료구조 이론] 큐(Queue) + 덱(Deque ; Double Ended Queue) 이해하기
큐는 스택과 함께 언급되고 또 비교되는 자료구조이다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이것이 스택과 큐의 유일한
nul-problg.tistory.com
'자료구조' 카테고리의 다른 글
| [자료구조] int 와 Integer 의 차이점? (0) | 2023.01.09 |
|---|---|
| [자료구조] 스택 (Stack) (0) | 2023.01.06 |