Being Programmer

자료구조 with Python : 스택 2개로 큐 구현하기

큐를 구현하는 방법 중 하나는 스택을 두 개 사용하는 것이다. 여기서는 스택 자료구조를 직접 사용하지 않고 파이썬 내장 리스트를 사용하여 스택을 대신한다.

큐의 구조

• enqueue : 뒤 쪽으로 원소를 삽입하는 함수
• dequeue : 가장 앞에 위치한 원소를 제거하면서 반환하는 함수
• is_empty : 큐가 비어있는지 확인하는 함수
• transfer : in_stack의 원소들을 모두 out_stack으로 옮기는 함수

스택 2개를 사용한 큐의 구현

class Queue(object):
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def isEmpty(self):
        return not(bool(self.in_stack) or bool(self.out_stack))

    def transfer(self):
        while self.in_stack:
            self.out_stack.append(self.in_stack.pop())

    def enqueue(self, item):
        return self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            self.transfer()
        if not self.isEmpty():
            return self.out_stack.pop()
        else:
            print("Queue is empty!")

    def __repr__(self):
        tmp = []
        tmp += self.out_stack[::-1]
        tmp += self.in_stack
        if tmp:
            return repr(tmp)
        else:
            return "Queue is empty!"

enqueue를 하게 되면 in_stack 리스트에 데이터를 입력한다. 그러다 dequeue를 실행했을 때 out_stack이 비어있으면 in_stack의 모든 원소들을 pop하여서 가져온다. 이후에 out_stack의 원소들을 pop하게 되면 큐의 동작처럼 FIFO로 데이터가 출력되는 것을 확인할 수 있다.

확인코드

queue = Queue()
for i in range(1, 4):
    queue.enqueue(i)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print("dequeue: {0}".format(queue.dequeue()))
queue.enqueue(4)
queue.enqueue(5)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print(queue)

고찰

가장 중요한 아이디어는 in_stack의 데이터들은 모두 out_stack보다 늦게 들어온 데이터라는 것이다. out_stack에 원소가 있다면 in_stack에서 원소를 가져오지 않고 pop을 해야했다. LIFO를 두 번 사용해서 FIFO로 만드는 게 꽤 흥미로웠다.

자료구조 with Python : Queue(큐)

큐는 스택과 다르게 항목이 들어온 순서대로 접근이 가능하다. 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조다. 큐도 스택처럼 랜덤 액세스가 제한된다.

큐의 구조

• front : 큐의 가장 앞을 가리키는 포인터
• rear : 큐의 가장 뒤를 가리키는 포인터
• enqueue : rear 뒤에 원소를 삽입하는 함수
• dequeue : front 위치의 원소를 제거하면서 반환하는 함수
• is_empty : 큐가 비어있는지 확인하는 함수
• size : 큐의 크기를 확인하는 함수

큐의 구현

class Queue(object):
    def __init__(self):
        self.items = []
        self.front = 0
        self.rear = -1

    def isEmpty(self):
        return self.front > self.rear

    def enqueue(self, item):
        self.items.append(item)
        self.rear += 1

    def dequeue(self):
        if self.isEmpty():
            print("Queue is empty")
        else:
            self.front += 1
            return self.items[self.front - 1]

    def __repr__(self):
        return repr(self.items[self.front:self.rear+1])

items 리스트에 enqueue()함수로 데이터를 넣으면 가장 뒤를 나타내는 rear가 커진다.

dequeue를 하면 front가 가리키는 데이터를 반환하고 front가 1 증가한다.

큐가 비어있는 지 여부는 front > rear로 알 수 있다.

확인코드

queue = Queue()
for i in range(1, 4):
    queue.enqueue(i)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print("dequeue: {0}".format(queue.dequeue()))
queue.enqueue(4)
queue.enqueue(5)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print(queue)

이 방법은 큐의 동작이 어떻게 이뤄지는지 확인하기 위함이고 이렇게 계속 사용하게 되면 dequeue()를 하더라도 데이터가 남아있기 때문에 좋은 방법은 아니라고 생각한다.

쉬운 구현은 list자료형을 이용해서 append와 pop(0)를 사용하는 방법이지만 pop(0) 의 경우 시간복잡도가 O(N)이기 때문에 이 또한 비효율적이다.