초보몽키의 개발공부로그

강의노트 20. 자료구조 - queue (큐)

18 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

queue

  • 참고글
  • 참고글-큐와 스택의 실제 사용 예
  • stack과 queue는 search가 없다.
  • FIFO (First Input First Out, 선입선출, 파이포)
  • Rear에서 삽입, Front에서 삭제가 발생
  • 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.(위키피디아)
  • queue overflow : 큐가 꽉 차서 더이상 자료를 넣을 수 없는 경우
  • queue underflow : 큐가 비어 있어 자료를 꺼낼 수 없는 경우
views
views

queue ADT (인터페이스)

  • front(head) : 데이터를 dequeue 할 수 있는 위치
  • rear(tail) : 데이터를 enqueue 할 수 있는 위치
  • 메소드
    • is_empty() -> boolean
    • enqueue -> insert
    • dequeue -> delete
    • peek -> 엿보기 : 맨 앞의 값 반환만 하고 삭제는 안함

queue 구현 예시1 (python list 사용)

class Queue(list):
    # enqueue == > insert 관용적인 이름
    enqueue = list.append
    # dequeue == > delete
    def dequeue(self):
        return self.pop(0)

    def is_empty(self):
        if not self:
            return True
        else:
            return False

    def peek(self):
        return self[0]

if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)

    while not q.is_empty():
        print(q.dequeue(), end= ' ') # 1 2 3 4 5

queue 구현 예시1 (node를 사용한 queue)

  • 면접에서는 node를 활용한 구현 필요
  • head,tail 만 있어도 구현이 된다
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        if not self.head:
            return True

        return False

    def enqueue(self, data):
        new_node = Node(data)

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return None

        ret_data = self.head.data
        self.head = self.head.next
        return ret_data

    def peek(self):
        if self.is_empty():
            return None

        return self.head.data

테스트코드

if __name__ == "__main__":
    q = Queue()

    print(q.is_empty()) # True

    q.enqueue(1)
    print("deleted data : {}".format(q.dequeue())) # deleted data : 1

    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)

    while not q.is_empty():
        print(q.dequeue()) # 2, 3, 4, 5

Related Posts