TIL - 자료구조 정리 노트 시리즈 (2. 큐)

'자료구조 정리 노트' 시리즈는 자료구조를 공부하면서 그려본 그림들과 함께 간략하게 배운 내용을 공유해 보는 시리즈 입니다.

2. Queue

definition of queue

큐는 나중에 집어넣은 데이터가 먼저 나오는 스택의 반대 개념으로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다.

real life applications of queue

• 톨게이트에 늘어선 차들 : 먼저 게이트에 도착한 차부터 순차적으로 빠져나감
• 컴퓨터에서 프린트 출력처리를 할 때 요청 순으로 처리함

queue as an ADT(Abstract Data Type)

Primery Stack Operations

• enQueue(data) : 큐의 tail 또는 rear에 데이터 삽입
• deQueue() : 큐의 front 또는 head의 데이터를 삭제하고 반환

Secondary Stack Operations

• front() or peek() : 큐의 front 또는 head의 데이터를 삭제 없이 반환
• isEmpty() : 큐가 비어있는지 확인
• isFull() : limit이 있는 큐라면, 큐가 가득 찼는지를 확인

linear queue vs circular queue

선형

막대 모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.

환형 큐

선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다. 원형 큐라고도 한다.

참고 자료

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) https://www.youtube.com/watch?v=XuCbpw6Bj1U