자료구조 · C++로 구현한 스택

스택 (Stack)

스택은 후입선출(LIFO; Last in First out) 방식의 선형 자료구조이다.

후입선출이란, 나중에 들어간 것이 먼저 나온다는 뜻이다. 즉, 스택은 나중에 들어간 데이터를 먼저 처리하는 자료구조이다.

---

Stack C++ 구현 소스코드

#include <iostream>
using namespace std;

const int MAX = 1e5;

class Stack {
private:
    int data[MAX];
    int index;
public:
    Stack();
    bool empty();
    void push(int x);
    void pop();
    int top();
    int size();
};

Stack::Stack() {
    index = -1;
}

bool Stack::empty() {
    return index == -1;
}

void Stack::push(int x) {
    index += 1;
    data[index] = x;
}

void Stack::pop() {
    index -= 1;
}

int Stack::top() {
    return data[index];
}

int Stack::size() {
    return index+1;
}

int main() {
    Stack s;
    for (int i=1; i<=10; i++) s.push(i); // Push 1~10
    for (int i=1; i<=4; i++) s.pop(); // Pop 10~7
    for (int i=1; i<=4; i++) s.push(i); // Push 1~4
    cout << "* Size: " << s.size() << '\n';
    while (!s.empty()) {
        cout << "Pop: " << s.top() << '\n';
        s.pop();    // Pop all
    }
    return 0;
}

# main 함수 출력 결과

* Size: 10
Pop: 4
Pop: 3
Pop: 2
Pop: 1
Pop: 6
Pop: 5
Pop: 4
Pop: 3
Pop: 2
Pop: 1

✓ 배열로 구현한 스택이다. 예외 처리는 하지 않았다.

---

Stack 클래스 설명

const int MAX = 1e5;

class Stack {
private:
    int data[MAX];
    int index;
public:
    Stack();
    bool empty();
    void push(int x);
    void pop();
    int top();
    int size();
};

✓ MAX는 스택의 최대 사이즈이다. 값을 바꾸면 최대 사이즈를 조절할 수 있다.

✓ Data는 스택에 넣은 원소를 저장하는 배열이다.

✓ index는 가장 마지막에 넣은 원소의 위치를 가리키는 변수다.

# 생성자와 empty 함수

Stack() {
    index = -1;
}

bool empty() {
    return index == -1;
}

✓ 생성자를 이용하여 인덱스를 -1로 초기화한다.

✓ empty 함수는 스택이 비어있는지 확인하는 함수이다. 인덱스가 -1이면, 스택이 비어있는 상태이다.

# push 함수

void push(int x) {
    // Full check, if index == MAX-1
    index += 1;
    data[index] = x;
}

✓ 스택에 원소를 집어넣는다. 인덱스를 1 증가시키고, 그 위치에 원소를 저장한다.

✓ 원소를 넣기 전에, 스택이 꽉 찬 상태인지 확인하여 예외 처리를 해야 한다. index == MAX-1 로 확인하면 된다. 스택 사이즈를 넉넉하게 두는 편이 좋다.

# pop 함수

void pop() {
    // Empty check
    index -= 1;
}

✓ 스택에서 가장 나중에 넣은 원소를 뺀다. 인덱스를 1 감소시키면 된다.

✓ 원소를 빼기 전에, 스택이 비어있는 상태인지 확인하여 예외 처리를 해야 한다. 위에서 구현한 empty() 함수를 이용하면 된다.

# top 함수

int top() {
    // Empty check
    return data[index];
}

✓ top 함수는 가장 나중에 넣은 원소가 무엇인지 보는 함수이다.

✓ 스택이 비어있는 상태인지 확인하여 예외 처리를 해야 한다.

# size 함수

int size() {
    return index+1;
}

✓ 스택에 몇 개의 원소가 들어있는지 확인하는 함수이다.