선형 구조
데이터가 선처럼 일렬로 쭉 나열된 형태를 의미한다
선형구조에는 스택(Stack), 큐(Queue), 덱(deque), 순차 리스트, 연결 리스트가 있다
- 스택은 후입선출(LIFO, Last-In-First-Out)의 특성
- 큐는 선입선출(FIFO, First-In-First-Out)의 특성
- 덱은 양쪽 끝에서 삽입과 삭제가 가능한 형태의 구조
비선형 구조
데이터가 일렬로 나열되지 않은 형태를 의미한다
비선형 구조에는 트리(Tree), 그래프(Graph)가 있다
Stack
스택(Stack)은 데이터를 차곡차곡 쌓아 올리는 '상자' 또는 '접시' 같은 자료구조이다
Stack의 특징
- 후입선출(LIFO: Last In First Out)구조 - 가장 마지막에 들어간 것이 가장 먼저 나온다
- 단일 입출력 - 데이터가 들어가는 입구와 나오는 출구가 같다
- 데이터를 하나씩 넣고 뺄 수 있다
- 활용 분야
- DFS(깊이 우선 탐색) - 그래프나 트리 탐색 시 방문 경로를 추적하는 데 사용
Stack의 선언
Stack<Integer> stackInt = new Stack<>();
Stack<String> stackStr = new Stack<>();
Stack<Boolean> stackBoolean = new Stack<>();데이터 타입은 클래스 또는 래퍼 클래스로 선언할 수 있다
Stack 클래스 주요 메서드
1. push()
- 기능 - 스택의 맨 위에 데이터를 추가
- 반환값 - 추가된 데이터
Stack<Integer> stack = new Stack<>();
stack.push(1); // 스택: [1]
stack.push(2); // 스택: [1, 2]
stack.push(3); // 스택: [1, 2, 3] (3이 맨 위)2. pop()
- 기능 - 스택의 맨 위에서 데이터를 꺼내고 제거
- 반환값 - 제거된 데이터
int topItem = stack.pop(); // topItem = 3, 스택: [1, 2]3. peek()
- 기능 - 스택의 맨 위 데이터를 제거하지 않고 확인만 함
- 반환값 - 맨 위의 데이터
int peekItem = stack.peek(); // peekItem = 2, 스택: [1, 2] (변화 없음)💡스택이 비어있는 상태에서 pop(), peek() 호출 시
EmptyStackException발생
4. isEmpty()
- 기능 - 스택이 비어있는지 확인
- 반환값 -
true(비어있음),false(데이터가 있음)
5. size()
- 기능 - 스택에 들어있는 데이터의 개수를 반환
- 반환값 - 데이터 개수(정수)
int size = stack.size(); // size = 2