자료구조 : 스택(Stack) 이해하고, 구현하기! C++

Stack 1분만에 이해하기

스택(Stack)은  후입선출 (Last In First Out, LIFO) 자료구조이다.

즉, 제일 늦게 들어온 데이터가 제일 빨리 나간다는 것이다.

스택에 데이터를 넣는 행동은 Push(밀어 넣는다), 꺼내는 행동은 Pop이라고 부른다.

그리고 스택의 가장 위 데이터를 가리키는 포인터를 top 이라고 하겠다.

Stack은 어디에 사용되고 있을까?

자료구조를 배우면서 나는 항상 "왜 이걸 만들까..."라는 생각이 제일 먼저 들었다.

배울때 스택이 유용하고 널리 쓰인다는 걸 알 수 있다면 좋겠다고 생각해서 이 섹션을 덧붙였다!

워드 프로세서를 이용하다가 되돌리기 버튼을 누르면 이전에 했던 명령이 취소된다.

이것은 워드 프로세서가 프로그램의 스택에 명령을 하나 하나 추가하다가,

사용자가 되돌리기 버튼을 누르면 스택을 Pop 해서 상태를 되돌리는 것이라고 이해할 수 있다.

이 밖에도 최근 본 글이나, 문자를 거꾸로 출력한다든지하는 상황에도 응용될 수 있다.

Stack의 추상 자료형 (Abstract Data Type)

그러면 스택의 ADT를 먼저 알아보도록 하자.

구현 코드가 C++로 되어있기 때문에 ADT도 C++ 스타일로 적겠다.

다음 ADT를 가지고 여러분이 직접 코드를 작성해보고 테스트 해 보면 좋을 것이다!

몇몇 함수와 변수들을 추가해서 구현해도 좋다.

class Stack {

public:

Stack(); // 생성자

~Stack(); // 소멸자

void Pop(); // 스택에 있는 데이터 꺼내기

void Push(const T&); // 스택에 데이터 넣기

T& Top(); // 스택 제일 위의 자료 얻기

bool IsEmpty(); // 스택이 비어있는지 검사

private:

int top = -1;

}

Stack의 구현 (C++)

간단하게 스택을 구현 해 본 코드다.

메인 함수에서는 char형 데이터를 담는 스택을 만들어서

스택을 만들고, 삭제하고, Push, Pop, Top 같은 일을 할 수 있도록 하고 있다.

보기가 어려울 수도 있으니 GitHub에도 업로드 해 놓았다.

주소 https://github.com/lx5475/Basic-Stack-in-Cpp

/*
Basic Stack in C++
@author: PARK JI EUN
@date: 2016.12.19
*/
#include <iostream>
 
using namespace std;
 
template <typename T>
class Stack {
    friend ostream& operator<<(ostream& os, Stack stack) {
        if (!stack.IsEmpty()) {
            for (int i = stack.top; i > -1; i--) {
                os << "\t" << stack.stack[i] << endl;
            }
        }
        return os;
    };
public:
    Stack();
    Stack(int);
    void Pop(); // Pop stack
    void Push(const T&); // Push data to stack
    T& Top(); // Get the data top of stack
    bool IsEmpty(); // Check the stack is empty or not
    bool IsFull(); // Check the stack is full or not
private:
    T* stack;
    int top = -1; // points nothing
    int capacity;
};
 
/* Stack Constructor */
template <typename T>
Stack<T>::Stack() {
    capacity = 10;
    stack = new T[capacity];
}
 
template <typename T>
Stack<T>::Stack(int _capacity) {
    capacity = _capacity;
    stack = new T[capacity];
}
 
template <typename T>
void Stack<T>::Pop() {
    if (IsEmpty()) {
        return;
    }
    else {
        top--;
    }
}
 
template <typename T>
void Stack<T>::Push(const T& data) {
    if (IsFull()) {
        return;
    }
    else {
        stack[++top] = data;
    }
}
 
template <typename T>
T& Stack<T>::Top() {
    T result = NULL;
    if (!IsEmpty()) {
        result = stack[top];
    }
    return result;
}
 
template <typename T>
bool Stack<T>::IsEmpty() {
    bool isEmpty = false;
    if (top < 0) {
        isEmpty = true;
        cout << "\tStack is Empty." << endl;
    }
    return isEmpty;
}
 
template <typename T>
bool Stack<T>::IsFull() {
    bool isFull = false;
    if (top == capacity - 1) {
        isFull = true;
        cout << "\tStack is Full." << endl;
    }
    return isFull;
}
 
Stack<char> CreateStack(int _capacity) {
    Stack<char> stack(_capacity);
    return stack;
}
 
bool IsValid(int value) {
    bool isValid = false;
    // Capacity should be a positive number.
    if (value > 0 && value < UINT_MAX) {
        isValid = true;
    }
    return isValid;
}
 
int main(void)
{
    int select = 0;
    int value;
    char data;
    bool stackExists = false;
    Stack<char> stack = NULL;
    while (true)
    {
        cout << "\n- Select Command -" << endl;
        cout << "1: Create Stack, 2: Delete Stack, 3: Push, 
                    4: Pop, 5: Top, 6:Display, 0: Quit\n\t>> ";
        cin >> select;
        switch (select)
        {
        case 1:
            do {
                cout << "\tEnter Capacity >> ";
                cin >> value;
            } while (!IsValid(value));
 
            stack = CreateStack(value);
            stackExists = true;
            break;
        case 2:
            stack.~Stack();
            stackExists = false;
            break;
        case 3:
            if (stackExists) {
                cout << "\tEnter Data to Push >> ";
                cin >> data;
                stack.Push(data);
            }
            else {
                cout << "\tCreate Stack first." << endl;
            }
            break;
        case 4:
            if (stackExists) {
                stack.Pop();
            }
            else {
                cout << "\tCreate Stack first." << endl;
            }
            break;
        case 5:
            if (stackExists) {
                cout << "\tTop >> " << stack.Top() << endl;
            }
            else {
                cout << "\tCreate Stack first." << endl;
            }
            break;
        case 6:
            cout << stack;
            break;
        case 0:
            cout << "BYE!" << endl;
            exit(0);
        default:
            cout << "WRONG INPUT" << endl;
            cout << "Re-Enter" << endl;
            break;
        }
    }
    system("pause");
    return 0;
}

Stack 구현한 코드 돌려보기 : Stack 만들고 Push하기

Stack 구현한 코드 돌려보기 : Pop하기

Stack 과제

다음은 여러분이 스택을 이해하기 위해 도전 해 볼만한 것들이다.

1. 문자열 받으면 스택에 차례로 넣어서 거꾸로 출력하기.

예) ABCDE -> EDCBA

2. 스택이 꽉 차면 2배로 스택 용량을 늘리도록 구현 해보기.

음~ 생각나는게 없으니 여기까지!

감사합니다.