[자료구조] Queue & Stack 2

Q. Queue 두 개를 이용하여 Stack을 구현해 보세요

편의상 push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2라고 칭하겠습니다. 두 개의 queue로 stack을 구현하는 방법은 다음과 같습니다.
1. push() :: q1으로 enqueue()를 하여 데이터를 저장합니다.
2. pop() ::
a. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()합니다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨집니다.
b. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환합니다.(LIFO)
c. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap합니다.

import queue

class Stack(object):
    def __init__(self):
        self.q1 = queue.Queue()
        self.q2 = queue.Queue()

    def push(self, element):
        self.q1.put(element)

    def pop(self):
        while self.q1.qsize() > 1:
            self.q2.put(self.q1.get())

        temp = self.q1
        self.q1 = self.q2
        self.q2 = temp

        return self.q2.get()

Q. 시간복잡도는 어떻게 되는지 설명해 주세요.

push() : q1.enqueue()를 한번만 하면 되기 때문에 $O(1)$의 시간복잡도를 갖습니다.
pop() : q1에 저장되어 있는 n개의 원소중에 n-1개를 q2로 옮겨야 하므로 $O(n)$이 됩니다.

---

---

Q. Stack 두 개를 이용하여 Queue를 구현해 보세요

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있습니다.

편의상 enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 칭하겠습니다. 두 개의 stack으로 queue를 구현하는 방법은 다음과 같습니다.
1. enqueue() :: instack에 push()를 하여 데이터를 저장합니다.
2. dequeue() ::
a. 만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 옮겨 넣습니다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 됩니다.
b. outstack.pop()을 하면 가장 먼저 왔던 데이터가 가정 먼저 추출됩니다.(FIFO)

class Queue(object):
    def __init__(self):
        self.instack=[]
        self.outstack=[]

    def enqueue(self,element):
        self.instack.append(element)

    def dequeue(self):
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

Q. 시간복잡도는 어떻게 되는지 설명해 주세요.

enqueue() : instack.push()를 한번만 하면 되기 때문에 시간복잡도 O(1)입니다.
dequeue() : 두 가지 경우를 따져봐야 합니다. worst case는 outstack이 비어있는 경우입니다. 이 때는 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 해줘야 합니다. 따라서 총 2n 번의 operation이 실행되어야 하므로 O(n)의 시간복잡도를 갖습니다.
하지만 outstack이 비어있지 않는 경우에는 outstack.pop()만 해주면 됩니다. 이는 O(1)의 시간복잡도를 갖습니다. 이를 종합했을 때, amortized O(1)의 시간복잡도를 갖는다고 할 수 있습니다.
enqueue() - O(1)
dequeue() - O(1)