[Leetcode] 225. Implement Stack using Queues

✅ 문제 - 큐를 이용한 스택 구현

 

 

 

---

 

✅ 풀이 코드

 

💡 문제 이해하기
이 문제는 큐를 이용해서 스택을 구현해야 한다.
스택은 LIFO(Last In First Out) 방식으로, 요소를 가로로 놓고 봤을 때 사실상 마지막 요소만 가지고 연산을 한다.

MyStack 클래스의 구현 내용 정의한 것을 보면 알고 있는 스택이 연산하는 방식과 조금 다르다.
1. push: 스택의 가장 첫 번째 자리에 요소 x를 삽입해야 한다.
    → stack은 요소 삽입 시 가장 마지막 자리에 요소가 삽입되므로 삽입 후 첫 번째 자리로 보내야 한다.
2. pop, top: 가장 첫 번째 자리 요소를 삭제하거나 반환해야 함

따라서 양 방향으로 연산이 가능하게끔 스택과 큐의 결합구조인 데크를 이용해서 이 문제를 풀어야 한다.

 

 

class MyStack:

    def __init__(self):
        self.q = collections.deque() 
        
    # 스택의 첫 번째에 x 삽입
    # 스택은 요소 삽입시 가장 오른쪽으로 가므로
    # 삽입 후 가장 왼쪽으로 가도록 정렬해주어야 함
    def push(self, x: int) -> None:
        self.q.append(x) 
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())

    # 첫 번째 요소 삭제
    # 가장 왼쪽에 있는 요소 삭제 
    def pop(self) -> int:
        return self.q.popleft()
        
    # 첫 번째 요소 반환
    def top(self) -> int:
        return self.q[0]
        
    # 스택이 비어있는지 확인
    def empty(self) -> bool:
        return len(self.q)==0

 

 

---

 

 

++ 추가적으로 제일 헷갈렸던 push 함수를 보자

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())

 

 

x=5일 때, 5가 제일 오른쪽에 추가된 이후에

popleft()를 통해 가장 왼쪽에 있는 요소를 제거하고, 그 값을 append()로 가장 오른쪽으로 추가한다.

이를 4번 반복하면 처음에 추가했던 5가 제일 왼쪽으로 정렬이 된 것을 볼 수 있다.

따라서 반복문에서는 self.q의 길이보다 1번 더 적게 이를 반복하면 원하는 대로 정렬할 수 있다.