[이것이 코딩 테스트다] 꼭 필요한 자료구조 기초 ( 스택, 큐)

0. 개요

1) 탐색

: 많은 양의 데이터 중 원하는 데이터 찾는 과정

   ex) 대표적인 탐색 알고리즘 : DFS, BFS

• DFS, BFS 원리를 제대로 이해해야 코딩테스트 탐색문제 풀 수 있음
• -> 이해하기 위해서 자료구조 기초인 스택과 큐에 대해 알아야 함
• 스택, 큐, 재귀함수 사전학습

 

2) 자료구조

: 데이터를 표현하고 관리하고 처리하기 위한 구조

스택, 큐 핵심 함수 / 고려사항

• 삽입 (push) : 데이터 삽입
• 삭제 (pop) : 데이터 삭제
• 오버플로우 : 수용할 수 있는 공간 없는데 삽입 연산 수행 할 때 발생
• 언더플로우 : 데이터가 전혀 없는 상태에서 삭제 연산 수행 시 발생

---

1. 스택 (Stack)

1) 스택이란 

• 자료구조의 기초 개념
• 박스 쌓기
• 선입후출, 후입선출 구조 (LIFO : Last In First Out)

2) 코드

import java.util.*; 를 해줌

Stack <Integer> s = new Stack<>();

s.push(5);
s.push(3);
s.push(7);
s.pop();

---

2. 큐 (Queue)

1) 큐란

• 자료구조의 기초개념
• 터널
• 선입선출구조 (FIFO : First In First Out)

2) 코드

import java.util.*;

Queue <Integer> q = new LinkedList<>();

q.push(5);
q.push(3);
q.push(7);
q.pop();

---

3. 재귀함수

: 자기 자신을 다시 호출하는 함수

 

1) 재귀함수 종료조건

재귀함수가 언제 끝날 지 종료 조건을 명시해야 됨.

 

2) 재귀함수와 스택

• 재귀함수는 내부적으로 스택 자료구조와 동일
• 함수를 계속 호출 했을 때 가장 마지막에 호출한 함수가 수행을 끝내야 가장 처음 호출했던 함수가 수행을 마무리 할 수 있음( = 스택!)
• 스택 자료구조를 활용해야 하는 상당수의 알고리즘은 재귀함수를 통해 간편히 구현 될 수 있음 ex) DFS

 

3) 점화식 이용

• 점화식 ( 재귀식)을 그대로 소스코드로 옮김 -> 간결
• 점화식 : 특정 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것
•  EX) 팩토리얼 
  • N=0 or N=1 : factorial(N)=1
  • N>1 : factorial(N) = N * factorial(N-1)