Data Structure - Queue

1.. Queue 란?

• "대기, 줄서서 기다리다"의 의미로, 데이터를 순서대로 입력하고 입력된 순서대로 빠져나가는 형태의 자료 구조
• 버퍼, BFS에 사용 (추후 자세히 알아볼 예정)
• 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조
  First In First Out(FIFO), 선입선출 구조
  

2.. Queue의 정의 및 성질

class Queue:
	def __init__(self):
    	self.items = []
        self.front-index = 0
        # 데이터 저장을 위한 리스트 준비
        # 가장 첫번째 index 지정
        
    def enqueue(self, val):
    	self.items.append(val)
        # 데이터 삽입(원소 추가)
        # Time Complexity = O(1)
        
    def dequeue(self):
    	if self.front-index == len(self.items):
        	print("Q is empty")
            return None
        # 지정한 순서의 index와 Queue의 item의 수를 비교하여 Queue가 비어있는 지 확인
        
        else:
        	x = self.items[front-index]
            self.front-index += 1
            return x
        # 데이터 삭제(원소 제거)
        # Time Complexity = O(1)
        
*** 가장 앞쪽(front) or 뒤쪽(rear)에 위치한 원소의 확인도 O(1) ***
*** 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 ***