[자료구조] Queue & Deque - 큐와 덱

일상 회고록·2024년 7월 8일

Deque queue 덱 자료구조 큐

자료구조 모음집

목록 보기

4/7

안녕하세요!

오늘의 주제는 Queue와 Deque 자료구조입니다 ㅎㅎ

하나가 아닌 두가지를 함께 다루는 이유는 두 자료구조가 비슷한 형태를 가지고 있고, 연장선에 있기 때문에 같이 정리하는 것이 좋을 것이라 생각했습니다!

직전 포스트 주제인 Stack 자료구조도 떠올리시면서 보시면 좋을 것 같습니다

그럼 시작하겠습니다~!

1. 개념

Queue - 큐와 Deque - 덱 모두 선형 구조로 데이터를 저장하는 자료구조입니다.

구분되어 사용되는 이유는 데이터의 삽입과 삭제에 대한 원칙이 다르기 때문인데요!

하나씩 살펴보도록 하겠습니다.

1-1. Queue

큐는 데이터의 선입선출, 즉 First In First Out - FIFO의 원칙을 가지고 있습니다.

먼저 저장된 데이터가 가장 먼저 빠져나오게 됩니다. (정확히 스택과 반대)

스택과 마찬가지로 중간 데이터에 대한 임의 접근은 제한적입니다.

큐에선 4가지 개념이 가장 핵심입니다.

Enqueue - 큐에 데이터 삽입
Dequeue - 큐에서 데이터 추출
Rear - 큐의 가장 뒤에 위치한 데이터를 가리키는 포인터
Front - 큐의 가장 앞에 위치한 데이터를 가리키는 포인터

일상생활 속 큐가 사용되는 곳도 많이 찾아볼 수 있습니다.

은행 창구, 병원 등 번호표를 사용하는 곳
프린터의 출력 처리
음식점 냉장고 속 재료

순서대로 진행되는 것에 쓰인다고 생각하시면 될 것 같습니다ㅎㅎ

1-2. Deque

덱은 Double-Ended Queue의 줄임말로 큐와 스택을 합친 하이브리드 형태의 자료구조입니다.

데이터를 앞과 뒤 모두에서 삽입, 삭제가 가능한 형태로, 선입선출 / 선입후출 두가지 모두 적용할 수 있습니다.

하지만 여전히 스택과 큐와 마찬가지로 중간 데이터에 대한 임의 접근은 제한적입니다.

(일상생활에서 사용되는 예시가 있다면 댓글로 알려주세요🥺)

2. 장단점

큐와 덱의 장단점에 대해서 알아보겠습니다.

시간복잡도를 중심으로 봐주시면 좋을 것 같습니다!

2-1. Queue

장점

뒤에서 데이터 삽입, 앞에서 데이터 삭제가 빠릅니다.
- Front, Rear 포인터로 바로 접근할 수 있기 때문에 O(1)의 시간 복잡도를 가집니다.

단점

중간 데이터에 대해 임의 접근할 수 없습니다
데이터를 추출하는 곳이 정해져 있습니다.

2-1. Deque

장점

데이터의 삽입, 삭제가 빠릅니다.
- Front, Rear 포인터로 바로 접근할 수 있기 때문에 O(1)의 시간 복잡도를 가집니다.
앞과 뒤 모두에서 데이터의 삽입, 추출이 가능합니다.

단점

중간 데이터에 대해 임의 접근할 수 없습니다. (STL에서는 예외)

3. 구현

자바와 파이썬으로 구현해보도록 하겠습니다.

3-1. Java

Queue

자바에서 Queue를 사용하기 위해선 큐 인터페이스의 구현체인 LinkedList를 활용하여 생성해야합니다.

//큐 객체 생성
Queue q = new LinkedList();
Queue<String> q1 = new LinkedList<>();

자바에서 구현된 큐의 주요 메소드는 크케 6가지가 있습니다.

add(E e)- 큐의 가장 뒤에 데이터를 삽입합니다.
offer(E e) - 큐의 가장 뒤에 데이터를 삽입합니다.
poll() - 큐의 가장 앞의 데이터를 꺼내고 반환합니다.
remove() - 큐의 가장 앞의 데이터를 꺼내고 반환합니다.
peek() - 큐의 가장 앞의 데이터를 꺼내지 않고, 반환합니다.
element() - 큐의 가장 앞의 데이터를 꺼내지 않고, 반환합니다.

읭? 뭔가 똑같은 기능을 하는 메소드가 두개씩 있는 것 같지 않으신가요?

맞습니다. 수행하는 기능은 같지만, 문제가 발생했을 때 처리하는 방식에 차이가 있습니다.

허용하는 용량이 초과되어 값을 추가하지 못하는 경우 add()은 에러를 발생시키지만, offer()는 false를 반환합니다.
큐가 비어있을 때 값을 꺼내는 경우 remove()는 에러를 반환하지만, poll()은 null을 반환합니다.
마찬가지로 element()도 에러를 반환하지만, peek()는 null을 반환합니다.

실제로 사용해보겠습니다.

Queue queue = new LinkedList<>();

// 데이터 삽입
queue.add(1);
queue.offer(2);
        
int first = (int) queue.poll(); // 출력 -> 1
int second = (int) queue.peek(); // 출력 -> 2
int third = (int) queue.element(); // 출력 -> 2

참 쉽죠?

Deque

자바의 Deque는 Queue를 상속받고 있고, 구현체로는 마찬가지로 LinkedList를 사용하고 있습니다.

Deque dq = new LinkedList();
Deque<String> dq2 = new LinkedList<>();

사용하는 메소드는 Queue의 연장으로 앞과 뒤 개념이 추가되었습니다.

add(E e)- 덱의 가장 뒤에 데이터를 삽입합니다.
addFirst(E e)- 덱의 가장 앞에 데이터를 삽입합니다.
addLast(E e)- 덱의 가장 뒤에 데이터를 삽입합니다.
offer(E e) - 덱의 가장 뒤에 데이터를 삽입합니다.
offerFirst(E e) - 덱의 가장 앞에 데이터를 삽입합니다.
offerLast(E e) - 덱의 가장 뒤에 데이터를 삽입합니다.

poll() - 덱의 가장 앞의 데이터를 꺼내고 반환합니다.
pollFisrt() - 덱의 가장 앞의 데이터를 꺼내고 반환합니다.
pollLast() - 덱의 가장 뒤의 데이터를 꺼내고 반환합니다.
remove() - 덱의 가장 앞의 데이터를 꺼내고 반환합니다.
removeFirst() - 덱의 가장 앞의 데이터를 꺼내고 반환합니다.
removeLast() - 덱의 가장 뒤의 데이터를 꺼내고 반환합니다.

peek() - 덱의 가장 앞의 데이터를 꺼내지 않고, 반환합니다.
peekFirst() - 덱의 가장 앞의 데이터를 꺼내지 않고, 반환합니다.
peekLast() - 덱의 가장 뒤의 데이터를 꺼내지 않고, 반환합니다.
getFirst() - 덱의 가장 앞의 데이터를 꺼내지 않고, 반환합니다.
getLast() - 덱의 가장 뒤의 데이터를 꺼내지 않고, 반환합니다.

한 번 사용해볼까요?

Deque dq = new LinkedList();
Deque<String> dq2 = new LinkedList<>();

// 데이터 삽입
dq.add(1); // [1]
dq.addFirst(2); // [1, 2]
dq.offer(3); // [3, 1, 2]
dq.offerFirst(4); // [3, 1, 2, 4]
        
int first = (int) dq.poll(); // 출력 -> 4
int second = (int) dq.pollLast(); // 출력 -> 3
int third = (int) dq.peekLast(); // 출력 -> 1

청기백기 마냥 헷갈리네요,,

3-2. Python

파이썬은 관련 라이브러리를 제공하고 있습니다.

Queue

파이썬은 Queue 모듈을 import 한 후 바로 사용할 수 있습니다.

from queue import Queue
// 큐 선언
q = Queue()

제공하는 메소드의 종류는 아래와 같습니다.

put(x) - 큐의 가장 뒤에 데이터 삽입
get() - 큐의 가장 앞에서 데이터 꺼내고 값 반환
empty() - 큐가 비어있는지 확인

직접 사용해보겠습니다

q = queue.Queue()

#데이터 추가
q.put(1)
q.put(2)
q.put(3)
q.put(4)
q.put(5)

print(q.get()) # 출력 -> 1
print(q[3]) # 임의접근 불가

파이썬에서 큐는 리스트 형태로도 선언하여 간편하게 사용할 수 있습니다. 하지만 성능 측면에서는 좋지 않기 때문에 보통 `Deque`의 사용을 권장하고 있습니다.

참고로 위에서 사용한 Queue 클래스는 내부적으로 locking을 지원하기 때문에 보통 멀티스레딩 환경에서 사용됩니다.

Deque

파이썬에서 Deque도 모듈을 import하여 편리하게 사용할 수 있습니다.

from collections import deque
// 덱 선언
dq = deque()

사용할 수 있는 주요 메소드는 아래와 같습니다.

append() - 덱의 가장 뒤에 데이터 삽입
appendleft() - 덱의 가장 앞에 데이터 삽입
pop() - 덱의 가장 뒤의 데이터 꺼낸 후 반환
popleft() - 덱의 가장 앞의 데이터 꺼낸 후 반환

뭔가 조금 더 직관적이지 않나요?

한 번 사용해보겠습니다.

dq = deque()
# 데이터 삽입
dq.append(1)
dq.append(2)
dq.append(3) # 출력 -> [1, 2, 3]

dq.appendleft(4)
dq.appendleft(5)
dq.appendleft(6) # 출력 -> [6, 5, 4, 1, 2, 3]

first = dq.pop() # 출력 -> 3
second = dq.popleft # 출력 -> 6