[2024] Day31. 232. Implement Queue using Stacks
코딩테스트
2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 1월 31일 (수)
Leetcode daily problem
232. Implement Queue using Stacks
Problem
두 개의 스택만 사용하여 FIFO(선입선출) 인 자료구조 큐를 구현한다. 구현된 큐는 일반 큐의 모든 기능(push, peek, pop, empty)을 지원해야 합니다.
MyQueue 클래스를 구현해서
void push(int x)는 요소 x를 대기열 뒤로 밀어 넣는다.
int pop()은 대기열의 앞부분에서 요소를 제거하고 반환한다.
int peek()은 대기열의 맨 앞에 있는 요소를 반환한다.
booleanempty() 대기열이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.
노트:
스택의 표준 작업만 사용해서 구현해야 한다.
즉 스택의 push, peek/pop, size, empty 등만 사용 가능하다. 언에 따라 스택이 기본적으로 지원되지 않을 수 있.
스택의 표준 작업만 사용하는 한 목록 또는 deque(양단 큐)를 사용하여 스택을 시뮬레이션할 수 있다.
Solution
data structure
스택으로 사용할 리스트(베열)을 2개 생성한다.
생성한 리스트를 각각 listA, listB라고 한다면
push 메소드는 생성한 배열에 원소를 넣었다 뺐다 하면서 진행하는데, 예를 들어 처음 들어오는 원소는 listA에 넣는다.
그 다음 push로 다른 원소가 들어온다면 listA에 먼저 들어와 있던 이전 원소를 listB에 pop을 통해서 먼저 들어온 순서대로 listB로 옮긴다. 그 후 현재 push로 들어오는 원소를
Code
class MyQueue:
def __init__(self):
self.lst1 = []
self.lst2 = []
def push(self, x: int) -> None:
while self.lst1:
self.lst2.append(self.lst1.pop())
self.lst1.append(x)
while self.lst2:
self.lst1.append(self.lst2.pop())
def pop(self) -> int:
return self.lst1.pop()
def peek(self) -> int:
return self.lst1[-1]
def empty(self) -> bool:
return not self.lst1
Complexicity
시간 복잡도
push의 경우 lst1에 있는 모든 요소를 lst2로 이동해야 하므로, 해당 시간 복잡도는 O(n), 리스트에 요소를 추가하는 것은 O(1)
pop 연산의 경우 lst1에서 마지막 요소를 제거하므로 O(1)
peek 연산의 경우 마지막 요소를 반환하기 때문에 O(1)
empty 연산의 경우 lst1이 비어 있는지 확인하기만 하면 되므로 O(1)
공간 복잡도
두 개의 lst1, lst2의 배열을 사용해 요소를 저장하므, 저장된 요소의 수만큼의 공간 복잡도는 O(n)이다.
