[자료구조] 스택(stack)

[자료구조] 스택(stack)자료구조 | 알고리즘/선형 자료구죠2024. 3. 28. 11:07@BE_개발자

Table of Contents

728x90

이번 포스팅에서는 스택의 정의와 성질, 구현 방법, 활용에 대해서 정리합니다. 스택은 큐, 데큐와 서로 비슷한 부분이 많기 때문에 함께 공부하는 것을 적극 추천합니다.

또한 스택은 비교적 여러 알고리즘에서 활용합니다. 따라서 어렵더라도 제대로 이해하고 넘어가야 합니다.

1. 스택의 의미와 특징

스택이란?

마지막으로 들어온 원소가 제일 먼저 나가는 자료구조

더 이해하기 쉽게 풀어보면 한쪽 입구만 뚫린 터널이라고 생각할 수 있다. 이 구조는 데이터들이 한쪽으로만 들어갔다가 나오며 무언가 쌓는 모양을 생각할 수 있다. 이러한 형태 때문에 "쌓다"라는 의미에서 스택(stack)으로 불린다.

스택의 특징

LIFO(Last In First Out)의 구조를 가진다.
원소의 추가/제거/확인이 모두 O(1)이다.
최상단의 원소에만 접근할 수 있다.

스택이라는 자료구조는 최상단원소 말고는 확인할 상황이 필요하지 않다. 따라서 원칙적으로는 최상단의 데이터에만 접근 가능하다.

일상에서 활용 예시

스택은 어디에 활용될까?

우리는 다양한 상황에서 알게 모르게 스택을 사용했다. 대표적인 두 가지 상황을 살펴보자.

웹 페이지의 뒤로 가기

뒤로 가기 기능은 스택에 저장된 방문 기록을 바탕으로 실행된다.

페이지에 방문할 때마다 방문 기록을 스택에 저장한다.
"뒤로 가기" 버튼 클릭 시 최상단의 기록을 꺼내서 돌아간다.

위에서 알 수 있듯이, 방문 기록은 현재를 기준으로 마지막 방문 기록만 알면 된다. 이런 특징은 스택을 사용하기에 적합하다.

재귀 함수

재귀 함수는 함수가 실행된 상태에서 자신을 다시 호출한다. 또한 종료될 때에는 가장 마지막에 실행된 함수부터 거꾸로 종료된다. 이런 함수의 실행 순서는 FIFO의 특징을 가지기 때문에 스택을 사용한다.

2. 기능과 구현

스택은 파이썬의 라이브러리와 C++의 STL을 이용하면 쉽게 구현할 수 있다.

하지만 공부하는 입장에서 직접 구현해보면 얻어 가는 것이 많다. 따라서 이 글에서는 직접 구현하는 방식과 라이브러리를 사용하는 방식 모두 정리했다.

기능

push

상단에 새로운 원소를 추가하는 연산

스택의 크기를 초과하면 -1을 반환한다.
스택의 크기보다 작으면 상단에 원소를 추가한 후 반환한다.

pop

상단의 원소를 제거하는 연산

스택이 비어있을 경우 -1을 반환한다.
스택이 비어있지 않으면 상단의 원소를 제거 후 반환한다.

top

상단의 원소를 반환하는 연산

스택이 비어있는 경우 -1을 반환한다.
스택비 비어있지 않으면 상단의 원소를 반환한다.

size

스택의 크기를 반환하는 연산

단순히 스택의 크기를 반환한다.
size라는 변수를 만들어 관리하면 O(1)로 값을 가져올 수 있다.

empty

스택이 비어있는지 여부를 반환하는 연산

인덱스로 관리하기도 하지만 위에서 정의한 size 변수로 확인할 수 있다.
size가 0인 경우 True를, 그 밖의 경우 False를 반환한다.

구현

직접 구현

일반적으로 스택은 배열과 연결 리스트 두 가지 방법으로 구현할 수 있다. 이 글에서는 간단한 배열 방식으로 구현하였다.

구현 코드는 파이썬과 C++ 두 가지이다. (이후 Java 코드도 추가해볼 예정)

python 코드

class ArrayStack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.array = [None] * capacity
        self.size = 0

    def isEmpty(self):
        return self.size == 0

    def isFull(self):
        return self.size == self.capacity

    def top(self):
        return self.array[self.size - 1] if not self.isEmpty() else -1

    def push(self, x):
        if self.isFull():
            return -1
        self.array[self.size] = x
        self.size += 1
        return self.top()

    def pop(self):
        if self.isEmpty():
            return -1
        target = self.top()
        self.size -= 1
        return target

라이브러리 사용

python 코드

파이썬의 경우 collection라이브러리를 사용하면 deque를 이용하여 스택을 구현할 수 있다.

from collections import deque

def isEmpty(stack):
    return len(stack) == 0

sta = deque()
# 비어있는 스택 pop호출 시 index error
#sta.pop()

#push
sta.append(20)

#isEmpty
print(isEmpty(sta))

#size
size = len(sta)

print("size: {}".format(size))

#스택 출력
print(sta)

C++

C++의 경우에는 STL에서 스택을 지원한다.

일반적으로 배열이나 vector로 구현한다.

스택 구현 연습 문제

스택은 queue와 기능이 거의 동일하므로 기본적인 구현문제를 몇 개 풀어보면 금방 구현법은 익힐 수 있다.

[백준 10828] 스택

[백준 10773] 제로

[백준 1874] 스택 수열

위의 3문제는 스택 구현을 연습하기 좋은 가장 기본적인 문제들이다.

3. 스택의 활용

스택은 주로 언제 사용할까?

현재의 상황을 기준으로 가장 최근의 데이터를 조회해야 할 때

위의 개념을 활용한 스택을 활용한 문제는 대표적으로 두 가지 유형이 있다.

유형 1) 괄호쌍 유효성

[백준 4949] 괄호

아이디어

문제가 복잡해 보이지만 상황을 이해하고 나면 간단한 괄호쌍 검사 문제라는 것을 알 수 있다.

[ 는 ] 와 짝이 맞아야 하고 ( 는 ) 와 짝이 맞아야 한다.

[ 와 ] 의 개수, ( 와 ) 의 개수만 맞으면 되지 않을까? → [ ( ] )의 예외 발생
닫히는 괄호( ] or ) )가 나왔을 때 가장 최근의 열린 괄호가 존재해야 한다.
- ] 가 올바르다면 최근 열린 괄호가 [이어야 한다.
- )가 사라지려면 최근 열린 괄호가 (이어야 한다.

"현재 상황을 기준으로 가장 최근의 괄호들을 비교"해야 한다. 이는 스택을 사용하기에 적합한 조건이다.

해결 방법

스택을 떠올렸다면 닫힌 괄호가 나올 때 마지막 열린 괄호와 비교하여 짝을 맞춰 없애는 방법으로 해결할 수 있다.

모두 검사한 후 스택이 비어있다면 모든 쌍이 맞게 없어진 것이고 남아있다면 짝이 안맞는 괄호쌍이다.

자세한 풀이는 [스택을 활용한 괄호쌍의 유효성 검사]글에서 다루었으니 필요하면 참고해 주세요.

예제2) 스택을 이용한 정렬

[백준 2493] 탑

아이디어

자신보다 왼쪽에 있는 탑들 중 자신보다 크고 가장 가까운 탑을 찾는 문제이다.

왼쪽의 탑들 중 현재보다 큰 탑만 찾으면 된다.
현재보다 작은 탑은 고려하지 않아도 될까?
- 이후 현재 탑보다 작은 탑이 올 경우, 어차피 현재 탑이 송신탑이 된다.
- 이후 현재 탑보다 큰 탑이 올 경우, 어차피 현재 탑도 고려하지 않는다.

"현재 탑보다 큰 가장 최근의 탑"만 찾으면 된다. 이는 스택을 활용하기 적합하다.

여기서 중요한 점은 현재보다 작은 탑들은 고려하지 않아도 된다는 점이다.

해결 방법

내림차순을 유지하면서 스택에 현재 탑을 넣어주면 됩니다.

즉, 현재 탑을 스택에 추가할 때, 다음을 고려하면 된다.

스택에 상단이 현재보다 크다면 현재 탑을 스택에 push한다.
스택의 상단이 자신보다 작다면 자신보다 큰 탑이 나올 때까지 pop연산을 진행한다.
- pop연산을 진행한 후 원소가 남아있다면 그 원소가 송신탑이다.
- pop연산을 진행한 후 원소가 남아있지 않다면 송신탑이 존재하지 않는다.

여기서 중요한 점은 현재의 탑보다 작은 탑들은 고려하지 않는다는 점이다.

따라서 스택을 이용하면 O(N)으로 해결할 수 있다.

이 유형에 대한 자세한 내용은 [스택을 이용한 정렬]에서 정리했다.

4. 정리

스택은 STL과 라이브러리로 간단하게 구현할 수 있으며 괄호쌍의 유효성, 정렬 등의 상황에서 활용할 수 있다.

이외에도 스택은 DFS, 재귀, 백트래킹 알고리즘에 활용됩니다. 많은 문제를 풀며 이 상황이 왜 스택인지 논리적 타당성 얻어가는 것이다.

긴 글 읽어주셔서 감사합니다. 궁금한 점이나 부족한 점이 있다면 댓글을 남겨주세요.