C++로 구현하는 자료구조!!!스택 편@@

강력한 언어, c++로 구현하는 자료구조

C++로 구현하는 Stack 자료구조

제 글을 보시게 되면, C 혹은 Python으로 구현한 스택자료구조를 보셨을 수도 있겠네요~ 물론 못 보셨다면 아래 링크 달아드릴테니 들어가셔서 간단하게 해보시는걸 추천드립니다~!

 

hazarddev.tistory.com/29

자료구조[1]-STACK(python)

hazarddev.tistory.com/17

STACK(스택)이 뭔가요?[1]

 

사실 어떤 언어로든 똑같은 자료구조를 만들 수 있어야 어느정도 언어에 대한 이해가 생겼다 라고 볼 수 있습니다! 문법은 달라도 사실 흐름 자체는 거의 비슷하다 볼 수 있으니까요~ 그럼 각설하고 클래스로 구현하는 스택 자료구조 부터 설명을 시작하도록 하겠습니다!

 

1. 클래스로 구현하는 스택 자료구조!

우선 C++로 스택을 구현하는 방법은 뭐 너무 많지만 대표적으로 클래스로 구현하는 방법 그리고 STL<Standard Template Library>라고 하는 강력한 자료구조, 알고리즘 등을 모아놓은 라이브러리입니다. 앞으로 포스팅하는 자료구조들은 클래스로 구현하는 방법과 STL을 이용한 방법 총 두가지로 나누어 설명할 예정입니다!

1.1 노드부 선언

클래스로 노드부를 선언해주어야 합니다. 그 이유에는 스택이라는 자료구조안에 들어가는 데이터가 객체여야 하기 때문인데요, 그럼 간단하게 생각해보았을 때 노드안에는 값을 담는 변수와, 그 다음 객체를 가리키는 노드 포인터가 들어가 있어야겠죠?

current value

next ->

nextNode value

next -> ...

위와 같은 방식으로 구현할 예정입니다. 우선 코드를 보시겠습니다!

 

#include <iostream>
#include <string>
 
class Stack;
class Node{
    friend class Stack;
    private:
        int val;
        Node *next;
        Node(int value = 0, Node *newNode = nullptr)
        {val = value; next = newNode;}
};

 

우선 아래 스택 객체를 전방선언해서 노드 클래스의 친구 클래스로 만들어, 스택 객체에서 노드 객체를 액세스할 수 있게 해야합니다. 또한 private한정자 내부에 선언된 데이터(정수)와 다음 노드를 가리키는 next노드 포인터 변수, 그리고 노드 객체를 초기화하는 생성자로 구성되어 있습니다! 혹시 C++가 익숙하지 못하신 분은 댓글 달아주시면 도와드리도록 하겠습니다!!

1-2.스택객체 선언

 

class Stack{
    private:
        Node *top;
    public:
        explicit Stack(){top = nullptr;}
        bool isEmpty()const;
        void pushStack(const int val);
        int *popStack(int &val);
        void show()const;
};
 
bool Stack::isEmpty() const{
    return top == nullptr;
}
 
void Stack::pushStack(const int val){
    top = new Node(val, top);
}
 
int *Stack::popStack(int &val){
    if(!isEmpty()) {
        std::cout << "Empty Stack" << std::endl;
        return 0;
    }
    Node *x = top;
    val = top -> val;
    top = x -> next;
    delete x;
    return &val;
}
 
void Stack::show() const{
    Node *temp = top;
    while (temp != nullptr){
        std::cout << temp -> val << std::endl;
        temp = temp -> next;
    }
}
 

int
main()
{
    Stack *stack = new Stack();
    stack -> pushStack(1);
    stack -> pushStack(2);
    stack -> pushStack(3);
    stack -> pushStack(4);
    stack -> pushStack(5);
    stack -> show();
}
 
RESULT >
5
4
3
2
1

 

main함수에서 스택객체를 생성해 값을 넣은 다음 출력하는 프로그램입니다. 스택의 완성이죠! 출력은 아래대로 5,4,3,2,1 이렇게 정상적으로 출력된 것을 확인할 수 있으며, 여러분들도 코드를 작성해보시는 것을 추천드립니다!

 

2. STL로 구현하는 스택!

사실 이건 누군가 실력이 아주 좋은 누군가가 미리 정의한 자료구조를 사용하는 것이기 때문에 사용하기 너무 간단하고 쉽습니다. 이것은 코드로 설명을 하도록 하겠습니다!!

 

int
main()
{
    std::stack<int> newStack; // <---- <>사이에 스택에 들어갈 데이터의 타입을 선언
    newStack.push(1); // <----- push() 함수를 이용해 삽입
    newStack.push(2);
    newStack.push(3);
    newStack.push(4);
    newStack.push(5);
    while(!newStack.empty()){ // <---- empty() 내장함수를 사용해 스택객체가 비어있는 상태가 될 때까지 반복
        int temp = newStack.top(); // <----- top()내장함수를 통해 스택 객체의 최상단 객체를 가져옴
        std::cout << temp << std::endl; 
        newStack.pop();//<---- pop() 내장함수를 통해 제거
    }
    return 0;
}
 
RESULT >
5
4
3
2
1

위 코드에 설명만 봐도 사용하기 쉽기 때문에 코드 내부에 주석으로 설명을 덧붙였습니다. 꼭 실습을 하셔야합니다!!! 한번 작성해보는 것은 백번 눈으로 보는것보다 좋으니까요ㅎㅎㅎ

 

C++을 이용해서 스택을 구현하는 방법을 알아보았는데요, 다음 글에서는 큐 구현하는 법에 대해서 글을 올릴 예정입니다!!!

 

hazarddev.tistory.com/38

C++로 구현하는 자료구조!!!큐(Queue)편@@@

 

댓글로 피드백, 문의 환영합니다