[자료구조] Queue

※ 2021년 12월 31일에 작성된 글입니다.

🚥 Queue

먼저 들어온 데이터가 먼저 나가는 자료구조

• FIFO(First-In First-Out, 선입선출)

Queue의 구조

0	1	2	3	4	5	6	7	8	9
	A	B	C
front			rear
* front
첫번째 요소 하나 앞의 인덱스
* rear
마지막 요소의 인덱스

Queue의 연산

• add
  = enQueue
  큐의 뒤에 요소를 추가 한다.
• remove
  = deQueue
  큐의 앞에 있는 요소를 반환한 다음 삭제한다.
• peek
• isEmpty

Queue의 용도

• 버퍼
• 시뮬레이션
• BFS

LinearQueue

배열을 선형으로 사용하여 큐를 구현한다.

0	1	2	3	4	5	6	7	8	9
	A	B	C
⬇

0	1	2	3	4	5	6	7	8	9
A	B	C
* 삽입/삭제를 위해서 요소들을 계속 이동시켜야 한다.

CircularQueue

배열을 원형으로 사용하여 큐를 구현한다.

0	1	2	3	4	5	6	7	8	9
B	C								A
	rear								front

LinkedListQueue

LinkedList로 구현된 큐
A(front) → B → C(rear)

• front 포인터는 삭제, rear 포인터는 삽입과 관련된다.
• 큐가 비어 있으면 front와 rear는 NULL

Deque

= Double-ended queue

큐의 앞단과 뒷단에서 모두 삽입/삭제가 가능한 큐

A(head) ↔ B ↔ C(tail)

• 양쪽에서 삽입/삭제가 가능하여야 하므로 일반적으로 이중연결 리스트를 사용한다.

Queue using two stacks

2개의 스택을 이용하여 큐를 구현할 수 있다.

inbox	outbox
B	A
A	B
1. inbox에 데이터를 삽입한다.
A, B
2. inbox에 있는 데이터를 꺼내 outbox에 삽입한다.
B, A
3. outbox에 있는 데이터를 꺼낸다.
A, B