요약

스택은 후입선출(LIFO)로 이뤄진 자료구조이며 깊이 우선 탐색(DFS), 백트래킹에서 주로 사용된다.
메서드로는 push, pop(), peek(), empty() 등이 있다.

스택

스택이란?

스택은 삽입과 삭제 연산이 후입선출LIFO 로 이뤄진 자료구조이다.
후입 선출은 삽입과 삭제가 한쪽에서만 일어나는 특징이 있다.

위 그림처럼 한개의 빈 스택과 3개의 데이터가 있다.

맨 앞의 첫번째 데이터를 스택에 넣는다.

이후 두번째 데이터도 스택에 넣는다.

이후 세번째 데이터도 스택에 넣는다.

이렇게 되면 스택 제일 상단에는 가장 마지막에 들어온 세번째 데이터가 위치하게 된다.

그렇게 되면 자연스럽게 세번째 데이터가 먼저 나가게 되고 가장 먼저 들어온 첫번째 데이터가 가장 마지막에 나가게 된다.

메서드

• push(값) : 스택의 맨 위에 값을 추가한다.
  

• pop() : 스택의 맨 위에 있는 요소를 제거하고 반환한다. 스택이 비어있으면 EmptyStackException이 발생한다.
  

• peek() : 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.
  

• empty() : 스택이 비어있으면 true를, 비어 있지 않으면 false를 반환한다.

사용 방법

간단한 예제를 통해 자바의 사용 방법을 알아보자.
자바에서 스택을 사용하려면 java.util.Stack패키지를 임포트 시켜야 된다.
이후 Stact<요소/클래스> 이름 = new Stack<요소/클래스>()로 스택을 선언해주자

import java.util.Stack;
public class Main {
    public static void main(String[] args){
        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        
        while(!stack.empty()) {
            System.out.println(stack.pop());
        }
    }
}

결과
4
3
2
1

스택의 후입선출(LIFO)은 개념 자체가 재귀 함수 알고리즘(순환) 원리와 일맥상통하기 떄문에 주로 깊이 우선 탐색(DFS), 백트래킹에서 효과적으로 사용된다.
또한 스택은 형태가 특이하기 때문에 응용하는 문제가 많이나온다. 그러니 원리만 잘 알아두면 좋다!