큐 (Queue)

• 먼저 들어온 데이터가 먼저 나가는 구조로, 선입선출(FIFO) 형식으로 입출력이 일어나는 자료구조이다.
• 스택과 다르게 큐는 삽입과 삭제가 다른 쪽에서 일어난다.
• 삽입은 enqueue 연산을 통해 큐의 맨 뒤(rear)에 새로운 요소를 추가한다. 삭제는 dequeue 연산을 통해 큐의 맨 앞에 있는 요소를 꺼내 외부로 반환한다.
• 장점 : 데이터의 삽입/삭제가 빠르다
• 단점 : queue 중간에 위치한 데이터의 접근이 어렵다
• 데이터를 입력된 순서대로 처리하거나 BFS 구현할 때 사용한다.

덱 (Deque)

• 덱은 double-ended queue의 줄임말로 큐의 맨 앞과 맨 뒤 모두 삽입과 삭제가 가능한 큐를 의미한다.
• 장점 : 데이터의 삽입과 삭제가 빠르고 크기가 가변적이다. 앞, 뒤에서 데이터를 삽입/삭제 할 수 있다. index로 임의 원소 접근이 가능하다. 새로운 원소 삽입 시에, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
• 단점 : deque의 중간에서의 삽입과 삭제가 어렵고 구현이 어렵다.
• 앞과 뒤에서 삽입, 삭제가 잘 일어나느 경우, 데이터의 개수가 가변적일 경우, 데이터 검색을 거의 하지않을 경우(랜덤 요소 접근)에 사용한다.

---

참고 사이트

C언어로 쉽게 풀어쓴 자료구조
https://velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue