1. 정의
스택은 연산이 제한된 선형 리스트입니다. 가장 큰 특징은 선입후출(LIFO, Last-In, First-Out) 원칙을 따른다는 것입니다.
2. 특징
스택의 핵심 특징은 다음과 같습니다:
- 데이터의 삽입(Push)과 삭제(Pop)는 오직 한쪽 끝에서만 이루어집니다.
이 연산이 이루어지는 끝을 스택의 꼭대기(Top)라고 하며, 반대쪽 끝을 스택의 바닥(Bottom)이라고 합니다.
3. 기본 연산
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
push |
요소를 스택에 추가 (삽입) | O(1) |
pop |
스택의 최상단 요소를 제거하고 반환 (삭제) | O(1) |
peek |
스택의 최상단 요소를 제거하지 않고 반환 (조회) | O(1) |
isEmpty |
스택이 비어 있는지 여부 확인 | O(1) |
size |
스택에 포함된 요소의 개수 반환 | O(1) |
4. 구현 방법
스택은 본질적으로 선형 자료구조이므로, 다음과 같은 방법으로 구현할 수 있습니다:
- 배열 (Array)
- 연결 리스트 (Linked List)
4.1 배열 기반 스택 (순차 스택)
배열을 사용하여 스택을 구현할 수 있습니다. 이때, 배열의 특정 인덱스를 스택의 최상단(Top)으로 관리합니다.
public class ArrayStack {
private int[] elements;
private int topIndex; // 현재 스택의 최상단 인덱스를 가리킴
public ArrayStack(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("용량은 0보다 커야 합니다.");
}
elements = new int[capacity];
topIndex = -1; // 초기에는 비어있으므로 -1로 설정
}
// 요소 추가 (Push)
public void push(int value) {
if (topIndex == elements.length - 1) {
throw new StackOverflowError("스택이 가득 찼습니다.");
}
elements[++topIndex] = value; // 최상단 인덱스를 증가시키고 요소 추가
}
// 요소 제거 및 반환 (Pop)
public int pop() {
if (isEmpty()) {
throw new IllegalStateException("스택이 비어 있습니다.");
}
return elements[topIndex--]; // 현재 최상단 요소를 반환하고 인덱스 감소
}
// 최상단 요소 조회 (Peek)
public int peek() {
if (isEmpty()) {
throw new IllegalStateException("스택이 비어 있습니다.");
}
return elements[topIndex]; // 현재 최상단 요소 반환
}
// 스택이 비어 있는지 확인
public boolean isEmpty() {
return topIndex == -1;
}
// 스택의 크기 반환
public int size() {
return topIndex + 1;
}
}
4.2 Java의 내장 Stack 클래스
Java는 java.util.Stack 클래스를 제공하여 스택 기능을 쉽게 사용할 수 있게 합니다.
import java.util.Stack;
public class JavaStackExample {
public static void main(String[] args) {
Stack<Integer> myStack = new Stack<>();
myStack.push(10); // 10을 스택에 추가
myStack.push(20); // 20을 스택에 추가
myStack.push(30); // 30을 스택에 추가
System.out.println("현재 스택: " + myStack); // 출력: 현재 스택: [10, 20, 30]
System.out.println("최상단 요소: " + myStack.peek()); // 출력: 최상단 요소: 30
System.out.println("요소 제거: " + myStack.pop()); // 출력: 요소 제거: 30
System.out.println("제거 후 스택: " + myStack); // 출력: 제거 후 스택: [10, 20]
}
}
출력 결과:
현재 스택: [10, 20, 30] 최상단 요소: 30 요소 제거: 30 제거 후 스택: [10, 20]
4.3 Deque 인터페이스 활용
Java의 java.util.Deque (Double Ended Queue) 인터페이스는 양쪽 끝에서 삽입/삭제가 가능한 자료구조입니다. 이 인터페이스의 한쪽 끝만 사용하면 스택처럼 활용할 수 있습니다.
Deque는 인터페이스이므로 직접 인스턴스화할 수 없습니다. 대신 ArrayDeque와 같은 구현 클래스를 사용합니다. 변수 타입을 Deque로 선언하고 ArrayDeque 객체를 할당하는 것은 다형성의 좋은 예시입니다.
// Deque 인터페이스 타입의 변수에 ArrayDeque 구현체 객체 할당
Deque<Integer> stack = new ArrayDeque<>();
코드 예시:
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeStackExample {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10); // 스택 꼭대기에 10 추가
stack.push(20); // 스택 꼭대기에 20 추가
stack.push(30); // 스택 꼭대기에 30 추가
System.out.println("가장 위에 있는 요소: " + stack.peek()); // 30 출력
System.out.println("요소 제거: " + stack.pop()); // 30 제거 및 반환
System.out.println("제거 후 가장 위에 있는 요소: " + stack.peek()); // 20 출력
}
}
5. 스택의 주요 활용 분야
- 함수 호출 관리 (콜 스택)
- 괄호 일치 검사
- 깊이 우선 탐색 (DFS) 알고리즘
- 수식 계산 (예: 후위 표기법 계산)
6. 스택과 큐의 차이점
스택과 큐는 둘 다 선형 자료구조이지만, 데이터 처리 방식에서 근본적인 차이가 있습니다.
| 구분 | 스택 (Stack) | 큐 (Queue) |
|---|---|---|
| 처리 규칙 | 선입후출 (LIFO) | 선입선출 (FIFO) |
| 삽입 위치 | 스택 꼭대기 (Top) | 큐의 꼬리 (Rear/Tail) |
| 삭제 위치 | 스택 꼭대기 (Top) | 큐의 머리 (Front/Head) |
| 대표적 활용 | 괄호 검사, 함수 호출 | 메시지 큐, 작업 스케줄링 |