Stack & Queue

📗 Stack & Queue

• stack과 queue는 데이터를 임시 저장하기 위해 사용하는 자료구조
  
  

🔔 Stack

• stack은 FILO(선입후출) 방식을 따르는 자료구조
• 먼저 들어온 데이터가 나중에 나가는 방식
• 리스트 자료형을 사용해 구현함
  - stack.append() : 리스트 가장 뒤쪽에 데이터 삽입
  - stack.pop() : 리스트 가장 뒤쪽 데이터를 꺼냄

🔔 Queue

• queue는 FIFO(선입선출) 방식을 따르는 자료구조
• 먼저 들어온 데이터가 먼저 나가는 방식
• 3가지 방식으로 구현가능
  1. 리스트 자료형 사용
  - queue에 데이터를 넣는 enqueue를 append(), 데이터를 빼는 dequeue를 pop(0)로 구현 가능
  - pop(0)은 O(n)의 시간복잡도를 가지므로 더 효율적인 방법을 사용하는 것이 좋음
  2. queue module 사용
  - queue module의 Queue는 데이터를 단방향에서 추가하고 제거하는 자료구조임
  - enqueue를 위해서는 put(), dequeue를 위해서는 get()을 사용
  - get()은 리스트의 pop()과 다르게 시간 복잡도가 O(1)이므로 효율이 좋음
  3. deque class 사용
  - collections module의 deque는 데이터를 양방향에서 추가하고 제거하는 자료구조임
  - 양방향이므로 append(), pop(), appendleft(), popleft()로 데이터를 각각 맨 앞에서 삽입 또는 제거 가능
  - appendleft(), popleft()는 시간복잡도가 O(1)이므로 리스트보다 효율이 좋음
• 일반적으로 양방향을 지원하고 효율이 가장 좋은 dequeue를 이용해 queue를 구현함
  

📘 관련 문제

⭐ 같은 숫자는 싫어
⭐ 기능개발
⭐ 올바른 괄호
⭐ 프로세스
⭐ 다리를 지나는 트럭
⭐ 주식가격