[자료구조] C++ 스택(STACK)

스택(STACK)의 정의

스택의 구조는 이렇게 생겼는데, 가장 늦게 들어간게 가장 먼저 나가는 방식이다.

가장 늦게 들어간 자료가 가장 먼저 나가는 구조를 후입선출(LIFO, Last In First Out)이라고도 부른다.

편하게 컵이라고 생각하면 된다. 컵과 같이, 스택도 한쪽 끝에서만 자료를 넣고 뺄 수 있다.

스택의 가장 위를 top이라고 하고, 삽입과 삭제가 top에서 일어난다.

스택의 연산

push	스택에 새로운 원소를 삽입하는 연산
pop	스택의 top 원소를 제거하고 반환
empty	스택이 비여있는지 검사
size	스택의 크기

참고자료

스택에 관한 자세한 내용은

 https://visualgo.net/ko/list?slide=4

위 링크에 들어가면  push와 pop을 직접 하고, push와 pop을 하는 과정을 눈으로 확인할 수 있어서 직접 스택의 구조와 원리를 더욱 실감나게 느낄 수 있다.

참고로 Visualgo의 스택은 배열이 아닌 연결리스트로 구현해서 여기서 구현한 스택과 다른 구조이다.

연결리스트에 대해서는 다른 포스팅에서 설명하겠다.

스택 직접 구현 예제

이제 스택을 직접 구현해 보겠다.

예제는 BOJ 10828번 스택 문제이다.

#include <iostream>
#include <string.h>
using namespace std;
 
int stack[10001], top = -1;
 
void push(int x){
    stack[++top] = x;
}
 
int empty() {
    if (top < 0)
        return 1;
    else return 0;
}
 
void pop() {
    if (empty() == 1)
        cout << "-1"<<"\n";
    else {
        cout << stack[top] << "\n";
        stack[top--] = 0;
    }
}
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char str[10];
        cin >> str;
        if (!strcmp(str, "push")) {
            int x; cin >> x;
            push(x);
        }
        else if (!strcmp(str, "top")) {
            if (empty() == 1)cout << "-1"<<"\n";
            else cout << stack[top] << "\n";
        }
        else if (!strcmp(str, "pop")) {
            pop();
        }
        else if (!strcmp(str, "empty")) {
            cout << empty() << "\n";
        }
        else {//size()함수는 간단하기 때문에 함수를 만들지 않음
            cout << top + 1 << "\n";
        }
    }
    return 0;
}
 

BOJ 10828 스택 문제

BOJ 10828 스택 문제는 아주 기초적인 단순한 스택 구현 문제이다.

이 문제에서 명령은 push, pop, size, empty, top으로 총 5가지다.

이렇게 스택을 직접 구현해봤다.

stack 배열을 만들고, 스택을 직접 구현할때 중요한 top을 가르키는 top 변수를 -1로 초기화하였다.

이 top변수는, top이 어디있는지 알려주면서 스택이 어디까지 차 있는지 저장한다.

이 말은 즉, top(변수)은 스택에 있는 가장 위에있는 데이터의 위치를 가르키킨다는 말이다.

먼저 push 함수는 top을 증가시키고, 배열에 X를 stack배열에 넣도록 하게 만들었다.

pop함수는, empty를 호출해서 스택이 비였는지를 검사한다음 비였으면 -1을, 

그렇지 않으면 top 원소를 출력하고, 스택의 가장 위를 0으로 만들고 top을 감소시킨다.

empty 함수는 간단하게 top이 0보다 작으면 1, 아니면 0을 반환하도록 하였다.

나머지 명령들은 size는 top에 1을 더하는 것으로, top은 비였으면 -1, 아니면 top 원소를 출력하도록 하였다.

실행 결과

후입 선출이기 때문에, pop()을 하면 push()한 순서의 반대 순서로 나온다.

push(1), push(2), push(3)을 한 상태에서 top()을 했을때, 제일 위에있는 3이 출력되고, size()를 했을때는 스택의 크기인 3, 

empty()는 비어있는지 아닌지의 여부를 확인하는 것이므로, 거짓이기 때문에 0을 출력한다.

두번째로 top()을 했을때는 스택이 비어있으므로 -1을, size()를 호출했을때는 0, empty()를 호출했을때는 1을 출력한다.

STL 스택

추후 추가예정

---

MADE BY DEV++

DESIGNED BY DEV++