chapter 1. 스택(stack)

 

오늘부터 본격적으로 자료 구조에 대한 공부를 진행해 보도록 합시다. 오늘 배울 자료 구조는 스택(stack)이라는 자료구조입니다. 아마 프로그래밍 언어 공부를 한번 정도 해본 사람이라면 낯선 단어는 아닐 겁니다. 그렇다고 너무 친숙하지도 않죠 ㅎ...

 

스택은 변수를 선언하고 저장할 때 사용됩니다. 아마도 C/C++에서 동적 할당에 대해 배우실 때, 스택과 힙에 대해 간략히 들어보셨을 것 같습니다. 오늘 스택의 자료 구조에 대한 개념과 구현 방법에 대해 배워보도록 하겠습니다. 개념도 구현도 그렇게 어렵지 않으니까 천천히 따라와 주시면 될 것 같습니다.

 

 

 

---

 

stack?

 

여러분들은 스택(stack)이라는 단어를 들으면 어떤 생각이 떠오르나요? 저는 이상하게 책이 여러 층으로 쌓여있는 모습이 상상됩니다. 

 

 

이렇게 책이 쌓여있으면 가장 아래에 있는 책을 꺼내기 위해선 가장 위에 있는 책부터 하나씩 꺼내야겠죠. 물론 가장 밑에 있는 책부터 꺼낼 수도 있겠지만 그렇게 되면 구조가 너무 불안정해질 겁니다. 안정적으로 우리가 원하는 자료를착지 위해선 가장 위에 있는 자료부터 없애야겠죠?

 

 

 

 

 

 

스택은 이처럼 가장 마지막에 들어간 자료가 가장 먼저 출력되는 구조로 이루어져 있습니다. 이를 조금 어려운 말로 Last In First Out이라고 합니다. 줄여서 LIFO라고 합니다. 말로만 설명하면 어려우니 스택이 어떻게 작동하는지 그 과정을 같이 관찰해봅시다. 

---

 

push와 pop

 

 VisuAlgo(visualgo.net/en/list)

VisuAlgo - Linked List (Single, Doubly), Stack, Queue, Deque

 

다음 그림들은 비쥬얼고라는 사이트에서 스택의 과정을 이미지로 보여준 것입니다. 스택에는 크게 push와 pop이 있는데요. push는 데이터를 저장하는 함수이고 pop은 데이터를 다시 꺼내서 없애는 함수입니다. push를 하면 head에 데이터가 저장되며 pop을 하면 데이터가 head에서 제거됩니다. 

 

 

 

 

 

pop을 연속으로 3번 호출하면 3개의 데이터가 head에서 제거됩니다. 

 

 

 

 

---

 

C++로 stack 구현

 

 

이번에는 stack를 c++로 구현하도록 하겠습니다. stack.cpp와 main.cpp 파일로 분할하여 stack의 주요 기능과 내장 함수는 stack.cpp에 그리고 stack에 대한 사용은 main.cpp에서 하도록 하겠습니다. 

 

 

 

stack.cpp

#include <iostream>

using namespace std;

class Stack
{
private:
    int top, MaxSize;
    char *stack;

public:
    Stack(int size);
    bool isFull();
    bool isEmpty();
    char pop();
    void push(char element);
    void print();
};

Stack::Stack(int size)
{
    MaxSize = size;
    stack = new char[MaxSize];
    top = -1;
}

bool Stack::isFull()
{
    if (top == MaxSize - 1)
        return 1;
    else
        return 0;
}

bool Stack::isEmpty()
{
    if (top == -1)
        return 1;
    else
        return 0;
}

char Stack::pop()
{
    if (isEmpty() == 1)
        cout << "Empty!\n";
    else
        return stack[top--];
}

void Stack::push(char element)
{
    if (isFull() == 1)
        cout << "Full!\n";
    else
        stack[++top] = element;
}

void Stack::print()
{
    for (int i = 0; i < top + 1; ++i)
        cout << stack[i] << endl;
}

 

 

main.cpp

#include <iostream>
#include "stack.cpp"
using namespace std;

int main()
{

    Stack stack(5);
    stack.push('a');
    stack.push('b');
    stack.push('c');
    stack.push('d');
    stack.push('e');
    stack.push('f');

    stack.pop();
    stack.push('f');
    stack.print();

    return 0;
}

 

 

이렇게 해서 stack에 대한 개념과 구현을 모두 마쳤는데요. 많이 어려웠나요? 글로만 이해하는 것이 어렵다면 제가 업로드한 유튜브 영상도 같이 이용해 주세요~! 아마 많은 도움이 될 겁니다. 그럼 다음 시간에 봬요~!!