24. Implement Queue using Stacks

🎯 leetcode - 232. Implement Queue using Stacks

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 24번 문제

📌 날짜

2020.01.30

📌 시도 횟수

3 try

💡 Code

class MyQueue:
    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> int:
        new_stack = []
        while len(self.stack) != 1:
            new_stack.append(self.stack.pop())
        result = self.stack.pop()
        while new_stack:
            self.stack.append(new_stack.pop())
        return result

    def peek(self) -> int:
        result = self.pop()
        self.stack.append(result)
        for _ in range(len(self.stack) - 1):
            self.stack.append(self.pop())
        return result

    def empty(self) -> bool:
        return self.stack == []

💡 문제 해결 방법

1. pop()
- pop을 구현하기 위해 new_stack을 한 개 더 만들었다.
- queue.pop은 stack의 마지막 요소를 뽑아내는 것이다.
- 따라서 stack의 마지막 요소에 접근할 때까지 new_stack에 stack에서 뽑은 요소들을 차례대로 append한다.
- 마지막 요소에 접근하면 stack = new_stack을 해주고, 마지막 요소 값을 리턴한다.

2. peek()
- 먼저 peek값을 미리 구한 pop으로 구해 보관해논다.
- 그리고 pop한 stack을 다시 원 상태로 돌려놓기 위해
- for문을 len(stack)-1번 돌면서 pop한 값(큐의 맨 처음)을 다시 push한다.
>> ex. queue = (앞)[3, 4, 5](끝) 의 peek 구하는 과정
>> queue.pop() = 3 / [4, 5]
>> queue.append(3) = [4, 5, 3]
>> [4, 5, 3] -> [5, 3, 4] -> [3, 4, 5]

3. push()
- 구현한 큐는 index = 0부터 차례대로, [1, 2, 3... ]의 순서대로 삽입된다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 이 문제도 list를 사용하긴 했지만 list의 여러가지 함수들 중
stack의 성질을 구현하는 함수들만 사용해야 한다.
- 맨 처음 방법에서 리스트 슬라이싱으로 금방 풀었는데, 리스트 슬라이싱은
스택에서 사용될 수 있는 함수가 아니므로 조건을 위반한 풀이가 된다!

---

😉 다른 풀이

📌 하나. 스택 2개 사용하기

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

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

    def pop(self):
        self.peek()
        return self.output.pop()

    def peek(self):
        # output이 없으면 모두 재입력
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self):
        return self.input == [] and self.output == []
	
    # 디버깅용 print_stack
    def print_stack(self):
        print(self.input + self.output[::-1])

🌵이해가 잘 안된다면...🌵

💡 새롭게 알게 된 점

>> 스택을 뒤집어서 요소를 삭제한다 == 큐의 요소를 삭제한다 <<를 이용한 코드이다!
- 주요 해결 방법은 2개의 스택을 각각 다르게 이용하는 것이다.
- 삽입할때는 input = [1, 2, 3, ++ ...]처럼 정방향으로 더한다.
- 제거할때는 정방향의 list를 반대로 뒤집어서 원소를 삭제한다.
이때 반대로 뒤집은 결과를 담을 stack이 바로 output인 것이다.
- 이것은 모두 stack이 기본적으로 뒤에서 삽입하고 뒤에서 빼는 동시에,
queue는 뒤에서 삽입하고 앞에서 빼는 방식이기 때문에 가능하다.
- 즉, stack과 queue의 빼는 방향이 다르므로, 애초에 pop할 때(혹은 peek) 삭제하는 방향만 바꿔주면 된다.

---