[03-13] Queue [1/2] - List를 사용해서 구현하기

1. 개요 & 알고리즘

Queue는 put과 get 동작을 수행하합니다. 자료는 뒤(rear)에 집어 넣고, 앞(front)에서 자료를 얻어내는 FIFO(First Input First Output) 동작을 하는 자료구조입니다.("C로 배우는 알고리즘"^[각주:1]) Python에서는 자체적으로 Queue를 제공^[각주:2]합니다만, 앞선 Stack에 대한 포스팅에서와 마찬가지로 List와 Linked list를 이용해서 Queue를 구현해 보겠습니다.

2. 동작 코드

Python에서 List를 이용해서 Queue를 구현한다면, 다음과 같이도 구현할 수 있어 보입니다.

* get()의 경우, List의 0번째 element를 읽고, del()을 사용해서 0번째 element를 지웁니다^[각주:3]. 이 경우 뒤에 있는 element들이 모두 앞으로 한칸씩 전진합니다.

* put()의 경우, List의 append()를 사용합니다.

* Python은 메모리 제약이 없기 때문에, empty 경우에 대해서만 예외처리하면 됩니다.

하지만, "C로 배우는 알고리즘"에서 구현한대로 List를 이용해서 Circular 동작을 하도록 구현하는 것은 알고리즘을 이해하는데 도움이 될 것으로 생각됩니다.

front와 rear가 같은 경우 empty로 생각하면 되고, front와 rear 사이에는 완충지대를 1개 둡니다. 따라서 front가 rear+1이면 full로 생각합니다.

put()은 아래와 같이 구현합니다.

def put(self, data):
    if (self.rear + 1) % self.max_num_of_list == self.front:
        print("Queue overflow")
        return False
    self.queue[self.rear] = data
    self.rear = (self.rear + 1) % self.max_num_of_list

    return data

get()은 아래와 같이 구현합니다.

def get(self):
    if self.front == self.rear:
        print("Queue underflow")
        return False
    data = self.queue[self.front]
    self.front = (self.front + 1) % self.max_num_of_list

    return data

3. 실행 코드

실행 코드는 아래와 같습니다("C로 배우는 알고리즘" 리스트 3-12 : QUEUE1에 대응) Full인 상황과 empty인 상황도 시험하도록 합니다.

# main() function
if __name__ == "__main__":
    queue = QueueWithArray()
    queue.init_queue()

    print("Put 5, 4, 7, 8, 2, 1")
    queue.put(5)
    queue.put(4)
    queue.put(7)
    queue.put(8)
    queue.put(2)
    queue.put(1)
    queue.print_queue()

    print("Get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

    print("Put 3, 2, 5, 7")
    queue.put(3)
    queue.put(2)
    queue.put(5)
    queue.put(7)
    queue.print_queue()

    print("Now queue is full, put 3")
    queue.put(3)
    queue.print_queue()

    print("Initialize queue")
    queue.clear_queue()
    queue.print_queue()

    print("Now queue is empty, get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

4. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_13.py

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. http://sarangyik.tistory.com/entry/Pythonmodule-queue [본문으로]
3. https://wikidocs.net/14 [본문으로]