# 스택 (Stack)

정의

스택은 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료구조입니다.

입력과 출력이 한 방향으로 제한되어 있습니다.
함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법 등의 상황에서 사용됩니다.
시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 발생합니다.
그래프의 깊이 우선 탐색(DFS)과 재귀적(Recursion) 함수를 호출 할 때 사용합니다.

# 데이터 삽입&삭제 속도

O(1)
입구 및 출구에서 하나의 데이터를 바로 pop(), push() 하면 됩니다.

# 데이터 탐색 속도

O(n)
찾는 데이터가 존재하는지 투입된 역순으로 차례대로 검색해야 합니다.
따라서 운이 안 좋으면 저장된 모든 값을 확인해야 할 수도 있습니다.

# 자바에서의 Stack

바로 상위의 부모클래스로 Vector를 상속 받았습니다.

import java.util.Stack;

public class Sample {
    public static void main(String[] args) {
        // 스택 만들기
        Stack<Integer> stack = new Stack<>();
        
        // 삽입하기
        stack.push(1);
        stack.push(2);
        stack.push(3);
        
        // 가장 상위의 값 찍먹하기
        stack.peek(); // 3
        
        // 값을 꺼내기
        stack.pop(); // 3

        // 비어 있는지 확인하기
        stack.empty(); // stack이 비어있는제 check (비어있다면 true)

        // 찾고자 하는 값이 SP로 부터 얼마나 떨어져 있는지
        stack.search(2); // 없으면 -1, 2가 가장 위에 있으므로 1이다.
    }
}

위의 항목은 오로지 Stack 클래스에서만 추가된 메소드입니다.

다른 메소드는 Vector의 구현 메소드를 이용합니다.
혹시 위의 메소드들을 사용하고 있었나요? 벡터라는 부모에서 제공하는 메소드입니다.

# 참고자료

← 벡터(Vector) 큐 (Queue) →