자료구조 -큐(Queue)

 

1. 큐(Queue)란?

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(선입선출)식 선형 자료구조이다.

---

2. 큐의 동작 방식

 

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조이다.
데이터는 뒤(rear)에서 삽입되고, 앞(front)에서 삭제된다.

1️⃣ Enqueue(데이터 삽입)

큐의 맨 뒤쪽인 rear위치에 데이터를 삽입한다.
새로운 데이터가 들어오면 기존 데이터들의 가장 뒤에 줄을 선다.
위의 예시처럼 10,20,30 순서대로 넣으면 10부터 차곡차곡 쌓이고, rear은 가장 마지막에 들어온 30을 가리키게 된다.

---

2️⃣ Dequeue (데이터 삭제)

큐의 맨 앞쪽인 front위치의 데이터를 꺼낸다. 데이터를 꺼낼 때는 가장 먼저 들어와서 맨 앞에 있던 데이터부터 빠져나간다. 데이터가 하나 빠져나가면 그 다음 차례인 데이터를 가리키기 위해 front 포인터가 한 칸 뒤로 이동한다.
예를 들어 10,20,30 이 있는 큐에서 Dequeue를 실행하면 가장 먼저 들어왔던 10이 제일 먼저 빠져나가고, 이제 맨 앞이 된 20을 front가 가리키게 된다.

---

3. 큐의 장,단점

3.1 큐의 장점

1️⃣ 공평하게 작업을 처리할 수 있다

큐는 FIFO(First In First Out, 선입선출) 구조로 먼저 들어온 데이터가 먼저 나가는 방식이다.
그래서 여러 작업이나 요청이 한꺼번에 들어오는 상황에서 순서를 꼬이지 않게 처리하기 좋다.

---

2️⃣ 처리 속도가 다른 시스템 사이에서 완충 역할을 한다

데이터를 보내는 쪽과 받는 쪽의 처리 속도가 다를 때도 큐가 많이 사용된다.
예를 들어 데이터를 보내는 속도는 빠른데 받는 쪽이 느리다면, 중간에 큐가 데이터를 버퍼(Buffer) 역할을 해준다.
이로 인해, 데이터가 한꺼번에 몰려도 유실되지 않고, 처리 가능한 속도에 맞춰 순서대로 가져갈 수 있다.

---

3.2 큐의 단점

1️⃣ 특정 데이터 접근이 어렵다

큐는 스택과 마찬가지로 인덱스를 이용해 원하는 데이터에 접근하는 랜덤 접근이 불가능하다.

그래서 중간에 있는 데이터를 바로 꺼내거나 특정 위치에 삽입하는 작업은 비효율적이다.
특정 데이터를 찾으려면 처음부터 끝까지 하나씩 확인해야 한다.

---

2️⃣ 선형 큐는 메모리 낭비 문제가 생길 수 있다

배열 기반의 선형 큐(Linear Queue) 에서는 앞쪽 데이터가 삭제되어 빈 공간이 생기더라도, 뒤쪽으로만 데이터를 추가한다.
그러다 보면 실제로는 앞쪽에 빈 공간이 남아 있는데도 배열 끝에 도달해서 더 이상 데이터를 넣지 못하는 상황이 발생할 수 있다.
이런 현상을 ‘가짜 포화(False Overflow)’ 라고 한다.
다만 이 문제는 양 끝을 연결한 원형 큐(Circular Queue) 를 사용하면 해결할 수 있다.

---

4. 큐의 실제 활용 사례

 

4.1 콘서트 티켓팅 / 수강신청 대기열

 

서버에 먼저 요청을 보낸 사람부터 대기 번호를 받고 순서대로 입장하는 시스템 역시 큐의 대표적인 예시이다.

---

4.2 운영체제의 작업 스케줄링

운영체제(OS)는 실행해야 할 여러 프로그램을 큐에 저장해 두고 순서대로 CPU 작업을 할당한다.
이를 통해 여러 프로그램이 동시에 실행되는 것처럼 보이게 만든다.

---

5. 구현

class Queue : 

# 생성자
  def __init__(self):
    self.items=[]

# ✅ enqueue : 큐의 맨 뒤쪽에 새로운 데이터를 줄 세운다

  def enqueue(self,data):
    self.items.append(data)

# ✅ dequeue : 큐의 맨 앞쪽에 있는 데이터를 꺼낸다 , 꺼낸 데이터는 삭제한다
  def dequeue(self):
    if self.items :
      result=self.items.pop(0)
      return result

    else :
      print("큐가 비어있습니다")

# ✅ display() : 현재 큐의 상태를 보여준다

  def display(self):
    print("==== 현재 Queue의 상태 =====")
    if self.items :
      for item in self.items:
        print(item,end=' ')
      print()
      print("============================")
    else: print('큐가 비어있습니다')

queue=Queue()

queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.enqueue(40)
queue.enqueue(50)
queue.display()

print(f'dequeue()실행:',queue.dequeue())

queue.display()

실행 결과

---

6. 큐(Queue)는 왜 선입선출(FIFO) 구조를 사용하는가?

큐(Queue)는 먼저 들어온 데이터가 먼저 처리되는 구조이다.
이를 선입선출(FIFO, First In First Out)  구조라고 한다.
예를 들어 큐에 10 → 20 → 30 순서로 데이터가 들어왔다면, 데이터를 꺼낼 때는 10 → 20 → 30 순서대로 삭제된다.
이런 구조를 사용하는 이유는 작업의 순서를 공정하게 처리하기 위해서이다.

---

7. 배열, 스택 ,큐의 차이점 정리

 

지금까지 자료구조 중 배열,스택,큐에 대해 알아보았다. 

이들의 차이점에 대해서 한 번 정리해보자.

 

구분	배열(Array)	스택(Stack)	큐(Queue)
동작 방식	순서대로 데이터 저장	LIFO(후입 선출) 한쪽 끝에서만 삽입/삭제	FIFO(선입선출) 한쪽에서 삽입/ 반대쪽에서 삭제
데이터 접근 방식	인덱스로 바로 접근 가능	가장 마지막 데이터부터 접근	가장 먼저 들어온 데이터부터 접근
삽입 위치	원하는 위치	Top에서만 가능	rear에 삽입
삭제 위치	원하는 위치	Top에서만 가능	front에서 삭제