• 큐란?

  큐는 데이터의 삽입이 한쪽 끝(뒤, rear)에서 이루어지고 삭제는 다른 쪽 끝(앞, front)에서 이루어지는 정렬된 리스트입니다.

  가장 처음 삽입된 항목이 맨 먼저 삭제됩니다. (First In First Out, FIFO)

  

  • EnQueue : 항목을 큐에 삽입
  • DeQueue : 항목을 큐로부터 제거
  • Underfolw : 비어있는 큐로부터 DeQueue하려고 하는것
  • Overflow : 가득 찬 큐에 항목을 EnQueue하려고 하는것

• 큐 ADT

  • EnQueue() : 데이터를 큐에 넣는 것
  • DeQueue() : 큐의 제일 마지막에 추가된 데이터를 삭제하고 리턴
  • Front() : 큐의 가장 앞에 있는데이터를 삭제하지 않고 리턴
  • Is_Empty() : 스택에 항목이 저장되어 있는지 아닌지를 확인

• 큐의 구현

# list 이용
class Queue:
    def __init__(self):
        self.queue = []
    
    def enqueue(self, data):
        self.queue.append(data)
        
    def dequeue(self):
        if self.is_empty():
            return -1
        return self.queue.pop(0)
            
    def front(self):
				if self.is_empty():
				            return -1
        return self.queue[0]
        
    def is_empty(self):
        if len(self.queue) == 0:
            return True
        return False

# linked list 이용
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, node):
        if self.head == None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next

    def dequeue(self):
        if self.is_empty():
            return -1
        data = self.head.data
        self.head = self.head.next
        return data

    def front(self):
        if self.is_empty():
            return -1
        return self.head.data

    def is_empty(self):
        if self.head == None:
            return True
        return False

BEFORE

8강 스택, 스택의 구현

NEXT

10강 트리