샷건치며 배우는 자료구조 with C++, 5화

스택에 대해 알아봅시다.

읽어주세요

자료구조를 배우기 위해 위대한 항로(?)를 넘어 여기까지 오신 분들 환영합니다. 본 게시글은 자료구조를 공부하면서 복습 겸 정리하기 위해 작성하였습니다. 개인적으로 강좌 형식 및 장난을 섞어가며 작성하는 걸 좋아하기 때문에 진지한 게시글을 원하신다면 뒤로 가기를 눌러주세요.

C++ 언어를 기반으로 하고 있습니다. 다른 프로그래밍 언어를 사용 중이신 경우 개념(이론)을 배우는 데 큰 문제는 없지만, 실제 코드로 구현할 땐 생각보다 차이가 있을 수 있습니다.

업데이트

C 언어 구현 내용 제거
- 게시글의 내용이 너무 복잡해져 제거하였습니다.

게시글 개선을 위해 임시 숨김 처리

스택

스택... 어디서 많이 들어본 단어죠? 조금 더 와닿는 예시를 들자면 업보 스택이 있겠군요. 방송인이나 일부 커뮤니티를 보면 업보 스택 쌓는 중 ㅋㅋ라는 드립이 자주 달립니다. 지금까지 쌓아온 업보가 나에게 돌아온다는 의미죠. 업보 스택이라는 드립에 스택의 의미가 잘 담겨 있습니다.

스택^Stack은 가장 마지막에 들어온 데이터가 가장 먼저 나가는 특징을 가지고 있습니다. 이러한 특징을 후입선출^{Last-In First-Out, LIFO} 또는 선입후출^{First-In Last-Out, FILO}이라 합니다.

스택은 배열이나 연결 리스트를 기반으로 설계됩니다. 우리는 아직 연결 리스트를 배우지 않았기 때문에 이 기반은 생략합니다. 다만, 어느정도 언급만 하고 넘어가겠습니다.

스택은 크게 두 가지의 연산이 중요합니다. 스택의 최상단(1)에 데이터를 추가하는 PUSH(2) 연산과 최상단에 있는 데이터를 꺼내는 POP 연산입니다. 업보를 쌓는 게 PUSH 연산이라면, 이 업보가 나에게 돌아오는 건 POP이라 할 수 있습니다.

최상단^Top은 마지막 데이터가 위치하는 곳을 말합니다. 최상단으로 표현하는 이유는 스택은 중간에 있는 데이터에 접근할 수 없고, 가장 마지막에 있는 데이터만 접근할 수 있기 때문에 그렇습니다. 즉, 후입선출을 특징으로 하기 때문입니다.
pussy 아님

실생활에서 예시를 더 들자면... 스택은 위 사진 속 프링글스^PRINGLES 과자를 예시로 들 수 있겠습니다. 뒷광고 아닙니다!

프링글스 통 안에는 칩이 차곡히 쌓여 있고, 우리는 이 칩을 맨 위에서 부터 하나씩 꺼내서 먹습니다. 맨 아래에 있는 칩을 먹으려면 위에 있는 칩들을 다 꺼내 먹어야 하죠. 물론 통을 뒤집어서 꺼내면 되지만 이건 반칙이죠. 지금은 스택의 개념을 이해하기 위함이니 뒤집는 짓은 하지맙시다.

프링글스 통 안에 칩을 쌓을텐데 이러한 행위는 PUSH 연산에 비유할 수 있고, 뚜껑을 열고 맨 위에 있는 칩부터 꺼내 먹는 걸 POP 연산이라 할 수 있습니다.

특징

후입선출 또는 선입후출

스택의 데이터는 가장 마지막에 추가되고, 가장 마지막에 추가된 데이터를 꺼냅니다. 나중에 들어온 것이 먼저 나가고, 먼저 들어온 것이 나중에 나갑니다.
가장 최근 데이터만 접근 가능

스택은 가장 최근에 추가된 데이터만 TOP 연산을 통해 확인할 수 있습니다. 이전에 추가된 데이터는 확인할 수 없습니다. 오래된 업보는 나중에 치루는 꼴이죠.

대표적인 사용처

되돌리기와 복구 기능

문서나 그외 작업을 수행하다 실수하면 Ctrl+Z를 눌러 마지막 작업을 취소합니다. 이러한 기능을 취소 또는 되돌리기^Undo라고 합니다. 또는 다시 복구하려면 Ctrl+Y를 눌러 다시하기^Redo를 시도하죠. 이러한 기능은 스택 자료구조를 통해 구현합니다.

사용자의 마지막 작업을 POP 연산을 통해 취소하여 되돌리고, 되돌린 작업을 다른 스택에 저장하여 PUSH 연산으로 복구할 수 있습니다. 두 개의 스택을 이용하는 방법입니다.
보스 공격 패턴

보통은 랜덤하게 나타나도록 하지만... 보스의 공격 패턴을 스택으로 구현할 수 있습니다. 스택에 미리 보스의 공격 패턴을 저장한 후 순서대로 POP 연산을 통해 수행하도록 합니다.

기본 구조

stack_frame.cpp
constexpr auto MAX_SIZE = 10;

class Stack {
private:
    int data[MAX_SIZE];
    int top = -1;
};

배열 기반의 스택 기본 구조는 위 코드 예시와 같습니다.

data는 스택의 데이터를 저장하는 배열입니다. 위 코드 예시는 int가 사용되었지만, 데이터 타입은 여러분 마음대로 하면 됩니다. 그리고 배열 기반의 스택은 주로 최대 크기가 정해져 있습니다. 그래서 MAX_SIZE와 같이 배열의 최대 크기를 나타내는 상수를 사용합니다.

top은 스택의 최상단 인덱스를 가리키는 변수입니다. 초기값으로 -1이 할당되어 있는 데 이는 스택이 비어있음을 의미합니다. 배열의 인덱스는 0부터 시작하기 때문에 데이터가 없음(비어있음)을 나타내기 위해 관습적으로 -1이라는 값을 초기값으로 합니다.

주요 연산

스택의 주요 연산은 PUSH와 POP입니다. 나머지 연산은 스택의 보조적인 역할을 수행합니다.

스택 자료구조는 단순함을 추구합니다. 그렇기 때문에 아래에서 언급하지 않는 연산은 굳이 추가할 필요가 없습니다.

PUSH

PUSH 연산은 스택의 공간이 남아있는 지 확인한 후 최상단에 새 데이터를 추가합니다. 공간이 남아있다면 top의 값을 1 증가하고 데이터를 추가합니다. 실패하면 실패를 의미하는 값을 반환하거나 아무 연산도 안 하거나 예외를 발생시키기도 합니다.

이 연산은 최상단에서만 작업하기 때문에 상수 시간만 소요됩니다. 그래서 시간 복잡도는 \(O(1)\)입니다.

스택의 공간이 남아있는 지 확인하는 이유는 안전한 연산을 위해서 입니다. 즉, 스택 오버플로우^{Stack Overflow}를 방지하기 위함입니다. 주로 고정된 크기를 갖는 배열 기반의 스택에서 발생합니다. 정해진 크기를 넘어서 데이터를 추가할 수 없습니다. 이를 가능하게 하면 엉뚱한 곳(또는 사용중인 영역)에 데이터를 작성하게 됩니다. 어떠한 오류, 충돌을 불러올 지 알 수 없기 때문에 최대한 조심해야 합니다. 연결 리스트 기반의 경우 어지간하면 발생하지 않지만 시스템의 메모리가 부족해지면 발생할 수 있습니다.

마치 프링글스 통 안에 칩을 억지로 더 넣은 상태에서 뚜껑을 닫으려 시도하는 경우죠. 이미 가득차 있는 상태인데 말이죠. 업보가 너무 쌓여서 감당 못하고 터지는 그런 느낌인거죠...(?)

classstd::stack

stack_push.cpp
constexpr auto MAX_SIZE = 10;

//! @brief 스택 클래스
class Stack {
private:
    int data[MAX_SIZE];         //!< 데이터 배열
    int top;                    //!< 최상단을 가리키는 인덱스

public:
    //! @brief 기본 생성자
    Stack() {
        for (auto i = 0; i < MAX_SIZE; ++i) {
            this->data[i] = -1;
        }
        this->top = -1;
    }

    //! @brief 데이터 추가 메서드
    //! @param value 데이터
    //! @return true(성공), false(실패)
    bool Push(int value) noexcept {
        // (1) 배열의 끝인가? (더 이상 빈 공간이 없는가?)
        if (this->top == (MAX_SIZE - 1)) {
            return false;
        }

        // (2) top 인덱스 증가
        ++(this->top);

        // (3) 새 데이터 추가
        this->data[this->top] = value;

        // 성공
        return true;
    }
};

빈 공간 확인

새 데이터를 추가하기 전에 빈 공간이 존재하는 지 확인해야 합니다. MAX_SIZE - 1 연산을 통해 배열의 끝(빈 공간 없음)에 도달했는 지 확인해야 합니다. 빈 공간이 없다면 return false 등의 연산을 통해 실패임을 알립니다.
인덱스 증가

새 데이터를 바로 추가하는 것이 아니라 인덱스부터 증가시켜야 합니다. 왜냐하면 스택의 top이 마지막으로 추가된 데이터(요소)를 가리켜야하기 때문입니다.

먼저 증가시키지 않으면 기존의 데이터를 덮어쓸 위험이 있고, 초기값(-1)으로 되어 있다면 잘못된 연산을 수행하게 됩니다.
새 데이터 추가

인덱스 연산 수행 후 새 데이터를 추가합니다. this->data[++(this->top)] = value;로 한 번에 수행할 수도 있습니다.

stack_push2.cpp
#include <stack>            // for std::stack

int main(int argc, char* argv[]) {
    // (1) 스택 선언
    std::stack<int> stk;

    // (2) PUSH
    stk.push(1);

    return 0;
}

C++ 언어는 배열과 클래스를 기반으로 직접 구현하여 사용할 수 있지만, 이미 사용하기 쉽게 구현된 컨테이너가 있습니다. 바로, std::stack입니다. 다만 이 컨테이너는 배열 기반이 아닌 std::deque를 기반으로 하고 있습니다.

std::deque는 양방향 큐라고 부릅니다. 양방향 큐는 데이터의 양 끝에 접근할 수 있고 동적으로 크기가 조절된다는 특징을 갖고 있습니다. 양방향 접근이 가능한데 왜 std::stack에서 기반으로 하고 있냐면... 어차피 중간 삽입 시도를 안 하고 한 쪽 끝에만 접근하기 때문입니다. 끝에 접근하는 속도는 \(O(1)\)으로 동일하니까요.

고정된 크기를 가지면 직접 배열과 클래스를 기반으로 직접 만들면 됩니다만... 굳이 싶죠?

참고로 sta::stack 컨테이너의 push() 연산은 배열의 끝(빈 공간 존재) 여부를 확인하지 않습니다. 왜냐하면 std::deque를 기반으로 해서 그렇습니다. 동적으로 크기가 조절되는 데 굳이 확인할 필요는 없죠. 만약, 시스템의 메모리가 부족해서 더 이상 추가할 수 없다면 std::bad_alloc 예외를 발생시킵니다.

정말로 예외가 발생할까요?

err_test.cpp
#include <iostream>
#include <stack>

int main(int argc, char* argv[]) {
    std::stack<int> stk;

    try {
        while (true) {
            stk.push(1);
        }
    } catch (const std::bad_alloc& err) {
        std::cout << "메모리 부족: " << err.what() << "\n";
    }

    return 0;
}

무한 반복문 안에 push() 연산을 통해 계속 데이터를 추가합니다. 언젠가는 한계에 도달할텐데 그때 예외가 발생할겁니다.

//!는 Doxygen 주석이예요

doxygen_comment.c
//! @brief 스택
struct Stack {
    int data[MAX_SIZE];     //!< 데이터 배열
    int top;                //!< 최상단을 가리키는 인덱스
};

@brief 태그는 간략한 설명을 남길 때 사용합니다. 자세한 설명은 @details 태그를 사용하죠.

@param 태그는 매개변수^Parameter를 의미합니다. @param 다음에 매개변수의 이름을 작성하고 그 다음에 설명을 작성합니다.

//!< 주석은 멤버 변수나 열거형 값 등에 주석을 남길 때 사용합니다.

Doxygen 주석을 사용한 이유는 일일이 주석 여러 개를 작성하는 것과 내용으로 하나씩 설명하는 것보다 Doxygen 방식으로 하는 게 더 직관적이고 나아보여서 입니다. 일단 앞으로는 이걸 사용하겠습니다.

POP

POP 연산은 스택의 최상단에서 데이터를 꺼내 제거합니다. 먼저 스택이 비어있는 지 확인한 후, 비어있지 않다면 최상단의 데이터를 반환한 후 top의 값을 1 감소시킵니다. 만약 스택이 비어있다면 실패를 의미하는 값을 반환하거나 아무런 동작도 하지 않거나 예외를 발생시킬 수도 있습니다.

이 연산은 스택의 최상단에서만 작업이 이루어지기 때문에 PUSH 연산과 마찬가지로 상수 시간(\(O(1)\))입니다.

스택이 비어있는 지 확인하는 이유는 스택 언더플로우^{Stack Underflow}를 방지하기 위함입니다. PUSH 연산에서 설명했던 것처럼 고정된 크기를 갖는 배열 기반의 스택에서 문제가 됩니다. 데이터가 없는 상태에서 꺼내려 하면 잘못된 메모리 접근이나 의미없는 값을 반환하게 되죠. 연결 리스트 기반의 스택에서도 빈 상태인지 확인을 해야합니다.

프링글스 통에서 마지막 칩을 먹고 또 빈 통에 손을 넣어 확인하는 경우죠. 업보 스택이 다 정리되었는 데 굳이 또 없나 찾아보면서 나락 보내려는 것과 비슷합니다.(?)

classstd::stack

stack_pop.cpp
constexpr auto MAX_SIZE = 10;

//! @brief 스택 클래스
class Stack {
private:
    int data[MAX_SIZE];         //!< 데이터 배열
    int top;                    //!< 최상단을 가리키는 인덱스

public:
    // 생성자 생략
    // Push 메서드 생략

    //! @brief 데이터 제거 메서드
    //! @return -1 이외의 값(성공), -1(실패)
    int Pop() noexcept {
        // (1) 스택이 비어있는 지 확인
        if (this->top < 0) { return -1; }

        // (2) 최상단의 데이터 기억
        int rtn_value = this->data[this->top];

        // (3) 인덱스 감소
        --(this->top);

        return rtn_value;
    }
};

빈 공간 확인

최상단의 데이터를 반환하기 전에 스택의 공간이 비어있는 지 확인해야 합니다. 최상단을 가리키는 인덱스가 -1이면 비어있다는 뜻이기 때문에 실패를 의미하는 값을 반환합니다.
최상단의 데이터 기억

PUSH 연산과는 다르게 인덱스를 먼저 연산하지 않습니다. 왜냐하면 최상단의 데이터를 기억해야 하기 때문입니다. 그래서 별도의 변수에 최상단에 있는 값을 기억합니다.
인덱스 감소

최상단에 데이터를 기억한 후 최종적으로 top의 값을 1 감소시킵니다.

stack_pop2.cpp
#include <stack>            // for std::stack

int main(int argc, char* argv[]) {
    // (1) 스택 선언
    std::stack<int> stk;

    stk.push(1);

    // (2) POP
    if (not stk.empty()) {
        int val = stk.top();
        stk.pop();
    }

    return 0;
}

std::stack 컨테이너의 pop() 메서드는 데이터를 제거할 뿐 최상단의 데이터를 반환하지 않습니다. 최상단의 데이터를 확인하고 싶다면 제거하기 전 top() 메서드로 확인할 수 있습니다. 이 메서드는 최상단의 데이터를 반환합니다.

std::stack은 std::deque 기반이라 동적 크기를 갖지만, 비어있는 상태에서 pop()을 호출하면 오류가 발생합니다. 예외가 발생하지 않으며, 정의되지 않은 동작^{Undefined Behavior}가 발생합니다. 그래서 empty() 메서드로 먼저 확인해야 안전하게 연산을 수행할 수 있습니다.

TOP

TOP 연산은 스택의 최상단 데이터를 제거하지 않고 확인합니다. POP 연산을 수행하기 전에 어떤 데이터가 존재하는 지 확인할 때 유용합니다. 스택이 비어있으면 실패를 의미하는 값이나 예외를 던지면 됩니다. 또는 아무런 연산을 수행하지 않아도 되구요.

TOP 대신 PEEK이라는 명칭을 사용하기도 합니다. Peek은 '몰래 엿보다'라는 뜻을 가지고 있는데, 잘 들어맞죠?

최상단에 접근만하기 때문에 시간 복잡도는 상수 시간(\(O(1)\))입니다.

이 연산은 마치 프링글스의 뚜껑을 열고 맨 위에 있는 칩만 확인하는 것과 같습니다. 상태를 확인하는 거죠.

classstd::stack

stack_top.cpp
constexpr auto MAX_SIZE = 10;

//! @brief 스택 클래스
class Stack {
private:
    int data[MAX_SIZE];         //!< 데이터 배열
    int top;                    //!< 최상단을 가리키는 인덱스

public:
    // 생성자 생략
    // Push 메서드 생략
    // Pop 메서드 생략

    //! @brief 최상단 데이터 반환 메서드
    //! @param stack 스택
    //! @return -1 이외의 값(최상단 데이터), -1(실패)
    int Top() noexcept {
        if (this->top < 0) { return -1; }

        return this->data[this->top];
    }
};

최상단의 데이터를 반환하기 전 스택이 빈 상태인지 확인한 후 아니라면 최상단의 데이터를 반환하면 됩니다.

stack_top2.cpp
#include <stack>            // for std::stack

int main(int argc, char* argv[]) {
    // (1) 스택 선언
    std::stack<int> stk;

    stk.push(1);

    // (2) TOP
    if (not stk.empty()) {
        int val = stk.top();
    }

    return 0;
}

std::stack의 top() 메서드도 pop() 메서드처럼 먼저 빈 상태인지 아닌 지를 확인해야 합니다. 예외를 던지지 않기 때문에 조심해야 합니다.

EMPTY

EMPTY 연산은 스택이 비어있는 지 확인합니다. 배열 기반의 스택에선 top의 값이 -1인지 확인만 하면 됩니다. POP이나 TOP 연산을 수행하기 전에 스택 공간을 확인할 때 사용합니다.

단순 연산이기 때문에 시간 복잡도는 상수 시간(\(O(1)\))입니다.

업보 스택이 쌓여있는 지 확인하는 용도로도 좋죠.

classstd::stack

stack_empty.cpp
constexpr auto MAX_SIZE = 10;

//! @brief 스택 클래스
class Stack {
private:
    int data[MAX_SIZE];         //!< 데이터 배열
    int top;                    //!< 최상단을 가리키는 인덱스

public:
    // 생성자 생략
    // Push 메서드 생략
    // Pop 메서드 생략
    // Top 메서드 생략

    //! @brief 스택이 비어있는 지 확인하는 메서드
    //! @param stack 스택
    //! @return 비어있음(true), 오류 또는 안 비어있음(false)
    bool IsEmpty() noexcept {
        return (this->top < 0) ? true : false;
    }
};

EMPTY 연산은 보통 bool 자료형을 사용해 비어있는 지 안 비어있는 지를 표현합니다.

return (this->top < 0) ? true : false; 대신 return (this->top < 0);처럼 더 간단하게 작성해도 됩니다.

stack_empty2.cpp
#include <stack>            // for std::stack

int main(int argc, char* argv[]) {
    // (1) 스택 선언
    std::stack<int> stk;

    stk.push(1);

    // (2) EMPTY
    if (not stk.empty()) {
        // ...
    }

    return 0;
}

empty() 메서드는 스택이 비어있는 지 안 비어있는 지 bool 자료형의 값으로 반환합니다. 비어있다면 true를, 안 비어있다면 false를 반환합니다.

FULL

FULL 연산은 EMPTY 연산과는 반대로 스택의 공간이 꽉 찼는 지 확인합니다. 배열 기반의 스택에선 top의 값이 MAX_SIZE - 1인지 확인하면 됩니다. PUSH 연산을 수행하기 전 새 데이터를 추가할 수 있는 지 확인하는 용도로 사용합니다.

단순 연산이기 때문에 시간 복잡도는 상수 시간(\(O(1)\))입니다.

프링글스 통 안에 칩을 더 넣을 수 있는 지, 업보 스택을 더 쌓을 수 있는 지 등을 확인할 때 좋죠.

classstd::stack

stack_full.cpp
constexpr auto MAX_SIZE = 10;

//! @brief 스택 클래스
class Stack {
private:
    int data[MAX_SIZE];         //!< 데이터 배열
    int top;                    //!< 최상단을 가리키는 인덱스

public:
    // 생성자 생략
    // Push 메서드 생략
    // Pop 메서드 생략
    // Top 메서드 생략
    // IsEmpty 메서드 생략

    //! @brief 스택이 꽉 차있는 지 확인하는 메서드
    //! @param stack 스택
    //! @return 꽉 차있음(true), 오류 또는 꽉 차지 않음(false)
    bool IsFull() noexcept {
        return (this->top == (MAX_SIZE - 1)) ? true : false;
    }
};

return (this->top < 0) ? true : false; 대신 return (this->top < 0);처럼 더 간단하게 작성해도 됩니다.

std::stack은 std::deque 기반(동적 크기)이라 FULL 연산이 없습니다.

SIZE

SIZE 연산은 현재 스택 공간에 저장된 데이터의 수(요소의 수)를 반환합니다.

top을 기반으로 연산하기 때문에 시간 복잡도는 상수 시간(\(O(1)\))입니다.

classstd::stack

stack_size.cpp
constexpr auto MAX_SIZE = 10;

//! @brief 스택 클래스
class Stack {
private:
    int data[MAX_SIZE];         //!< 데이터 배열
    int top;                    //!< 최상단을 가리키는 인덱스

public:
    // 생성자 생략
    // Push 메서드 생략
    // Pop 메서드 생략
    // Top 메서드 생략
    // IsEmpty 메서드 생략
    // IsFull 메서드 생략

    //! @brief 데이터의 수를 반환하는 메서드
    //! @return 데이터의 수(성공), -1(실패)
    int Size() noexcept {
        return (this->top + 1);
    }
};

top에 1을 더하는 이유는 top이 -1을 초기값으로 하기 때문입니다.

데이터의 수는 0부터 시작하는 걸 원칙으로 하기 때문에 1을 더하는 겁니다.

stack_size2.cpp
#include <stack>            // for std::stack

int main(int argc, char* argv[]) {
    // (1) 스택 선언
    std::stack<int> stk;

    // (2) 데이터의 수(크기) 확인
    int size = stk.size();

    return 0;
}

std::stack은 size() 메서드를 통해 현재 스택에 저장된 데이터의 수를 확인할 수 있습니다.

CLEAR

CLEAR 또는 RESET 연산은 스택을 완전히 비우는 연산을 수행합니다. 단순히 top의 값을 -1로 되돌리는 편입니다. 배열에 있는 데이터는 굳이 건드릴 필요 없이 덮어쓰기로 처리하면 되니까요. 배열의 모든 요소의 값을 초기화할 필요는 없습니다. 불필요한 연산입니다.

top의 값만 단순히 변경하기 때문에 시간 복잡도는 \(O(1)\)입니다.

이 연산을 수행하면 당신의 업보 스택이 없어집니다.

classstd::stack

stack_clear.cpp
constexpr auto MAX_SIZE = 10;

//! @brief 스택 클래스
class Stack {
private:
    int data[MAX_SIZE];         //!< 데이터 배열
    int top;                    //!< 최상단을 가리키는 인덱스

public:
    // 생성자 생략
    // Push 메서드 생략
    // Pop 메서드 생략
    // Top 메서드 생략
    // IsEmpty 메서드 생략
    // IsFull 메서드 생략
    // Size 메서드 생략

    //! @brief 스택을 비우는 메서드
    void Clear() noexcept {
        this->top = -1;
    }
};

top에 -1을 할당하여 비어있음으로 바꿔버립니다. 배열의 데이터는 덮어쓰기 처리하면 됩니다.

stack_clear2.cpp
#include <stack>            // for std::stack

int main(int argc, char* argv[]) {
    // (1) 스택 선언
    std::stack<int> stk;

    while (not stk.empty()) {
        stk.pop();
    }
}

std::stack은 별도의 CLEAR 연산이 없습니다. 새 객체를 만들거나 위 코드 예시와 같이 수행하여 데이터를 제거하면 됩니다. 위 코드 예시처럼 할 경우 시간 복잡도는 \(O(n)\)입니다.

정리

스택은 한 쪽 끝에서 데이터를 삽입(PUSH)하고 제거(POP)할 수 있는 선형 자료구조로, 후입선출을 기반으로 합니다. 즉, 나중에 들어온 데이터가 가장 먼저 나가죠.

배열과 연결 리스트를 통해 구현되는데 보통 배열을 기반으로 합니다. 왜냐하면 구조가 단순하기 때문이죠. 물론 여유 공간으로 인한 메모리 낭비 그리고 오버플로우와 언더플로우가 발생할 수 있다는 단점이 존재하지만 적절한 크기 사용과 안전한 검사를 통해 해결할 수 있습니다.

연습문제 1

반대로 봐도 같은 문장을 회문^Palindrome이라 합니다. 공백과 구두점을 따지진 않습니다. 아래는 그 여러 개의 회문 중 일부입니다. 아래의 문장을 스택을 이용해 거꾸로 출력해보세요.

"No lemon, no melon"

해답

classstd::stack

answer1.cpp
#include <iostream>

constexpr auto MAX_SIZE = 20;           //!< 문자열 배열의 최대 크기

class Stack {
private:
    char data[MAX_SIZE];                //!< 문자열 배열
    int top;                            //!< 최상단 가리키는 인덱스

public:
    //! @brief 기본 생성자
    Stack() noexcept {
        for (auto i = 0; i < MAX_SIZE; ++i) {
            this->data[i] = '\0';
        }
        this->top = -1;
    }

    //! @brief 문자 데이터 추가 메서드
    //! @param ch 문자 데이터
    //! @return 성공(true), 실패(false)
    bool Push(char ch) noexcept {
        if (this->top == (MAX_SIZE - 1)) { return false; }

        // 인덱스 증가
        this->top += 1;

        // 데이터 추가
        this->data[this->top] = ch;

        return true;
    }

    //! @brief 문자 데이터 반환 및 제거 메서드
    //! @return 성공(문자), 실패(\0)
    char Pop() noexcept {
        if (this->top < 0) { return '\0'; }

        // 문자 데이터 기억
        char rtn_ch = this->data[this->top];

        // 인덱스 감소
        this->top -= 1;

        return rtn_ch;
    }

    //! @brief 스택이 비어있는 지 확인하는 메서드
    //! @return 비어있음(true), 안 비어있음(false)
    bool Empty() noexcept {
        return (this->top < 0);
    }
};

int main(int argc, char* argv[]) {
    // 회문
    std::string str = "No lemon, no melon";

    // 스택
    Stack stk;

    // 회문 문자 데이터 추가
    for (char ch : str) {
        stk.Push(ch);
    }

    // 역순 출력
    while (not stk.Empty()) {
        std::cout << stk.Pop();
    }                    

    return 0;
}

nolem on ,nomel oN

answer1-1.cpp
#include <iostream>
#include <stack>            // for std::stack

int main(int argc, char* argv[]) {
    // 회문
    std::string str = "No lemon, no melon";

    // 스택
    std::stack<char> stk;

    // 회문 문자 추가
    for (char ch : str) {
        stk.push(ch);
    }

    // 역순 출력
    while (not stk.empty()) {
        std::cout << stk.top();
        stk.pop();
    }

    return 0;
}

nolem on ,nomel oN

연습문제 2

이번에는 난이도가 아주 조금 높습니다.

여러분은 소괄호, 중괄호, 대괄호가 포함된 문자열 STR1과 STR2를 얻을 수 있습니다. 이 괄호들이 올바르게 짝을 지을수 있는 지 bool 형식으로 알려주세요. 이 문제는 스택을 통해 해결해주세요.

문자열의 길이는 20을 초과하지 않고, 최소 길이는 0일 수 있습니다.

아래는 테스트케이스입니다.

입력	출력	이유
`""`	`true`	괄호가 없지만 잘못된 짝이 없는 경우라 `true`
`"()"`	`true`	소괄호가 서로 짝을 이룸
`"(]"`	`false`	서로 짝을 이루지 않음
`"({[})]"`	`false`	`{` 다음에 `[`가 열렸지만, 그 다음에 `}`가 오면서 `[`와 짝이 맞지 않음
`"(()(()))"`	`true`	중첩되어 있지만 모든 괄호가 짝을 이룸
`"hello(world)"`	`true`	문자가 포함되어 있지만 소괄호는 짝을 이룸

문자열 변수	값
`STR1`	((([[{{}}]])))
`STR2`	((([[{{)}]])))

해답

classstd::stack

answer2.cpp
#include <iostream>
#include <string_view>                  // for std::string_view

constexpr auto MAX_SIZE = 20;           //!< 문자열 배열의 최대 크기

//! @brief 스택 클래스
class Stack {
private:
    char data[MAX_SIZE];                //!< 문자 배열
    int top;                            //!< 최상단을 가리키는 인덱스

public:
    //! @brief 기본 생성자
    Stack() noexcept {
        for (auto i = 0; i < MAX_SIZE; ++i) {
            this->data[i] = '\0';
        }
        this->top = -1;
    }

    //! @brief 문자 데이터 추가 함수
    //! @param ch 문자
    //! @return 성공(true), 실패(false)
    bool Push(char ch) noexcept {
        if (this->top == (MAX_SIZE - 1)) { return false; }

        // 인덱스 증가
        this->top += 1;

        // 데이터 추가
        this->data[this->top] = ch;

        return true;
    }

    //! @brief 문자 데이터 제거 함수
    //! @return 성공(true), 실패(false)
    bool Pop() noexcept {
        if (this->top < 0) { return false; }

        // 인덱스 감소
        this->top -= 1;

        return true;
    }

    //! @brief 최상단 문자 데이터 반환 함수
    //! @return 성공(문자), 실패(\0)
    char Top() noexcept {
        if (this->top < 0) { return '\0'; }

        return (this->data[this->top]);
    }

    //! @brief 스택이 비어있는 지 확인하는 함수
    //! @return 비어있음(true), 안 비어있음(false)
    bool Empty() noexcept {
        return ((this->top) < 0);
    }
};

//! @brief 짝이 맞는 지 확인하는 함수
//! @param str 문자열
//! @return 짝이 맞음(true), 짝이 안 맞음(false)
bool isMatch(std::string_view str) noexcept {
    if (str.empty()) { return true; }

    // 스택
    Stack stack;

    for (char ch : str) {
        // 여는 괄호 PUSH
        if (ch == '(' or ch == '{' or ch == '[') {
            stack.Push(ch);
        }
        // 짝이 맞는 소괄호라면 제거
        else if (ch == ')' && stack.Top() == '(') {
            stack.Pop();
        }
        // 짝이 맞는 중괄호라면 제거
        else if (ch == '}' && stack.Top() == '{') {
            stack.Pop();
        }
        // 짝이 맞는 대괄호라면 제거
        else if (ch == ']' && stack.Top() == '[') {
            stack.Pop();
        }
    }

    return stack.Empty();
}

int main(int argc, char* argv[]) {
    // STR
    std::string STR1 = "((([[{{}}]])))";
    std::string STR2 = "((([[{{)}]])))";

    std::cout << "STR1 : " << (isMatch(STR1) ? "true" : "false");

    std::cout << "\n----------\n";

    std::cout << "STR2 : " << (isMatch(STR2) ? "true" : "false");

    return 0;
}

STR1 : true ---------- STR2 : false

answer2-2.cpp
#include <iostream>
#include <stack>            // for std::stack
#include <string_view>      // for std::string_view

//! @brief 짝이 맞는 지 확인하는 함수
//! @param str 문자열
//! @return 짝이 맞음(true), 짝이 안 맞음(false)
bool isMatch(std::string_view str) noexcept {
    if (str.empty()) { return true; }

    // 스택
    std::stack<char> stack;

    for (char ch : str) {
        // 여는 괄호 PUSH
        if (ch == '(' or ch == '{' or ch == '[') {
            stack.push(ch);
        }
        // 짝이 맞는 소괄호라면 제거
        else if (ch == ')' && stack.top() == '(') {
            stack.pop();
        }
        // 짝이 맞는 중괄호라면 제거
        else if (ch == '}' && stack.top() == '{') {
            stack.pop();
        }
        // 짝이 맞는 대괄호라면 제거
        else if (ch == ']' && stack.top() == '[') {
            stack.pop();
        }
    }

    return stack.empty();
}

int main(int argc, char* argv[]) {
    // STR
    std::string STR1 = "((([[{{}}]])))";
    std::string STR2 = "((([[{{)}]])))";

    std::cout << "STR1 : " << (isMatch(STR1) ? "true" : "false");

    std::cout << "\n----------\n";

    std::cout << "STR2 : " << (isMatch(STR2) ? "true" : "false");

    return 0;
}

STR1 : true ---------- STR2 : false

isMatch() 함수에서 마지막에 empty() 함수를 반환값으로 하는 이유는 모든 괄호에 짝이 맞으면 결국 스택은 비어있게 되기 때문입니다.

반복문의 로직을 잘 보시면 여는 괄호를 만나면 무조건 추가합니다.

그리고 문자를 검사하면서 닫는 괄호가 나타나면 top() 함수를 통해 스택에 가장 마지막 데이터와 비교합니다. 서로의 괄호 짝이 맞다면 제거합니다.

이렇게 추가와 제거를 수행했는 데 스택에 데이터가 남아있다면 짝이 맞지 않다는 의미가 됩니다.