[ 자료구조 ] 스택(Stack)

스택 (Stack)

스택은 후입선출(LIFO: Last-In First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조다. 스택을 직역하면 '무더기'라는 뜻인데 말그대로 무더기처럼 쌓아 올리고, 하나씩 제거한다. 여기서 데이터 삽입을 push라 하고, 데이터 삭제를 pop이라 한다. 

굉장히 간단한 자료구조다. 스택은 후입선출 구조이기 때문에 가장 마지막에 들어온 데이터가 가장 먼저 나간다. 반대로 가장 먼저 들어온 데이터는 가장 마지막으로 나간다. 위 그림만 봐도 쉽게 이해할 수 있을 것이다. 이러한 자료구조가 왜 필요할까? 어떻게 활용할 수 있을까? 스택의 활용 예시로 두 가지만 살펴보자. 

 

먼저 인터넷 브라우저에서 '뒤로가기' 기능을 예로 들 수 있다. 구현할 수 있는 방법은 많겠지만 스택을 사용하면 아주 간단하게 구현할 수 있다. 그냥 새로운 사이트를 방문할 때마다 사이트의 주소를 스텍에 push 해주고, 사용자가 '뒤로가기' 버튼을 누르면 스택의 pop을 통해 이전에 방문했던 사이트로 되돌아가면 끝이다.

 

문서 편집기에서 '되돌리기' 기능도 마찬가지다. word, visual studio, power point 등 편집 기능이 있는 모든 응용 프로그램에는 '되돌리기' 기능이 있다. 원리는 인터넷 브라우저의 '뒤로가기' 기능과 완전히 동일하다. 

스택 구현

이제 스택을 구현해보자. 스택의 기본적인 연산은 아래와 같다. 

push(e) : 객체 e를 스택의 최상위에 삽입.
pop() : 스택의 top에 있는 객체를 스택에서 제거. 만약 빈 스택이라면 오류를 발생시킨다.
top() : 스택의 최상위 원소의 레퍼런스를 반환한다. 만약 빈 스택이라면 오류를 발생시킨다. 
size() : 스택 내의 객체의 개수 반환.
isEmpty() : 스택이 비어있는지 여부를 반환.

 

우리의 목표는 위 기능들을 구현하는 것이다. 스택을 구현하는 방법으로 크게 배열을 사용하는 방법과 연결 리스트를 사용하는 방법이 있다. 두 가지 방법으로 위 기능들을 구현해보자. 이번에는 예외처리까지 고려한다.

스택 구현 : 배열 기반

1. 구조

배열로 후입선출을 구현하려면 어떻게 해야 할까? 인덱스를 사용하면 크게 어렵지 않다. 먼저 top을 가리키는 인덱스를 t라는 변수에 저장한다. 아래 그림과 같이 push 할때는 인덱스에 1을 더한 값에 데이터를 넣어주면 되고, pop 할때는 인덱스에 1을 빼주면 된다. 

데이터 삭제가 정말로 메모리에서 지워버리는게 아니라는 점에 유의하자. 배열은 컴파일 타임에 크기가 정해지기 때문에 메모리 반납이 무의미하다. 따라서 여기서 데이터 삭제는 '무시'에 좀 더 가깝다. 값을 무시해버리면 이를 데이터 삭제로 간주하는 것이다. 배열의 큰 장점은 '속도'에 있다. 곧 모든 기능을 구현해보면 알겠지만 각 멤버 함수의 시간 복잡도는 O(1)로 매우 빠르다. 

2. 클래스 정의

예외처리 클래스

class RuntimeException{
private:
    string errorMsg;
public:
    RuntimeException(const string & err) : errorMsg(err) {}
    virtual string what() const { return errorMsg; } // 가상함수 지정
};

// 스택이 비었을때
class StackEmpty: public RuntimeException{
public:
    StackEmpty(const string& err) : RuntimeException(err) {}
};

// 스택이 가득 찼을때
class StackFull: public RuntimeException{
public:
    StackFull(const string& err) : RuntimeException(err) {}
};

 

ArrayStack 클래스

template <typename E>
class ArrayStack{
public:
    ArrayStack(int cap = 100); // 생성자
    ~ArrayStack(); // 소멸자
    int size() const; // 스택에 저장된 데이터 개수
    bool empty() const; // 스택이 비었는지?
    const E& top() const; // 스택의 top 원소
    void push(const E& e); // e를 스택에 push
    void pop(); // pop
private:
    E* S; // 배열 
    int capacity; // 용량
    int t; // top의 인덱스
};

3. 구현

// 생성자
template <typename E> ArrayStack<E>::ArrayStack(int cap)
    : S(new E[cap]), capacity(cap), t(-1) {}

// 소멸자
template <typename E> ArrayStack<E>::~ArrayStack(){
    delete[] S;
}

// 스택에 저장된 데이터 개수
template <typename E> int ArrayStack<E>::size() const{
    return (t + 1);
}

// 스택이 비었는지?
template <typename E> bool ArrayStack<E>::empty() const{
    return (t < 0);
}

// 스택의 top 원소
template <typename E>
const E& ArrayStack<E>::top() const{
    if(empty()) throw StackEmpty("Top of empty stack");
    return S[t];
}

// e를 스택에 push
template <typename E>
void ArrayStack<E>::push(const E& e){
    if(size() == capacity) throw StackFull("Push to full stack");
    S[++t] = e;
}

// pop
template <typename E>
void ArrayStack<E>::pop(){
    if(empty()) throw StackEmpty("Pop from emtpy stack");
    --t;
}

 

크게 어려운 부분은 없으므로 설명은 생략한다. 각 멤버 함수를 읽어보면 어렵지 않게 이해할 수 있을 것이다. 구현을 완료했으므로 메인 함수에서 테스트를 해보자! try, catch문으로 감싸주면 오류 발생시 적절한 문구가 출력될 것이다. 아래는 테스트 코드 예시다. 

 

int main(){
    try{
        ArrayStack<int> A(3);
        A.pop(); // 오류: 빈 스택에 pop
        cout << A.top() << endl;
    } catch(StackFull& e){
        cout << e.what() << endl;
    } catch(StackEmpty& e){
        cout << e.what() << endl;
    }
    
    cout << "Done" << endl;
    
    return 0;
}

스택 구현 : 연결 리스트 기반

1. 구조

단일 연결 리스트를 사용하면 스택을 굉장히 쉽게 구현할 수 있다. 스택은 단일 연결 리스트에 포함된다고 봐도 된다. 왜냐하면 단일 연결 리스트에서 head 포인터를 top으로 이름만 바꾸면 스택이 되기 때문이다. 스택의 기능을 구현할 때도 단일 연결 리스트의 멤버 함수가 많이 사용된다. 데이터 추가(push) 및 삭제(pop) 할 때의 구조는 아래와 같다. 

 

데이터 추가(push)

 

데이터 삭제(pop)

2. 클래스 정의

(예외처리 클래스는 배열 기반과 동일하므로 생략)

 

LinkedStack 클래스

template <typename E>
class LinkedStack{
public:
    LinkedStack(); // 생성자
    // 소멸자는 SLinkedList의 소멸자 사용
    int size() const; // 스택 내 데이터 개수
    bool empty() const; // 스택이 비었는지?
    const E& top() const; // 스택의 top 원소
    void push(const E& e); // e를 스택에 push
    void pop(); // pop
private:
    SLinkedList<E> S; // 연결 리스트 생성
    int n; // 데이터 개수
};

 

SLinkedList에 대한 코드는 여기를 참고하길 바란다. 멤버 변수로 n을 따로 둔 이유는 SLinkedList에 크기를 반환하는 함수가 없기 때문이다. 또한 소멸자는 SLinkedList의 소멸자를 사용하므로 LinkedStack 클래스에서 따로 정의해줄 필요가 없다. 할당 해제가 되는지 확인하고 싶으면 SLinkedList의 소멸자에 "Destructed..."와 같은 문자열을 출력하도록 한 뒤에 메인 함수에서 테스트를 해보면 된다. 

3. 구현

// 생성자
template <typename E>
LinkedStack<E>::LinkedStack() : S(), n(0) {}

// 스택 내 데이터 개수
template <typename E>
int LinkedStack<E>::size() const{
    return n;
}

// 스택이 비었는지?
template <typename E>
bool LinkedStack<E>::empty() const{
    return n == 0;
}

// 스택의 top 원소
template <typename E>
const E& LinkedStack<E>::top() const{
    if(empty()) throw StackEmpty("Top of empty stack");
    return S.front();
}

// e를 스택에 push
template <typename E>
void LinkedStack<E>::push(const E& e){
    ++n;
    S.addFront(e);
}

// pop
template <typename E>
void LinkedStack<E>::pop(){
    if(empty()) throw StackEmpty("Pop from empty stack");
    --n;
    S.removeFront();
}

 

크게 어려운 부분은 없으므로 설명은 생략한다. 구현을 완료했으므로 메인 함수에서 테스트를 해보자. 아래는 테스트 코드 예시다. 

 

int main(){
    try{
        LinkedStack<int> A;
        A.push(2);
        cout << A.top() << endl;
        A.pop();
        A.pop(); // 오류: 빈 스택에 pop
    } catch(StackFull& e){
        cout << e.what() << endl;
    } catch(StackEmpty& e){
        cout << e.what() << endl;
    }
    
    cout << "Done" << endl;
    
    return 0;
}

 

 

여기까지 스택을 마무리한다. 큐(queue)로 다시 돌아오도록 하겠다.