[자료구조] 스택의 개념, 구현 및 적용 C/C++

📕  스택이란??

---

 자료구조 스택을 이해하기 위해서는 영어 stack이 무엇인지를 알면 이해가 쉽다.

stack은 '무더기', '쌓아놓은 더미' 등을 가리키는 명사의 뜻과 '쌓다'라는 동사의 뜻이 있다.

여기서 우리가 눈여겨봐야 할 것은 '쌓는다'라는 특성이다.

 

📕  스택의 특징

---

 어떠한 것을 '쌓는' 것이기 때문에 생기는 특성이 있는데, 바로 후입선출(LIFO)

즉, 먼저 들어간 것이 나중에 나오는 특성이다.

간단한 예시로 책 더미를 생각해보자.

책을 위로 점점 쌓고난 후, 맨 밑에 있는 책을 꺼내기 보기 위해서는 그 책위로 쌓여있는 책을 다 빼낸 후에야 가능할 것이다.

반대로, 맨 마지막에 쌓은 책의 경우 가장 위에 있기 때문에 제일 먼저 꺼낼 수 있을 것이다.

그렇기 때문에 후입선출, Last In First Out(LIFO) 라고 하는 것이다.

그리고 이러한 기능들은 스택에서 꺼낼 때는 pop(), 스택에 삽입할 때는 push()라는 명령어를 통해서 수행된다.

 

그리고 우리는 스택의 상단을 top, 하단을 bottom이라고 부른다.

 

 

 

📕  스택의 구현 및 사용 C/C++

---

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100
typedef int element;
element stack[MAX_SIZE];
int top = -1;

//공백 상태인지 확인
int is_empty(void) {
    return (top == -1);
}

//포화 상태인지 확인
int is_full(void) {
    return (top == (MAX_SIZE - 1));
}

//push(삽입)함수
void push(element item) {
    if(is_full()) {
        fprintf(stderr, "error(stack full)");
        return;
    } else {
        stack[++top] = item;
    }
}

//pop(삭제)함수
element pop(void) {
    if(is_empty()) {
        fprintf(stderr, "error(stack empty)");
        exit(1);
    } else {
        return stack[top--];
    }
}

//peek함수(top을 po하지 않고, 반환)
element peek(void) {
    if(is_empty()) {
        fprintf(stderr, "error(stack empty)");
        exit(1);
    } else {
        return stack[top];
    }
}

 

대부분의 동적 할당이 기본으로 가능한 언어에서는 pop, top, push, empty 등과 같은 함수들을 지원하기 때문에,

C처럼 힘들게 구현할 필요가 없다. (javascript는 empty()가 없다....)

 

C++과 간단한 문제를 통해 스택의 기본적인 사용을 알아보자.

아래는 백준 10828번 스택 문제이다.

기본적인 기능들을 사용해보기에 적합한 문제이다.

 

스택은 C++에서 vector와 많이 닮아 있다.(하지만 벡터가 더 유연하고, 인덱스 접근이 가능하다.)

vector에서 push_back()과 pop_back()를 써봤다면, 스택을 이해하는데 문제없다.

#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
//
//14
//push 1
//push 2
//top => 2
//size =>2
//empty => 거짓 => 0
//pop => 맨위 => 2
//pop => 맨위 => 1
//pop => 없으니까 => -1
//size => 없으니까 = 0
//empty => 비었으니까 => 1
//pop => 없으니까 => -1
//push 3
//empty => 있으니까 => 0
//top -> 3

stack<int> arr;

int main() {
    int op;
    int value;
    cin >> op;
    string s;
    for(int i = 0; i < op; i++) {
        cin >> s;
        if(s == "push") {
            cin >> value;
            arr.push(value);
        }
        else if(s == "top") {
            if(arr.empty()) {
                cout << "-1" << "\n";
            }
            else {
                cout << arr.top() << "\n";
            }
        }
        else if(s == "size") {
            cout << arr.size() << "\n";
        }
        else if(s == "empty") {
            cout << arr.empty() << "\n";
        }
        else if(s == "pop") {
            if(!arr.empty()) {
                cout << arr.top() << "\n";
                arr.pop();
            }
            else {
                cout << "-1" << "\n";
            }
        }
    }
    return 0;
}