Stack

Stack

데이터의 출입구가 마지막에 위치한 컨테이너다.

때문에 마지막으로 삽입된 원소가 처음으로 나오게 강제되는 단순한 구조를 가지고 있다.(Last in First out)

 

이렇게 강제되는 구조이기 때문에 따라오는 이점들이 있다.

• 중간 접근 불가
• 순서 변경 불가

이는 단점일 수도 있지만, 장점 또한 가진다!
Random Access를 허용하지 않으므로 Random Access을 통해 의도되지 않은 데이터 조작의 실수를 원천적으로 막아준다.

또한 마지막 인덱스에서 삽입 삭제가 이루어지기 때문에 데이터의 흐름 파악과 디버깅에 효과적이라고 생각한다.

 

예전에는 그냥 정적배열을 스택처럼 사용하고 필요할 때 인덱스 접근도 가능하게끔 하는게 더 좋지 않나? 라고 생각했었다.

근데 지금와서 정리해보면 할 수 없게 하는 것 또한 강력한 기능이라고 생각이 된다.

 

스택이 역순으로 처리하는 강제성은, 중간 값이 절대 수정될 일 없다는 안정성과코더의 의도가 담긴 가이드라인? 이 되는 것 같다.

어떻게 보면 가장 마지막 원소만 보여주는 면이, 필요한 인터페이스만 보여주는 OOP의 캡슐화와 비슷하다고 생각이 든다ㅎㅎ

 

시간 복잡도

• 탐색 : 탐색을 목적으로 설계된 자료구조가 아니다.
  
  
• (마지막 원소) 접근 : O(1)
  내부에 항상 마지막 원소의 인덱스 혹은 주소를 가지고 있어 상수 시간을 가진다.
  
  
• (마지막 원소) 삭제 : O(1)
  접근 후 삭제 하면 되기 때문에 상수 시간을 가진다.
  
  
• 삽입 : O(1)
  마찬가지로 마지막 원소 접근 후 다음 위치에 삽입하면 된다.
  다만 배열로 스택이 구현되어 배열이 꽉 찼을 경우에는 불가피하게 재할당을 해야하는 경우가 온다.
  
  이 때는, 재할당 후 복사하는 과정으로 인해 O(n)으로 볼 수도 있겠으나, 가끔 재할당 하는 것 뿐인데 O(n)으로 낙인을 찍으면 스택 입장에서는 억울한 부분이 있다.
  
  그래서 가끔은 비용이 비싸지만, 전체적으로 보면 싸다! 라는 뜻의
  분할 상환 관점인 AmortizedO(1)로 말하기도 한다.
  

 

언제 사용해야 하는가

최근에 삽인 된 원소에만 접근이 가능해야한 상황은 당연할테고,

이런 구조에서 효과적인 상황중 하나가 상태를 보관하고 역순으로 복원해야 할 수 있는 상황이다.

아래와 같이 정리 가능할 수 있다.

• 상태의 일시 중단과 복구가 필요할 때
  다른 작업을 수행 후 다시 정확한 지점으로 돌아와야 하는 상황
  
  
• 모든 순서에 대해 역전이 필요할 때
  스택에서 꺼낸 순으로 출력하면 쉽게 해결할 수 있다.
  문자열 뒤집기나 실행 취소(Ctrl + z)가 해당 상황에 속한다.
  
  
• DFS
  미로 찾기 처럼 막히면 되돌아가 다른 갈림길로 이동하는 깊이 우선 탐색 방식에 최적화 되었다.

 

언제 피해야 하는가

중간 데이터에 접근하지 못할 때. 라고 하면 너무 당연하다.

좀 더 나아가서 몇 가지를 알아보면 아래와 같다.

• 탐색이 필요할 경우
  위에서 작성했듯이, 탐색은 스택에서 권장하는 기능이 아니다.
  
  
• 스택의 깊이를 예측할 수 없을 때.
  하드웨어의 스택 메모리는 보통 몇MB로 제한적으로 정해져있다.
  이 하드웨어의 스택에서 Overflow가 일어나면 재할당이고 뭐고 프로그램에서 크래시가 일어난다.
  
  
• 데이터 처리의 우선순위가 존재할 때.
  스택은 가장 늦게 온 데이터를 가장 먼저 처리하는 차별적 구조므로, 데이터 자체가 가진 중요도에 따라 처리해야 할 때는 피해야한다.
  이 때는 우선순위 큐나 힙을 이용하여 처리하는 게 좋다.

 

 

구현

구현 방법에는 배열, 리스트 2가지 방법으로 구현이 가능하다.

배열은 캐시 효율성이 높지만, 메모리 재할당이 불가피하다.

 

리스트의 경우... 단점 밖에 없다고 생각한다...

그러므로 배열을 통한 스택을 구현을 진행한다.

 

멤버 변수

    T* data;        // 실제 데이터를 담는 배열
    int capacity;  // 최대 크기
    int top;       // 가장 마지막 원소의 위치

 

메모리 재할당

// 배열이 찼을 때 메모리를 1.5배로 늘리는 함수
void resize() 
{
    int newCapacity = (capacity == 0) ? 1 : static_cast<int>(capacity * 1.5) + 1;
    T* newData = new T[newCapacity];

    // 기존 데이터 복사
    for (int i = 0; i < capacity; ++i) {
        newData[i] = data[i];
    }

    delete[] data;   // 이전 메모리 해제
    data = newData;
    capacity = newCapacity;
}

 

삽입

bool Push(const T& value)
{
    if (top >= capacity - 1)
        return false; // Stack Overflow

    data[++top] = value;
    return true;
}

 

삭제

bool Pop()
{
    if (top < 0)
        return false; // Stack Underflow

    --top;
    return true;
}

top이후의 메모리에는 접근할 수 없으므로, 실제 메모리를 지우지 않고 top의 인덱스만 내려도 된다.

접근

bool Top(T& outValue) const
{
    if (top < 0)
        return false;

    outValue = data[top];
    return true;
}

Argument에 들어온 참조변수에 값을 저장하고 성공 실패 여부를 반환한다.

 

 

 

덧붙임

위에서 구현한 reSize함수는 기존 메모리를 1.5배에서 2배로 늘린다.

근데 생각해보면 Vector에서도 메모리 재할당시 기존 메모리에서 2배를 늘리곤 한다.

근데 왜 더 큰 숫자가 아닐까?

 

그건 바로 메모리 재사용이라는 음침한 의도가 숨겨진 숫자가 1.5혹은 2이기 때문이다;;

확장 계수라는 개념이 있는데 이에 대해 다음에 알아봐야겠다