[파이썬 알고리즘 인터뷰] 스택, 큐

- 스택: lifo, 큐: fifo

- 파이썬 리스트는 스택과 큐의 모든 연산 수행 가능

- 그러나 성능을 고려한다면 큐는 데크를 사용해야 좋음

- 스택 ADT에서는 차곡차곡 쌓이지만, 실제 연결리스트로 구현 시 무작위로 배치되고 포인터로 처리

 

※ 참고: 클래스의 메소드에서 self는 인스턴스 자체, 인스턴스로 메소드 호출하면 자동으로 인스턴스(self) 인자로 넣음

 

20. valid parentheses

- 딕셔너리 활용

- 스택에 왼 괄호 쌓기

 

316. remove duplicate letters

- 재귀(분리 가능하냐로 접근)

- 스택에 문자 쌓으면서 비교

- collections.Counter()

 

739. daily temperatures

* [0] * len(T)

- 스택에 인덱스 쌓으면서 온도 비교

- enumerate()

 

225. implement stack using queues

- 첫 값만 뺄 수 있으므로, 푸쉬하고 첫 인덱스로 되게끔 조작

 

232. implement queue using stacks

- 스택 두개로 구성: 한 스택에 쌓다가 peek 하면 다 빼서 다른 스택에 모두 재입력

- 내 풀이: 큐로 스택 구현하듯이 푸쉬할때 미리 스택 조작

 

622. design circular queue

※ 원형 큐는 일반 큐와 다르게 pop한 공간을 재사용할 수 있다.

- 포인터 두개 설정(front, rear)

- 내 풀이: enQueue할 때마다 리스트 조작