Queue

FIFO?

큐를 설명할 때 가장 많이 쓰는 말 중 하나는 'FIFO'다. FIFO란, First In First Out이란 뜻이다.

영어 표기법대로, '먼저 들어간 놈이 먼저 나온다'는 뜻이다. 즉 가장 먼저 입력된 원소가 가장 먼저 출력된다는 것을 의미한다.

 

큐의 필수요소들

큐는 자료 구조이다. 따라서 자료들을 넣고 뺄 수 있어야 하며, 큐의 상태도 조사할 수 있어야 한다.

 

• Enqueue e: 큐에 원소 e를 넣는다.
• Dequeue: 현재 큐의 가장 앞에 있는 원소를 빼서 return한다. 만약 큐가 비었다면, 오류가 발생한다.
• First: 현재 큐의 가장 앞의 원소가 뭔지 알려주기만 한다. 빼지 않는다.
• Empty: 큐에 원소가 하나도 없으면 True, 하나라도 있으면 False를 return한다.
• Length: 큐의 길이를 확인한다.

실제 큐의 예시

빈 큐 Q를 하나 만들자...

명령어	return	큐의 상태
Enqueue a		a
Enqueue b		a, b
Dequeue	a	b
Enqueue c		b, c
Enqueue d		b, c, d
Length	3	b, c, d
Empty	False	b, c, d
Dequeue	b	c, d
Dequeue	c	d
Dequeue	d
Empty	True
Dequeue	Error

큐의 구현

큐는 배열을 통해 구현할 수 있다.

class Queue:
  def __init__(self):
    self.q=[]
  def length(self):
    return len(self.q)
  def empty(self):
    return not self.length()
  def Enqueue(self, e):
    self.q.append(e)
  def Dequeue(self):
    if self.empty():
      raise Empty()
    else:
      x=self.q[0]
      self.q=self.q[1:]
      return x
  def First(self):
    if self.empty():
      raise Empty()
    else:
      return self.q[0]