[자료구조] 스택, 큐

선형적인 자료구조 스택과 큐에 대해 정리

스택

• LIFO (Last In First Out)
• Python에서는 스택 자료형을 따로 제공하지는 않지만 리스트가 스택의 연산들을 모두 제공한다.
• 리스트에서 append, pop이 O(1)로 빠르기 때문에 리스트를 스택을 구현한다.

큐

• FIFO (First In First Out)
• Python에서 리스트를 사용하면 된지만 큐 연산을 수행하기에는 효율적이지는 않다.
• 그래서 deque라는 별도의 자료형을 사용하면 더 좋은 성능을 이용할 수 있다.

Python

• Link
• 유효한 괄호
• 중복 문자 제거
• 일일 온도
• 큐를 이용한 스택 구현
  • deque 이용
• 스택을 이용한 큐 구현
  • 두 개의 스택(리스트)을 이용
• 원형 큐 디자인

Reference

• 파이썬 알고리즘 인터뷰 (박상길 지음)