[Python / 자료구조] Python으로 Queue 구현하기

---

Python으로 큐(Queue) 구현하기

Python으로 Stack 구현하기의 다음 시리즈이다. 이번엔 Queue를 다양한 방법으로 구현해보자.

2021.12.18 - [Development/Python] - [Python / 자료구조] Python으로 Stack 구현하기

[Python / 자료구조] Python으로 Stack 구현하기

 

 

큐(Queue)의 기본 구조

---

출처 : 위키피디아

 

• 스택과 달리 FIFO(First In First Out)의 구조를 가진다.
  
  
• 한국말로 번역하면 "대기열"로, 먼저 줄 선 사람이 먼저 빠져나가는 구조이다. 
  
  
• 롤할 때 "큐"돌린다의 Queue가 이거다. 은근히 모르시는 분이 많았다.
  
  
• 운영체제의 스케줄러에서도 프로세스를 처리할 때 Queue를 쓴다.

 

큐가 가져야 할 Method 목록

---

• push(x) : 큐의 맨 뒤에 x라는 값을 집어 넣는다.
  
  
• pop() : 큐의 맨 앞 부분(먼저 들어온 원소)를 꺼내고 반환한다.
  
  
• size() : 큐의 길이를 반환한다.
  
  
• empty() : 큐가 비어있는지에 대한 유무를 반환한다.
  
  
• front() : 큐의 맨 앞 부분 원소를 반환한다.
  
  
• back() : 큐의 맨 뒷 부분 원소를 반환한다.

 

 

구현

---

 

from collections import deque

 

사실 Python에서 가장 편하게 Queue를 쓰는 방법은 그냥 deque을 가져다 쓰는 거다.

내부적으로 이중 링크드리스트를 쓰고 있기 때문에, enqueue, dequeue를 앞에서 할 수도 있고, 뒤에서 할 수도 있어 알고리즘 문제 풀이에 자주 쓰인다.

deque의 코드가 궁금하신 분들은 https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c#l21를통해확인할 수 있다. (C로 구현되어있음)

원소 삽입, 삭제의 경우 list에선 빈공간 만큼 앞으로 원소를 당겨주는 과정을 수행하지만, deque은 그냥 링크드리스트의 포인터 부분만 바꾸면 되기 때문에 오버헤드가 적어, O(1)의 시간 복잡도를 가진다.

 

반면, 인덱스를 활용한 탐색의 경우 Linked List를 타고타고 들어가야 하다보니, 그냥 list방식의 시간복잡도 O(1)보다 느린 O(N)의 시간 복잡도를 지닌다.

본 포스팅에서는 List로 구현하기, 면접 단골 출제 문제인 스택 2개로 Queue 구현하기 두 가지 방식을 다룬다.

 

 

List로 구현하기

---

'''
    push(x) - input x to queue
    pop() - delete last element of queue and return it
    size() - return length of queue
    empty() - return boolean that checks whether queue has an element
    front() - return first element in queue
    back() - return last element in queue
'''
class HyunQueue:
    def __init__(self):
        self.que = []

    def push(self, x):
        self.que.append(x)

    def pop(self):
        return self.que.pop(0) if self.que else -1

    def size(self):
        return len(self.que)

    def empty(self):
        return not self.que

    def front(self):
        return self.que[0] if self.que else -1

    def back(self):
        return self.que[-1] if self.que else -1

if __name__ == "__main__":
    q = HyunQueue()
    q.push(1)
    q.push(2)
    print(q.front())
    print(q.back())
    print(q.size())
    print(q.empty())
    print(q.pop())
    print(q.pop())
    print(q.pop())
    print(q.size())
    print(q.empty())
    q.push(3)
    print(q.empty())
    print(q.front())
    print(q.back())

 

 

Stack 2개로 구현하기

---

 

파이썬에서는 사실 Stack 구조를 안쓰고 List를 쓰는데다가, List 내부적으로 index 기반 pop이 가능하다.

즉, stack.pop()이 아니라 stack.pop(0)을 하면 그 자체가 Queue의 dequeue와 같이 동작하는 것이다.

 

본 방식은 C++, Java에서 자주 나오는 빈출 유형이라 Python으로 푸는게 어불성설이긴 하지만, 그래도 List에 인덱스 기반 pop이 없다고 가정하고 풀어보면 아래와 같은 구현이 가능하다.

 

Stack1에 데이터를 순차적으로 넣고, dequeue할 때 Stack1의 원소를 pop한뒤 Stack2에 담은 후, Stack2에서 pop을 진행하면 FIFO 구조를 가지게끔 할 수 있다.

 

이 때, 중요한 것은, dequeue 요청이 왔을 때,  Stack2가 비어있을 경우에만 Stack1의 원소들을 모두 Stack2에 넣는 것이다.

그렇지 않으면 순서가 꼬이게 된다. 

 

Stack1 = [1, 2, 3, 4]

Stack2 = [ ] 
위 상황에서 pop 요청이 오면, Stack1의 데이터를 Stack 2로 하나씩 pop해서 넣는다. Stack의 원소는 후입선출이므로 4부터 빠져서 Stack2에 들어가게 된다.

Stack1 = [ ] 

Stack2 = [4, 3, 2, 1] -> pop() -> Stack2 = [4, 3, 2]

 

예를 들어 위와 같은 상황에서, Stack2가 차있는 상태로 Stack1에 새로운 데이터 5, 6이 들어왔고 이를 옮긴다고 가정해보자.
Stack1 = [5, 6]

Stack2 = [4, 3, 2]

Stack1의 원소를 빼서 Stack2에 넣는 과정에서, 6, 5가 Stack2에 뒤에 추가된다.
즉, Stack2 = [4, 3, 2, 6, 5]가 된다. 순서가 완전히 깨져버렸다.
그래서, Stack2가 비어 있지 않으면 일단은 원소를 Stack1에 쌓아두는 방식을 사용한다.

 

말보다 코드로 보면 오히려 바로 이해가 갈 것이다. 아래 구현을 보자.

 

'''
    push(x) - input x to queue(enqueue)
    pop() - delete last element of queue and return it(dequeue)
    size() - return length of queue
    empty() - return boolean that checks whether queue has an element
    front() - return first element in queue
    back() - return last element in queue
'''
class HyunQueue():
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self,x):
        self.stack1.append(x)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop() if self.stack2 else -1

    def size(self):
        return len(self.stack1) + len(self.stack2)

    def empty(self):
        return not self.stack1 and not self.stack2

    def front(self):
        if self.stack2:
            return self.stack2[-1]
        elif self.stack1:
            return self.stack1[0]
        else:
            return -1

    def back(self):
        if self.stack1:
            return self.stack1[-1]
        elif self.stack2:
            return self.stack2[0]
        else:
            return -1

if __name__ == "__main__":
    q = HyunQueue()
    q.push(1)
    q.push(2)
    print(q.front())
    print(q.back())
    print(q.size())
    print(q.empty())
    print(q.pop())
    print(q.pop())
    print(q.pop())
    print(q.size())
    print(q.empty())
    q.push(3)
    print(q.empty())
    print(q.front())
    print(q.back())