[Data Structures] 챕터4. 스택(Stack)

스택

---

• 할 일을 쌓아둔다.
• LIFO(Last in First Out), 후입선출

용도

• 편집 소프트웨어의 Undo/Redo 기능 구현
• 연산자 우선순위를 고려한 수식의 계산 예) 1 + 2 * 3 에서 + 연산을 미뤄두고 *를 먼저 수행
• 함수 실행할 때 스택에 프레임 쌓기 - 앞에서 재귀호출 가시화 도구 가시화에서 봤듯이 나중에 호출된 함수를 끝낸 후 그 전에 호출된 함수로 돌아갈 수 있습니다.

 

구현

int Size() const
{
    return top_ + 1; // top_이 index를 가리키므로 +1을 해주자
}

 

// Insert item into the TOP of the stack
void Push(const T& item)
{
    if (capacity_ == top_+1) // capacity는 top + 1 index를 포함해야함
        Resize(capacity_ * 2);
	
    ++top_;
    stack_[top_] = item;
}

 

Pop

T자료형이 내부에서 동적할당 메모리를 사용한다면 소멸자를 호출해주자.

void Pop()
{
    assert(!IsEmpty());
    
    stack_[top_].~T(); // T 자료형 내부에서 동적할당 메모리를 사용할 경우
    top_--;

    // 메모리를 아껴야 될 경우 Resize로 크기를 줄이자
}

 

미로

---

struct Pos
{
    int row;
    int col;

    friend ostream& operator<<(ostream& os, const Pos& pos)
    {
        cout << "(" << pos.row << ", " << pos.col << ")" << flush;
        return os;
    }
};

참고 1) 9.2 입출력 연산자 오버로딩하기 https://hoplite.tistory.com/100 

1. 연산자 오버로딩은 2개의 Parameter가 필요하다
2. 멤버 함수로 정의할 경우 1개의 Parameter가 필요하다
3. ostream의 멤버함수를 정의할 수 없으므로 외부 함수로 2개의 Parameter를 호출하는 형태로 함수를 정의한다.
4. 이 때 외부에서 구현하면 private 멤버변수에 접근할 수 없다.
5. 따라서 class 내부에서 정의 + friend keyword를 활용하여 해당 함수에서 멤버 변수의 접근권한을 준다.

 

참고 2) constexpr Keyword in C++17 https://hoplite.tistory.com/86

constexpr은 compile time에 초기화되는 변수이다.아래와 같이 정적 배열을 정의하는데 사용할 수 있다.

constexpr int kNumRows = 2;
constexpr int kNumCols = 2;

char maze[kNumRows][kNumCols] = {{0,1},{2,3};

 

참고 3) 구조체의 생성자와 임시 구조체

Pos start = { 1, 1 }; // i = 1, j = 1  시작 지점
//Pos start;
//start.row = 1;
//start.col = 1;

s.Push(start); // s.Push({1, 1});

 

구현

재귀호출

int RecurMaze(Pos p)
{
    const char mark = maze[p.row][p.col];
    cout << p << endl;

    if (mark == 'G')
    {
        cout << "Found!" << endl;
        return 1;
    }
    
    if (mark == '1' || mark == 'X')
        return 0;
    
    maze[p.row][p.col] = 'X';

    if (RecurMaze({p.row, p.col-1})) return 1;
    if (RecurMaze({p.row, p.col+1})) return 1;
    if (RecurMaze({p.row+1, p.col})) return 1;
    if (RecurMaze({p.row-1, p.col})) return 1;
}

문자 값 '1'으로 둘러쌓인 배열이므로 사용할 수 없는 index에 접근하는지 확인할 필요는 없다.

/*L*/if (0 < p.col - 1)
{
    if (RecurMaze({p.row, p.col-1}) == 1)
        return 1;
}

 

stack

재귀 호출은 자기함수를 호출하는 순서와 순회하는 순서가 동일하다.

stack을 사용하면 push하는 순서와 순회하는 순서가 반대가 된다.

void StackMaze()
{
    Stack<Pos> s;
    s.Push({1, 1});// i = 1, j = 1  시작 지점

    // s.Print(); // 디버깅에 사용 가능
    while (!s.IsEmpty())
    {
        Pos p = s.Top();
        s.Pop();

        cout << p << " "; // 디버깅 출력

        const char mark = maze[p.row][p.col];

        if (mark == 'G')
        {
            cout << "Found!" << endl;
            break;
        }

        if (mark == 'X' || mark == '1')
            continue;
        
        maze[p.row][p.col] = 'X';

        // 재귀와 다르게 마지막 Push부터 순회함
        s.Push({ p.row, p.col-1 });
        s.Push({ p.row, p.col+1 });
        s.Push({ p.row+1, p.col });
        s.Push({ p.row-1, p.col });
    }
}

 

의미

재귀호출와 Stack을 사용한 구현은 유사하다.

 

하노이의 탑

---

N개의 Disk를 옮기려면

1. N-1개의 Disk를 임시 위치로 옮긴다.
2. 가장 아래에 있는 N 번째 Disk를 목표 위치로 옮긴다.
3. 임시 위치에 있는 N-1개의 Disk를 목표위치로 옮긴다.

이 때 N-1개의 Disk를 옮기는 일은 다시 위와 같이 처리할 수 있으므로 재귀호출로 문제를 풀 수 있다.

https://github.com/HongLabInc/HongLabDataStructures/blob/main/Ex0403_TowerOfHanoi/Ex0403_TowerOfHanoi.cpp

void RecurMoveDisks(int n, int from, int temp, int to)
{
    if (n == 0)
        return;

    // stack the rest on temp location
    RecurMoveDisks(n-1, from, to, temp);

    // Move bottom disk to target location
    MoveDisk(from, to);

    // move the rest on the temp to target location
    RecurMoveDisks(n - 1, temp, from, to);
}