자료구조_스택(Stack) & 큐(Queue)

⭐ 프로그램의 성능을 결정하는 2가지 요인

1. 메모리 성능 ← 자료구조가 결정
2. 로직의 속도 ← 알고리즘이 결정

⭐ 자료구조 종류

• Stack vs Queue
• Array vs List (ArrayList, LinkedList)
• Map, Set, Tree, ...

 

어떤 상황에서

어떤 자료구조를 선택해야할까? → 자료구조를 결정하는 것이 중요해짐

---

[ Stack ]

• 스택(Stack) 자료구조는, 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조
• 출입구가 1개뿐인 자료구조
• 후입선출(LIFO, Last In First Out) 방식의 자료구조

활용예시

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 마지막에 열린 페이지부터 다시 보여줌
• 실행 취소 (undo) : 가장 마지막에 실행된 것부터 실행 취소
• 역순 문자열 만들기 : 가장 마지막에 입력된 문자부터 출력
• 후위 표기법 계산
• 수식의 괄호 검사 : 연산자 우선순위 표현을 위한 괄호 검사
• History류와 잘 어울림

[ Queue ]

• 큐(Queue) 는 "줄을 서서 기다린다."라는 사전적 의미를 가짐
• 입구와 출구가 별개로 존재하는 자료구조
• 먼저 들어온게 먼저 나가는 선입선출(FIFO, First In FirstOut) 방식의 자료구조

활용예시

• 주로, 데이터가 입력된 순서에 따라 처리되어야 할 때 사용 == 대기열
  • 일상생활에서, 줄을 서서 기다려야하는 모든 행동
  • 프로세스 관리
  • 너비 우선 탐색(BFS, Breadth-First Search) 구현
  • 캐시(Cache) 구현

📌연습

 

📌CodeUp 문제

https://codeup.kr/problem.php?id=3117

0은 빼!