자료구조: 스택(Stack)

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)
대표적 활용 괄호 검사, 함수 호출 메시지 큐, 작업 스케줄링

태그: 스택 자료구조 배열 연결리스트 deque

10월 22일 15:34에 게시됨