[자료구조/스택,큐] 스택을 이용한 큐 구현

문제

• 스택을 이용해 다음 연산을 지원하는 큐 자료구조를 구현하라
  • push(x) : 값 x를 큐 마지막에 삽입하라
  • pop() : 큐의 처음에 있는 값을 제거한다.
  • peek() : 큐의 처음에 있는 값을 조회한다.
  • empty() : 큐가 비어있는지 여부를 확인한다.
• 원본 url : https://leetcode.com/problems/implement-queue-using-stacks/

 

문제 풀이

• 스택의 연산만을 활용하기 위해서는 2개의 스택이 필요하다
• 이유는 맨 마지막 값만을 활용할 수 있기 때문에 스택의 연산으로 값을 추출하면 값이 곧 최신에 들어간 값(마지막 값)이다.
• 그런데 큐는 맨 처음에 들어간 값이 추출돼야 해서 스택의 연산으로 할 경우 이동이 필요하다.
• output 값이 아무것도 없기 전까지는 재입력하는 알고리즘이 돌아가지 않는다
• 시간복잡도는 O(1) 로 계산되게끔 구현한다
• 실행속도 : 18 ms

class MyQueue(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.input.append(x)


    def pop(self):
        """
        :rtype: int
        """
        # input 값을 재정렬하는 과정 거친 후
        self.peek()
        # 제일 처음에 들어온 값을 추출
        return self.output.pop()

    def peek(self):
        """
        :rtype: int
        """
        # 출력값이 아무것도 없다면 입력값 확인해서 값 재정렬
        if not self.output:

            # 새로 들어온 값이 있다면
            # 해당 값은 output으로 queue 구조로 재입력 돼야 함
            while self.input:

                # 우선 input값에서 마지막 값을 빼고
                # 해당 값을 output에 집어 넣는다
                self.output.append(self.input.pop())

        # 결과값이 맨 마지막 위치한 값이 제일 처음 들어온 값으로 위에서 세팅했음
        return self.output[-1]


    def empty(self):
        """
        :rtype: bool
        """
        # 입력값과 결과값 stack을 모두 확인해야 함
        # 입력값에 값이 들어온 후 결과값에 재정령 안 돼 있을 수도 있기 때문
        return self.input == [] and self.output == []