[C++] 자료구조 스택 Stack 구현하기

▣ 스택 Stack은 뭔가?

 ●  데이터를 저장하는 자료구조의 한 종류이다.

 ●  스택의 기본 연산

  ▷ push: 데이터를 저장하는 연산

  ▷pop: 마지막으로 저장한 데이터를 인출하는 연산

  ▷ LIFO : Last Input First Out

 

▣ 예제 - CharStack 클래스

 ●  CharStack 클래스

  ▷ a문자를 최대 20개까지 저장할 수 있는 스택을 나타내는 클래스

  ▷ 스택 객체는 데이터를 저장(push)하고 인출(pop)한다.

  ▷ 스택이 비었는지 가득찼는지 검사할 수 있다.

  ▷ 스택을 이용해서 입력된 단어를 역순으로 출력하는 프로그램을 만든다.

멤버함수	비고
CharStack( )	생성자
bool chkEmpty( )	스택이 비었는지 검사
bool chkFull( )	스택이 가득찼는지 검사
bool push(char)	스택에 데이터 저장
char pop( )	스택에서 데이터 꺼내기

데이터 멤버	비고
int top	가장 위에 있는 데이터 위치를 가리킨다
char buf[20]	데이터 저장 공간

 

 ●  CharStack 클래스 - CharStack.h

#ifndef CHARSTACK_H_INCLUDED
#define CHARSTACK_H_INCLUDED

class CharStack {
    enum { size = 20 }; // 스택의 크기
    int top;  // 마지막 데이터를 가리키는 포인터
    char buf[size];  //스택의 저장공간
public:
    CharStack() : top{ size } {} // 생성자
    bool chkEmpty() const {  // 스택에 데이터 없으면 true
        return top == size;
    }
    bool chkFull() const {   // 스택이 가득차면 true
        return !top;
    }
    bool push(char ch);  // 스택에 데이터 넣기
    char pop();   // 스택에서 데이터 꺼내기
};

#endif

  ▷ stack에 아무것도 없으면 top이 buf에서 buf[size]를 가리킨다.

stack에 아무것도 없을 때 20을 가리킨다

  ▷ stack이 가득차면 top이 0번 위치를 가리키게 된다. !top은 0이 아니라는 것이니 참을 반환한다.

 

stack이 꽉 찼을 때

  ▷ stack에서 데이터를 넣을 때, 데이터를 buf[size-1]부터 시작해서 차례로 위로 쌓는다.

 

 ●  CharStack 클래스 - CharStack.cpp

#include <iostream>
#include "CharStack.h"
using namespace std;

bool CharStack::push(char ch)
{
    if (chkFull()) {
        cout << "stack is full." << endl;
        return false;
    }
    buf[--top] = ch;  // stack에 공간 있으면 저장한다.
    return true;
}

char CharStack::pop()
{
    if (chkEmpty()) {
        cout << " there is no data in stack." << endl;
        return 0;
    }
    return buf[top++]; // top 위치의 데이터 반환
}

  ▷ CharStack::push를 통해 top의 위치에서 1개 감소된 위치의 버프에 ch 값을 저장한다.

  ▷ CharStack::pop을 통해 가장 위에 있는 값이 반환되고, top의 위치가 1개 증가된 위치의 버프로 이동한다.

 

 ●  CharStack 클래스 - CSMain.cpp

#include <iostream>
#include "CharStack.h"
using namespace std;

int main()
{
    CharStack chStack; // 20개 문자를 저장할 수 있는 stack 생성
    char str[20];
    
    cout << " Enter any word : ";
    cin >> str;
    
    char* pt = str;  // 포인터로 문자열 시작 위치를 가리킨다.
    while (*pt)   // 문자열의 끝이 아니면 반복한다.
        chStack.push(*(pt++));  // stack에 문자 넣기
    
    cout << " Print backwards : ";
    while (!chStack.chkEmpty())  // stack이 비어있지 않으면 반복
        cout << chStack.pop();  // stack에서 인출한 문자를 출력
    cout << endl;
    return 0;
}

  ▷ C문자열 끝에 \0 (null)을 만나면 문자열이 끝났다는 걸 알 수 있다.

  ▷ while (*pt)는 *pt 가 null 이 아닌 동안 반복한다는 의미이다.

  ▷ *(pt++)은 pt가 가리키는 문자에 1을 더한 다음 문자의 값을 가리키게 한다. (그 다음 반복부터)

  ▷ stack에서 buf의 위치 숫자를 다 찼을 때 0이 되게 하든, 20이 되게 하든 그건 개발자 마음이지만, 통상적으론 위와 같이 구성한다.

 

 ●  실행결과