[자료구조] 스택

 

스택 (Stack)

 

스택은 후입선출(Last In First Out, LIFO) 구조를 가진 자료구조

먼저 들어온 데이터가 아래로 쌓여서 마지막에 들어온 데이터가 먼저 나가는 구조이다.

 

주요 연산

• push(item) : 스택에 데이터를 삽입  /  O(1)의 시간복잡도를 가진다.
• pop() : 스택에서 데이터를 제거하고 반환  /  O(1)의 시간복잡도를 가진다.
• peek() : 스택의 맨 위 데이터를 반환(제거하지 않음)  /  O(1)의 시간복잡도를 가진다.
• isEmpty() : 스택이 비어 있는지 확인

* 접근 및 탐색에는 O(n) 의 시간복잡도를 가진다.

 

스택의 활용 예시

• 웹 브라우저의 뒤로가기 기능 (방문 기록 스택)
• 함수 호출 스택 (프로그램 실행 중 재귀 호출 관리)
• 수식 계산기 (후위 표기법 계산)
• 괄호 검사 문제 (열림/닫힘 괄호 짝 맞추기)

 

자바를 통한 간단한 스택 구현 예시

 

- 배열기반

class ArrayStack {
    int[] arr = new int[5];
    int top = -1;

    void push(int x) { arr[++top] = x; }
    int pop() { return arr[top--]; }
    int peek() { return arr[top]; }
    boolean isEmpty() { return top == -1; }
}

public class Main {
    public static void main(String[] args) {
        ArrayStack s = new ArrayStack();
        s.push(1); s.push(2); s.push(3);
        System.out.println(s.pop());   // 3
        System.out.println(s.peek());  // 2
    }
}

 

 

- 연결 리스트 기반

 

class Node {
    int data;
    Node next;
    Node(int d) { data = d; }
}

class LinkedStack {
    Node top = null;

    void push(int x) {
        Node n = new Node(x);
        n.next = top;
        top = n;
    }
    int pop() { int v = top.data; top = top.next; return v; }
    int peek() { return top.data; }
    boolean isEmpty() { return top == null; }
}

public class Main2 {
    public static void main(String[] args) {
        LinkedStack s = new LinkedStack();
        s.push(1); s.push(2); s.push(3);
        System.out.println(s.pop());   // 3
        System.out.println(s.peek());  // 2
    }
}