Queue

공부한 내용을 스스로 보기 쉽게 정리한 글입니다.

Queue의 특징

1. 내가 버스정류장에 서있다고 생각해보면, 버스 전용차선으로 버스가 줄지어 들어온다. 아무리 뒷차가 손님을 다 태웠다고해서, 앞에 버스가 아직 손님을 태우고 있으면 뒷 버스는 출발 하지 못한다.
   
   이것이 바로 QUEUE
2. FIFO : First In First Out == 선입선출 or 후입후출
3. front와 rear 라는 index가 각각 구조의 맨 앞과 뒤를 가리키고 있다. Data는 rear로 들어가고, front 에서 나온다.

ADT

1. empty() 라는 메소드로 Queue 에 data가 있는지 없는지 확인하게 한다. empty 이면 True, not empty 이면, False 를 return 한다.
   
   Queue.empty() returns Boolean

2. enaueue(data) 메소드로 Queue의 rear 가 가리키고 있는 data 뒤에 data를 넣는다.
   
   Queue.enqueue (data) returns None

3. dequeue() 메소드로 Queue의 front가 가리키고 있는 data를 반환하면서 삭제 된다.
   
   Queue.dequeue() returns data

4. peek() 메소드로 Queue의 front가 가리키고 있는 data를 반환한다. peek은 어디까지나 확인하는 메소드 이므로, data가 삭제되지 않는다.
   
   Queue.peek() returns data

구현 1 : by python list

• Queue 구조를 Python에 내장 되어 있는 list를 container 로 구현한다.

class Queue:
  def __init__(self):
    self.container=list()

  def empty(self):
    # ADT 를 따라서, 비어 있으면 return True 비어있지 않으면 return False
    if not self.container:
      return True
    return False

  def enqueue(self, data):
    # list 를 활용했으므로, list.append(data)를 활용할 수 있다.
    self.container.append(data)

  def dequeue(self):
    # pop 역시 list.pop()을 활용할 수 있다.
    return self.container.pop(0)

  def peek(self):
    # peek은 단지 front 에 어떤 데이터가 있는지 확인 하는 것 뿐이므로, 현재 리스트의 가장 앞 부분에 있는 data 를 확인하면 된다.
    return self.container[0]

구현 2 :