관리 메뉴

솜씨좋은장씨

파이썬으로 구현하는 자료구조! - 큐 ( Queue ) 본문

Programming/Data Structure | Algorithm

파이썬으로 구현하는 자료구조! - 큐 ( Queue )

솜씨좋은장씨 2021. 5. 7. 00:59
728x90
반응형

1. 큐(Queue)가 뭐야?

큐는 양쪽이 뚤려있는 기다란 통에서 한쪽은 데이터를 삽입하고 한쪽은 데이터를 삭제하는 자료구조 입니다.

스택이 후입선출 ( LIFO - Last In, First Out ) 구조였다면

큐는 먼저 들어간 데이터가 먼저 나오는 선입선출 ( FIFO - First In, First Out ) 구조입니다.

위의 그림과 같이 데이터의 앞부분Front 뒷부분Rear라고 부릅니다.

데이터는 Rear로 들어와서 Front로 나갑니다.

 

큐와 같은 구조는 우리의 일상속에서 많이 볼 수 있습니다.

 

은행에 가면 번호표를 뽑은 순서대로 창구에서 은행 업무를 보는 것과

프린터의 대기열을 예로 들면 먼저 프린트를 요청한 사람부터 먼저 프린트를 하는 것을 예로 들 수 있습니다.

2. 주요 Method

2-1. enqueue, equeue

데이터를 삽입하는 과정을 enqueue

가장 먼저 삽입한 데이터를 빼서 사용하는 과정을 dequeue라고 합니다.

dequeue를 하는 경우에 큐가 비어있는지 먼저 확인한 후에 실행합니다.

2-2. peek

peek은 Front 위치에 있는 데이터를 꺼내지 않고 어떤 값인지 return하는 method입니다.

2-3. isEmpty

isEmpty는 현재 큐가 비어있는지 확인하는 method입니다.

3. 코드로 구현하기

3-1. Python List로 구현하기

class Queue():
    def __init__(self):
        self.queue = []
        
    def enqueue(self, data):
        self.queue.append(data)
        
    def dequeue(self):
        dequeue_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            dequeue_object = self.queue[0]
            self.queue = self.queue[1:]
            
        return dequeue_object
            
    def peek(self):
        peek_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            peek_object = self.queue[0]
            
        return peek_object
            
    def isEmpty(self):
        is_empty = False
        if len(self.queue) == 0:
            is_empty = True
        return is_empty

enqueuelist의 append를 활용하여 구현하였습니다.

 

dequeuequeue가 비어있는지 isEmpty를 활용하여 확인하고

비어있다"Queue is Empty"를 출력하고 None을 return

비어있지않다 list의 가장 첫번째값을 가져온 뒤 [1:] 을 활용하여 첫번째 값 이외의 값들만 남겨둡니다.

 

peekqueue가 비어있는지 isEmpty를 활용하여 확인하고

비어있다 "Queue is Empty"를 출력하고 None을 return

비어있지않다list의 가장 첫번째값을 가져와서 return합니다.

 

isEmptyqueue에 값이 하나도 없을 경우 True, 값이 있을 경우 False를 return 하도록 하였습니다.

3-2. Python Singly Linked List로 구현하기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue():
    def __init__(self):
        self.front = None
        self.rear = None
        
    def enqueue(self, data):
        new_node = Node(data)
        
        if self.front is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = self.rear.next
        
    def dequeue(self):
        dequeue_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            dequeue_object = self.front.data
            self.front = self.front.next
            
        if self.front is None:
            self.rear = None
        return dequeue_object
    
    def peek(self):
        front_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            front_object = self.front.data            
        return front_object
    
    def isEmpty(self):
        is_empty = False
        if self.front is None:
            is_empty = True
        return is_empty

먼저 LinkedList를 만들기 위해 필요한 Node를 정의해줍니다.

각각의 노드는 data와 next로 이루어져 있습니다.

 

LinkedList로 만드는 Queue는 front와 rear를 먼저 None으로 init 해줍니다.

 

enqueue는 먼저 새로운 데이터를 담은 노드를 먼저 생성합니다.

만약 front가 None이면 front와 rear에 이 노드를 연결합니다.

그렇지 않으면 rear의 next에 새로운 노드를 넣어주고 이를 다시 rear에 넣어줍니다.

 

dequeue는 먼저 isEmpty를 활용하여 Queue가 비어있는지를 먼저 확인하고

비어있다 "Queue is Empty"를 출력하고 None을 return

비어있지 않다front의 노드에서 데이터를 꺼내온 뒤 front에 front의 next 노드를 넣어주고 아까 꺼낸 데이터를 return 합니다.

 

peek은 먼저 isEmpty를 활용하여 Queue가 비어있는지를 먼저 확인하고

비어있다"Queue is Empty"를 출력하고 None을 return

비어있지 않다front의 노드에서 데이터를 꺼내와 return 합니다.

 

isEmptyfront가 None일 경우 TrueNone이 아닐 경우 False를 return 합니다.

 

4. 관련 문제 풀어보기

Programmers - 코딩테스트 연습 > 스택/큐

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

BaekJoon - 단계별로 풀어보기 > 큐, 덱

 

큐, 덱 단계

덱의 개념을 익히고 실습하는 문제. (입력 크기가 너무 작아서 비효율적인 구현으로도 통과가 되지만, 가급적이면 연산 당 시간 복잡도가 O(1)이도록 구현해 주세요.)

www.acmicpc.net

HackerRank - Interview Praperation Kit > Stacks and Queues

 

Solve Stacks and Queues Interview Questions | HackerRank

Stacks and Queues Prepare for you upcoming programming interview with HackerRank's Ultimate Interview Preparation Kit

www.hackerrank.com

LeetCode - Problems > Tags > Queue

 

Problems - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

5. 구현 코드 GitHub

 

SOMJANG/DataStructure-Algorithm-Practice

자료구조 / 알고리즘 스터디. Contribute to SOMJANG/DataStructure-Algorithm-Practice development by creating an account on GitHub.

github.com

 

다른 자료구조 알아보기

 

파이썬으로 구현하는 자료구조! - 스택 ( Stack )

오늘부터 시간이 날때마다 초심으로 돌아가 자료구조와 알고리즘에 대해서 하나씩 차근차근 공부해보려 합니다. 그 시작으로 이번 글에서는 파이썬을 활용하여 자료구조 중에 하나인 스택에

somjang.tistory.com

 

 

파이썬으로 구현하는 자료구조! - 큐 ( Queue )

1. 큐(Queue)가 뭐야? 큐는 양쪽이 뚤려있는 기다란 통에서 한쪽은 데이터를 삽입하고 한쪽은 데이터를 삭제하는 자료구조 입니다. 스택이 후입선출 ( LIFO - Last In, First Out ) 구조였다면 큐는 먼저

somjang.tistory.com

Comments