c++ stack 스택 구현

* 본문은 <C++로 구현하는 자료구조와 알고리즘>(범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다.

 

1. STL을 사용할 경우

스택 객체를 선언하기 위해선 먼저 stack이라 불리는 정의 파일을 먼저 포함해야 한다. STL벡터 클래스와 마찬가지로 스택 클래스도 std네임스페이스에 포함되기 때문에, "std::stack"으로 사용하던지 using 문을 사용해야 한다. 스택 클래스는 개별 원소의 클래스를 사용할 수 있는 템플릿으로 만들어졌다.

#include <stack>
using std::stack
stack<int> myStack;

스택에 포함된 원소의 타입을 스택의 기본 타입이라 한다. STL 스택 역시 STL 벡터처럼 새 원소가 삽입되면 동적으로 자신의 크기를 변경한다. STL 스택 클래스는 size(), empty(), push(e), pop(), top() 인터페이스를 지원한다. 빈 스택에 대해선 top, pop 연산의 결과가 정의되어 있지 않아 오류가 발생하지 않는다. 오류가 발생되지 않더라도 프로그램이 중단될 가능성이 높다. 따라서 접근할 때 조심해야 한다.

 

 

 

2. 배열을 기반으로 구현

template <typename E>
class ArrayStack {
    enum { DEF_CAPACITY = 100 }; //default stack capacity
public:
    ArrayStack(int cap = DEF_CAPACITY); //constructor
    int size() const;
    bool empty() const;
    const E& top() const throw(StackEmpty);
    void push(const E& e) throw(StackFull);
    void pop() throw(StackEmpty);
private:
    E* S; //스택 원소들의 배열
    int capacity;
    int t; //스택 최상위 원소의 인덱
};


template <typename E> ArrayStack<E>::ArrayStack(int cap)
        : S(new E[cap]), capacity(cap), t(-1) { } //디폴트 용량을 갖는 생성자

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

template <typename E> int ArrayStack<E>::empty() const
    { return (t<0); }

template <typename E>
const E& ArrayStack<E>::top() const throw(StackEmpty) {
    if (empty()) throw StackEmpty("Top of empty stack");
}

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

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


//example code
ArrayStack<int> A;
A.push(7);
A.push(13);
cout << A.top() << endl;
A.push(9);
cout << A.top() << endl;
cout << A.top() << endl; A.pop();
ArrayStack<string> B(10);
B.push("Bob");
B.push("Alice");
cout << B.top() << endl; B.pop();
B.push("Eve");

생성자에서 디폴트값이 사용되었다. 아무 입력 파라미터 없을 때 디폴트값으로 설정하는거! 파이썬에서 나왔던 것 말이다.

디폴트 값을 정의하기 위해 enumeration이 사용되었으며, 이는 C++ 클래스에서 정수형 상수값을 갖는 심볼을 정의하는 가장 간단한 방법이다.

const가 붙은 메서드들은 이 메서드에서 함수값을 결코 변경하지 않음을 의미한다. 레퍼런스 값을 파라미터로 받는다고 해도 말이다.

 

 

3. 일반 링크드 리스트로 구현

typedef string Elem;
class LinkedStack {
public:
    LinkedStack();
    int size() const;
    bool empty() const;
    const Elem& top() const throw(StackEmpty);
    void push(const Elem& e);
    void pop() throw(StackEmpty);
private:
    SLinkedList<Elem> S;
    int n;
};


LinkedStack::LinkedStack()
    : S(), n(0) { }

int LinkedStack::size() const
    { return n; }

bool LinkedStack::empty() const
    { return n==0; }

const Elem& LinkedStack::top() const throw(StackEmpty) {
    if (empty()) throw StackEmpty("Top of empty stack");
    return S.front();
}

void LinkedStack::push(const Elem& e) {
    ++n;
    S.addFront(e);
}

void LinkedStack::pop() throw(StackEmpty) {
    if (empty()) throw StackEmpty("Pop from empty stack");
    --n;
    S.removeFront();
}

이 코드에서 이전에 구현했던 SLinkedList를 사용한다. SLinkedList 클래스는 멤버 함수 size를 제공하지 않기 때문에, 현재 원소의 개수를 멤버 변수 n에 저장한다. 소멸자는 따로 만들지 않고 SLinkedList의 소멸자를 이용하여 링크드 리스트 S의 할당을 해제한다.

SLinkedList의 head와 tail 중 어느 쪽을 스택의 최상위로 할 것인가? SLinkedList는 head에서만 상수 시간에 원소를 삽입 삭제할 수 있기 때문에, 당연히 head를 선택해야 한다. 따라서 멤버 함수 top은 S.front()를 반환한다.

 

 

4. 스택을 이용해 벡터 역순화

벡터 원소들을 역순화하는데 스택을 이용할 수 있다. 벡터의 모든 원소를 하나의 스택에 push한 후 원소들을 스택으로부터 하나씩 pop하여 벡터에 다시 넣는 개념이다.

void reverse(vector<E>& V) {
    ArrayStack<E> S(V.size());
    for (int i=0; i<V.size(); i++)
        S.push(V[i]);
    for (int i=0; i<V.size(); i++) {
        V[i] = S.top(); S.pop();
    }
}

 

 

5. HTML문서의 태그 맞추는 프로그램

여는 태그를 만나면 모두 push하고, 닫는 태그를 만나면 스택에서 pop하여 두 태그가 서로 맞는지 확인한다. 간단히 하기 위해 모든 태그는 문법적으로 맞는 형식을 가진다고 가정한다.

#include <string>
vector<string> getHtmlTags() {
    vector<string> tags;
    while (cin) { // 파일 끝까지 읽는다
        string line;
        getline(cin, line); // 텍스트의 한 줄을 입력한다
        int pos = 0; // 현재의 스캔 위치
        int ts = line.find("<", pos); // 태그의 시작
        while (ts != string::npos) { // 문자열 끝까지 반복한다
            int te = line.find(">",ts+1); // 태그 끝을 찾는다
            tags.push_back(line.substr(ts, te-ts+1)); // 태그를 벡터에 추가
            pos = te+1; // 위치를 전진
            ts = line.find("<",pos);
        }
    }
    return tags;
}

- string의 getline 함수: 끝에 지정 문자를 정해주지 않으면 개행 문자를 만나기 전까지 입력받는다. 와... 입력받는 방식이 엄청 맘에 든다! 내가 자바에서 배우지 못한걸 씨플플에서 알아가고 있다!

참고: https://giantpark197cm.tistory.com/142

- string::npos? : 찾는 문자가 없는 경우에 반환하는 것이라고 한다.

참고: https://blankspace-dev.tistory.com/314

- find 메서드의  두번째 인자는 찾기 시작하는 문자열 상의 위치(인덱스)를 말한다.

참고: https://blockdmask.tistory.com/338

->위 자료 엄청 좋음! C++의 string 클래스 전반에 대해 다루고 있어서!!!

 

아래는 태그를 맞추는 코드다.

bool isHtmlMatched(const vector<string>& tags) {
    LinkedStack S; // 여는 태그를 저장하는 스택
    typedef vector<string>::const_iterator Iter;

    for (Iter p = tags.begin(); p!=tags.end(); ++p) {
        if (p->at(1)!='/') // 여는 태그인가?
            S.push(*p);
        else { // 그렇지 않으면 닫는 태그
            if (S.empty()) return false; // 짝이 없으면 실패
            string open = S.top().substr(1); // '<'를 제외한 여는 태그
            string close = p->substr(2); // '</'를 제외한 닫는 태그
            if (open.compare(close) != 0) return false; // 맞지 않음
            else S.pop();
        }
    }
    if (S.empty()) return true;
    else return false;
}

이 코드에 대해 모르는 부분들 역시 내가 엄청 좋다고 바로 위에 첨부해둔 링크에 모든 설명이 나온다.

 

아래는 메인 실행 코드다.

int main() {
    if (isHtmlMatched(getHtmlTags()))
        cout << "The input file is a matched HTML document" << endl;
    else
        cout << "The input file is not a matched HTML document" << endl;
}