특징
- 스택은 배열을 사용하면 고정된 크기를 가질 수 있으며, 연결 리스트를 사용하면 동적으로 크기를 변경할 수 있습니다.
- 들어온 순서의 반대 순서로 나갑니다. (LIFO - 후입선출)
메서드
Stack에서 사용하는 메서드에 대해서 알아보겠습니다.
push(), pop(), peek() 메서드는 모두 O(1)이라는 시간복잡도를 갖습니다.
| 메서드 | 설명 | |
|---|---|---|
Object push() | 원소를 객체에 삽입 | 스택이 꽉 찬 상태에서 데이터를 더 넣게되면 Stack Overflow condition이 됩니다. |
Object peek() | 다음에 빼낼 원소 조회. 스택의 꼭대기 요소 반환 | |
Object pop() | 원소를 빼내서 반환 | 스택이 비어있는 상태에서 꺼내려하면 Stack Underflow condition이 됩니다. |
boolean empty() | Stack이 비어있는지 여부 반환 | |
int search(Object o) | 주어진 객체를 찾아 위치 반환 | 위치는 1부터 시작하고 없으면 -1을 반환합니다. |
⁉️ Stack Overflow / Underflow
- Stack Overflow
- 스택이 고정된 크기를 가지는 경우, 예를 들어 배열 기반의 스택에서, 스택이 꽉 찬 상태에서
push메서드를 호출하면 발생합니다.
일반적으로 재귀 함수가 너무 깊어져 스택이 한계에 도달할 때도 발생할 수 있습니다.public void recursiveCall() { // 재귀 호출이 계속되면서 Stack Overflow 발생 recursiveCall(); }💡 배열 기반의 스택은 고정된 크기를 가지기 때문에 Stack Overflow의 위험이 있지만, 연결 리스트를 사용하면 동적으로 크기를 조정할 수 있어 이러한 위험이 줄어들게 됩니다!
- Stack Underflow
- 스택이 비어 있는 상태에서
pop메서드를 호출할 때 발생합니다.
예를 들어, 잘못된 루프 조건이나 논리 오류로 인해 비어 있는 스택에서 요소를 꺼내려고 할 때 발생합니다.Stack<Integer> stack = new Stack<>(); // 비어 있는 상태에서 pop 호출 -> Stack Underflow 발생 stack.pop();
코드로 보기
public class StackDemo {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("=====push=====");
System.out.println(stack);
System.out.println("=====pop=====");
System.out.println(stack.pop());
System.out.println("=====peek=====");
System.out.println(stack.peek());
System.out.println("=====empty=====");
System.out.println(stack.empty());
System.out.println("=====search=====");
System.out.println(stack.search(1));
}
}
활용 예시
- 함수 호출 관리: 함수 호출 시마다 호출 스택에 함수가 추가되고, 함수가 끝나면 스택에서 제거됩니다.
- 괄호 짝 검사: 컴파일러나 파서에서 중괄호, 대괄호 등의 짝을 검사할 때 스택이 사용됩니다.
- 깊이 우선 탐색(DFS): 그래프 탐색 알고리즘인 DFS에서 스택이 사용됩니다.
- Undo 기능: 문서 편집기에서 작업을 취소할 때, 이전 상태를 저장하고 되돌리는 기능에서 스택이 사용됩니다.
참고
꾸준히 성장하는 백엔드 개발자