기본적인 자료구조 스택(Stack) 배우기

개념

Stack은 가장 기본적이고 널리 쓰이고 있는 자료구조이다. 처음에 넣은 것은 마지막에 돌려주는 Last in First Out 즉, LIFO의 특성을 가진다.

구현

기본적으로 다음과 같은 함수를 가지고 있으면 된다.

• push(element)
• pop()
• isEmpty()

1.C언어를 이용한 구현(배열)

이 같은 경우 stack이라는 배열과 top이라는 변수가 필요하다. top 변수는 가장 위에 있는 원소를 가르키는 것이다. 처음에 top 초기값이 -1인 이유는 인덱스 0번째 자리에도 값이 들어가야하기 때문이다. 그리고 배열을 사용했기 때문에 top이 배열 크기를 넘어서지 않도록 조심해야한다.

 

MAX_STACK_SIZE = 100;
int stack[MAX_STACK_SIZE];
int top = -1;

int isEmpty() {
    if(top == -1) {
        return 1;
    }
    else {
        return 0;
    }
}

void push(int elemet) {
    if(top >= MAX_STACK_SIZE) {
        // 가득 찼을 때 처리
        return;
    }
    // 가장 위에 있는 원소를 갱신한다.
    stack[++top] = element;
}

int pop() {
    if(isEmpty()) {
        // 에러 처리
        return -1;
    }
    //가장 위에 있는 원소를 반환하고 top을 한 칸 아래를 가르키도록 한다.
    return stack[top--];
}

2.C++ STL을 이용한 구현

STL을 사용할려면 우리가 쓰고 싶은 자료구조를 include 시켜야한다. 보통 스택 구현과는 다르게 pop을 해도 값을 반환하지 않는다. 값을 읽을려면 top 함수를 써야한다.

#include 
#include 

int main() {
    //꺽쇠 안에 있는 것은 자기가 스택에서 쓰고자 하는 자료형이다.
    //구조체를 정의한 다음에 stack에 넣으면 그 자료형으로 스택을 사용할 수 있다.
    stack s;

    s.push(10); // stack push 연산
    int top = s.top();  // 스택에서 가장 위에 있는 Element를 엿보는 함수이다.
    cout << top << endl;
    s.pop() // stack의 pop 연산이지만, 값을 반환하지는 않는다.

    // empty() 는 스택이 비어있으면 true 아니면 false를 반환한다.
    if(s.empty()) {
        cout << "스택이 비어있습니다" << endl;
    }
}

스택을 활용한 문제들

실제로 배운 것을 응용할 때는 관련 알고리즘 문제를 풀어보는 것이 도움이 된다.

9012번 괄호

1874번 스택수열