[Algorithm] 06. 스택 (Stack)

스택 (Stack)

 

스택(Stack)은 마지막에 추가된 데이터가 먼저 출력되는 후입선출(LIFO) 방식으로 데이터를 저장하는 자료구조이다.

스택의 top에 데이터를 추가하는 것을 push, 스택의 top에서 데이터를 추출하는 것을 push라고 한다.

 

스택(Stack)은 Deque 인터페이스를 사용한다.

스택(Stack)을 구현하는 방법에는 Linked List를 기반으로 한 방법과 Deque를 기반으로 한 방법이 있다.

 

 

 

Linked List 기반의 Stack

 

Linked List를 기반으로 한 Stack은 선형 자료구조로 LIFO(Last In Fist Out) 방식으로 요소를 처리한다.

Deque<Integer> s = new LinkedList<>();

 

 

 

Deque 기반의 Stack

 

ArrayDeque를 기반으로 한 Stack은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다.

Deque<Integer> s = new ArrayDeque<>();

 

※  Linked List 기반 vs ArrayDeque 기반

ArrayDeque의 양쪽 끝에서는 삽입과 삭제 연산을 O(1)O(1)의 시간 복잡도로 지원한다.
따라서 특별한 이유가 없다면 ArrauDeque 기반의 Queue를 사용하는 것이 좋다.

 

 

 

Stack 연산

 

Deque<Integer> s = new ArrayDeque<>();

// push
s.push(1);                               // s = [1]
s.push(2);                               // s = [2, 1]
s.push(3);                               // s = [3, 2, 1]

// pop
System.out.println(s.peek());            // 출력 = 3   // q = [3, 2, 1]
System.out.println(s.pop());             // 출력 = 3   // q = [2, 1]
System.out.println(s.pop());             // 출력 = 2   // q = [1]

 

 

 

Stack 사용 시기

 

1. DFS (깊이 우선 탐색)

 

DFS는 그래프나 트리의 시작 노드에서 출발해 한 경로를 끝까지 탐색하는 방법이다.

경로를 탐색하다가 더 이상 탐색할 노드가 없으며 바로 이전 단계로 돌아가 다른 경로를 탐색한다.

이 과정에서 재귀적으로 탐색을 하거나 스택을 사용하여 경로를 추적한다.

• 미로 탐색 : 미로에서 출구를 찾기 위해 한 방향으로 가다가 막히면 이전 교차로로 돌아가 다른 길을 찾는다.       

 

2. 백트래킹

 

문제 해결 과정에서 유망하지 않은 경로를 탐색하다가, 조건이 만족되지 않으면 다른 경로를 시도하는 방법이다. 

스택은 되돌아가는 경로를 관리하는데 유용하다.

• N-Queen 문제 : 스택을 사용하여 퀸의 배치를 시도하고, 유망하지 않은 경우 다른 배치를 시도한다.

 

3. 괄호 검사 및 문자열 처리

 

여는 괄호와 닫는 괄호가 짝을 이루는지 확인하거나, 후위 표기법 계산 등에서 사용한다.

 

• 괄호의 유효성 검사 : 여는 괄호는 스택에 넣고, 닫는 괄호가 나오면 스택의 괄호와 짝이 맞는지 확인한다.
• 후위 표기법 계산 : 연산자와 피연산자를 스택에 저장하고, 스택에서 피연산자를 꺼내 연산한다.