[자료구조] 큐(Queue) 란? 한번에 쉽고 간단하게 이해하기!

큐(Queue) 란 무엇일까요 ?

 

큐(Queue)는 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트이다.

 

 

 

큐(Queue)의 특징 ?

 

First in First Out (FIFO) 선입선출이라고 생각하면 쉽습니다. 먼저들어온것이 먼저 나가는 형식입니다.

 

즉, 제일 처음에 들어온 데이터가 먼저 삭제가 된다.

 

 

 

실생활에서 쓰이는 큐(Queue)의 3가지 예시들

 

1. 티켓 판매부스에서 줄을서서 기다리는 사람들

한줄로(선형으로) 서있는 구조

 

 

2. 한줄로 나란히 가야만하는 차들

 

 

3. 컴퓨터 운영체제의 테스크 스케줄링

 

 

큐(Queue)의 주요 동작들

 

• enQueue() : 큐에 데이터를 넣는다.
• deQueue() : 큐에서 데이터를 빼낸다.
• isEmpty() : 큐가 비어있는지 확인한다.
• isFull() : 큐가 꽉 차 있는지 확인한다.
• peek() : 앞에있는 원소를 삭제하지 않고 반환한다.

 

큐(Queue)의 문제점

 

큐(Queue)를 구현하고 사용할때 큐에서 데이터를 빼내는 deQueue()함수를 쓰게되면 맨 앞에있던 값이 빠져나가게 되는데 이때 front가 한칸씩 뒤로 밀려나게 되면서 큐의 가용범위가 줄어들면서, 큐의 재사용 또한 불가능하게 됩니다.

 

만약에, 억지로 큐의 재사용을 하기위해서 front를 출력하고 front뒤의 인덱스를 하나씩 앞당긴다고 하더라도 불필요한 연산이 너무 많아집니다. 

 

 

 

 

큐(Queue)의 다른 형식

 

원형 큐 (Circle Queue) - 

위와 같은 큐의 문제점을 보완하기 위해서 "원형 큐(Circle Queue)"를 사용합니다

 

우선순위 큐 (Priority Queue) - 

우선순위를 이용하여 우선순위가 높은 순서대로 나가게 된다.

쉽게 말해, 병원에서 기존 환자들을 진료보다가 응급환자가 오게되면 먼저 진료하게된다고 이해하면 된다.

 

 

Reference 

아래 사이트에서 queue를 클릭해보시면서 enqueue(큐에 데이터 추가) / dequeue (큐에서 데이터를 꺼내기)를 쉽게 이해할수있는 사이트입니다! 꼭 참고해보세요.

 

https://visualgo.net/en/list

VisuAlgo - Linked List (Single, Doubly), Stack, Queue, Deque

 

www.studytonight.com/code/python/ds/circular-queue-in-python.php

Implementing Circular Queue in Python | Studytonight

zzsza.github.io/development/2018/07/29/cpu-scheduling-and-process/

CPU Scheduling, Process 이해하기