자료구조 - 스택(Stack)

스택이란?

• 후입선출(LIFO, Last In First Out) 자료구조
• 가장 최근에 삽입된 데이터가 가장 먼저 삭제

1. 스택의 기본 구조

스택의 기본 연산(push, pop, top, isEmpty)을 설명하는 예제

• push : 스택에 요소를 추가, 배열의 끝에 새 요소르 삽입하고, top 인덱스를 증가시킴
• pop : 스택에서 요소를 제거, 배열의 끝에서 요소를 제거하고, top 인덱스를 감소
• peek : 스택의 최상위 요소를 확인, 스택의 top 인덱스에 있는 요소를 반환
• isEmpty : 스택이 비어 있는지 확인, top 인덱스가 -1이면 스택이 비어있는 것

스택 구현

#include <iostream>
#define MAX 1000 // 스택의 최대 크기

using namespace std;

class Stack
{
    int top;
    int capacity;        // 스택의 크기

public:
    int a[MAX];            // 스택 배열

    Stack() 
    {
        top = -1;         // 스택 초기화
        capacity = 0;    // 스택의 크기 초기화
    }

    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
    int size();            // 스택의 크기를 반환하는 함수
};

// 스택에 요소를 추가하는 함수
bool Stack::push(int x)
{
    if(top >= (MAX - 1))
    {
        cout<< "스택 오버플로우\n";
        return false;
    }
    else
    {
        a[++top] = x;
        capacity++;
        cout<<x<<" 스택에 푸쉬 되었습니다\n";
        return true;
    }
}

// 스택에서 요소를 제거하는 함수
int Stack::pop()
{
    if(top < 0)
    {
        cout<< "스택 언더플로우\n";
        return 0;
    }
    else
    {
        int x = a[top--];
        capacity--;
        return x;
    }
}


// 스택에 최상위 요소를 반환하는 함수
int Stack::peek()
{
    if(top < 0)
    {
        cout<<"스택에 쌓인게 없어요\n";
        return 0;
    }
    else
    {
        int x = a[top];
        return x;
    }
}

// 스택이 비었는지 확인하는 함수
bool Stack::isEmpty()
{
    return (top<0);
}

// 스택의 크기를 반환하는 함수
int Stack::size()
{
    return capacity;
}


int main()
{
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout<<s.pop()<<"\n";
    cout<<s.peek()<<"\n";
    cout<<s.size()<<"\n";
    cout<<s.isEmpty()<<"\n";

    return 0;
}

과제로 하면 좋을 것

1. 스택의 크기 반환 함수를 추가해보자
2. 스택을 동적 배열로 구현해보자
3. 연결 리스트를 이용한 스택을 구현해보자
4. 예외 처리를 추가하여 더 견고한 스택 클래스를 만들어보자

필요에 따라 STL의 std::stack을 사용하는 것도 좋은 방법

스택을 동적 배열로 구현

#include <iostream>
#include <vector>

using namespace std;

class Stack {
private:
    vector<int> a; // 동적 배열을 이용한 스택

public:
    Stack() {}

    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
    int size(); // 스택의 크기를 반환하는 함수
};

// 스택에 요소를 추가하는 함수
bool Stack::push(int x) {
    a.push_back(x);
    cout << x << " 스택에 푸쉬 되었습니다\n";
    return true;
}

// 스택에서 요소를 제거하는 함수
int Stack::pop() {
    if (a.empty()) {
        cout << "스택 언더플로우\n";
        return 0;
    } else {
        int x = a.back();
        a.pop_back();
        return x;
    }
}

// 스택의 최상위 요소를 반환하는 함수
int Stack::peek() {
    if (a.empty()) {
        cout << "스택에 쌓인게 없어요\n";
        return 0;
    } else {
        return a.back();
    }
}

// 스택이 비었는지 확인하는 함수
bool Stack::isEmpty() {
    return a.empty();
}

// 스택의 크기를 반환하는 함수
int Stack::size() {
    return a.size();
}

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.pop() << " 스택에서 팝 되었습니다\n";
    cout << "최상위 요소는 " << s.peek() << " 입니다\n";
    cout << "스택의 크기는 " << s.size() << " 입니다\n";
    cout << "스택이 비었나요? " << (s.isEmpty() ? "네" : "아니요") << endl;

    return 0;
}