Queue 두 개를 이용하여 Stack을 구현 & Stack 두 개를 이용하여 Queue를 구현

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

💡 큐 한 개는 메인 큐, 다른 큐는 임시 큐 용도로 둔다.

1. 메인 큐에 값을 넣는다.(put) ex) 1→ 2→ 3 → 4
2. 메인 큐에 1개의 원소가 남을 때까지 get 한 값을 임시 큐에 put 한다.
3. 마지막 남은 원소는 result 변수에 저장한다.
4. 임시 큐에 있는 원소들을 메인 큐로 모두 이동시킨다. (get → put)
5. result 값을 리턴한다.

 

1-1. 순서 설명 

1. 메인큐에 값을 넣는다.(put) ex) 1→ 2→ 3 → 4

   

2. 메인 큐에 1개의 원소가 남을 때까지 get 한 값을 임시 큐에 put 한다.

   

3. 마지막 남은 원소는 result 변수에 저장한다.

   

4. 임시 큐에 있는 원소들을 메인 큐로 모두 이동시킨다. (get → put)

   

5. result 값을 리턴한다.

 

1-2. 코드

from queue import Queue

class Stack:
    def __init__(self):
        self.main = Queue()
        self.sub = Queue()

    def push(self, x):
        self.main.put(x)

    def pop(self):
        if self.main.empty():
            return

        while self.main.qsize() != 1:  # 메인 큐가 1개 남을 때까지 임시 큐에 넣기
            self.sub.put(self.main.get())

        result = self.main.get()

        self.main, self.sub = self.sub, self.main  # swap
        return result

s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
print(s.pop())  # 4
print(s.pop())  # 3

---

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

💡 스택 한개는 InBox, 한 개는 OutBox 용도로 만든다.

1. inBox에 데이터를 push(삽입)한다. ex) 4→ 3→ 2→ 1
2. inBox에 있는 데이터를 pop(추출) 하여 outBox에 push(삽입) 한다. ex) 1→ 2→ 3→ 4
3. outBox에 있는 데이터를 pop(추출) 한다. - 4→ 3→ 2→ 1

 

2-1. 순서

1. inBox 에 데이터를 push(삽입)한다. ex) 4→ 3→ 2→ 1

   

2. inBox에 있는 데이터를 pop(추출) 하여 outBox에 push(삽입) 한다. ex) 1→ 2→ 3→ 4

   

   

3. outBox에 있는 데이터를 pop(추출) 한다. - 4→ 3→ 2→ 1

   

 

2-2. 코드

class Queue:
    def __init__(self):
        self.inbox = list()
        self.outbox = list()

    def push(self, item):
        self.inbox.append(item)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

queue = Queue()
queue.push(4)
queue.push(3)
queue.push(2)
queue.push(1)
print(queue.pop())
print(queue.pop())
print(queue.pop())
print(queue.pop())

---

참고

https://hyerios.tistory.com/48

https://www.geeksforgeeks.org/implement-stack-using-queue/