스택(Stack)

개요

스택 자료구조에 대해서 알아본다.

스택(Stack)이란?

 스택은 데이터를 저장할 객체와 객체에 적용할 수 있는 연산을 함께 정의한 추상 자료형으로써, 앞으로 다룰 큐(Queue), 데크(Deque)와 같이 자료 구조 형태에 이름이 붙었다는 것에서 큰 의의를 갖는 자료형이다. 스택은 너무나도 잘 알려져 있기에 간단하게 특징을 살펴본다.

 위 이미지에서 6개의 선으로 간단하게 표현해서 알아보기 힘들 수는 있지만, 아래 용어정의들을 통해서 스택의 개념을 온전히 이해할 수 있을 것이라 생각한다.

1. LIFO(Last In First Out)

스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는데, 가장 늦게 들어간 자료가 가장 먼저 나오게 된다.

2. TOP

한쪽 끝에서만 데이터 입출입이 발생한다고 하였는데, 스택에서 이 입출입이 발생하는 지점 즉 스택의 최상단을 top이라고 지칭한다.

3. Push / Pop

자료구조에 데이터를 넣고 빼는 것을 일반적인 언어의 list 형태의 자료구조에서는 'add'로 지원하고 있으나, 스택을 비롯한 추상자료형에서는 데이터를 넣는 것을 push, 빼는 것을 pop으로 지칭한다.

스택은 연결 리스트를 사용해서 구현할 수도, 동적 배열을 사용해서 구현할 수도 있으나, Java의 경우 `Vector` 를 상속받아서 구현되어 있으므로 '동적배열'을 사용하고 있다고 볼 수 있다. 대다수의 언어의 표준 라이브러리에서 스택은 구현체를 제공하고 있으므로, PS 중심적으로 봤을 때 스택을 직접 구현하면서 시간을 낭비할 필요는 없다.

---

스택 응용

 사실 단순한 비즈니스 로직(CRUD)을 구현함에 있어서 스택을 사용할 일은 거의 없다고 봐도 무방하므로, 스택이 언제 어떤 경우에 필요한가를 느껴볼 필요가 있다고 생각한다. 아~ Java의 VM은 스택 기반의 VM이더라. 스택에는 호출되는 메서드의 정보인 frame이 저장되고, 허용되는 Stack의 범위를 넘겼을 때 StackOverflow가 발생하더라! 정도 그리고 스택이 어떤 자료구조형이다만 알아도 문제는 없지만, 상황에 적절한 추상 자료형을 사용하기 위해서는 이렇게도 쓸 수 있구나 라는 것을 경험해보는 것이 중요하다고 생각하기 때문이다.

대표적인 문제는 막대기 문제다. 아래 문제 링크를 참고하자.

17608번: 막대기

출처 - https://www.acmicpc.net/problem/17608

해당 문제에서는 '순서'가 굉장히 중요하다. 이유는 단순히 최대높이나, 가장 오른쪽의 블록만을 기준으로 판단할 수가 없기 때문이다. 그 이상의 블록이 보이는지 보이지 않는지 판단하기 위해서는 현재 볼 수 있는지의 여부를 결정하는 블록의 길이를 갱신해주어야 하기 때문이다. 백문이 불여일견이라고 간단하게 코드로 스택을 이런 경우에 활용할 수 있구나를 익혀보자.

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		Stack<Integer> stack = new Stack<Integer>();
		for(int i = 0; i < N; i++) 
			stack.push(Integer.parseInt(br.readLine()));
		
		int cnt = 1;
		int max = stack.pop();
		while(!stack.isEmpty()) {
			if(stack.peek() > max) {
				cnt++;
				max = stack.peek();
			}
			stack.pop();
		}
		
		bw.write(String.valueOf(cnt));
		bw.flush();
		bw.close();
		br.close();
	}
}

 

참고 문제

1. Silver 4 - 10828번 스택
 스택의 기본 함수와 개념에 대해서 익힐 수 있는 기본 문제로, 각 구현하고자 하는 언어의 스택 표준 라이브러리를 활용해보는 겸 풀어보자.

10828번: 스택

2. Gold 5 - 2493번 탑

2493번: 탑

3. Platinum 5 - 1725번 히스토그램

1725번: 히스토그램