[DS] 스택(Stack)이란?

스택(Stack)이란?

LIFO(Last in First out) 특성을 가지는 linear list입니다.

Linear list의 한쪽 끝위치(TOP)에서 Push와 Pop이 이뤄집니다.

(즉, stack에서 pop을 하면 그 원소가 가장 마지막에 넣은 원소입니다.)

 

 

Stack을 구현하기 위한 ADT 정의

---

#include <iostream>
using namespace std;
#define SIZE 100

class stack{
    int list[SIZE];
    int top;
public:
    stack();
    void push(int a);
    int pop();
    bool stack_full();
    bool stack_empty();
};

stack - stack을 생성한 초기 empty 상태

push - stack에 원소 한 개 추가

pop - stack에서 원소 한 개 제거

full_stack - 현재 stack이 full인지에 대한 상태 확인

empty_stack - 현재 stack이 empty인지에 대한 상태 확인

 

 

함수 구현

---

stack::stack() {
    top = 0;
}

stack class의 생성자(constructor)에서는 top을 0으로 초기화시켜 줍니다.

 

 

void stack::push(int a) {
    list[top] = a;
    top++;
}

push는 stack에 원소 한 개를 추가하는 원소입니다.

top은 stack에서 원소가 추가될 위치를 의미하기에 top위치인 list 자리에 원소를 넣고 top을 증가 시켜줍니다.

 

 

int stack::pop() {
    top--;
    return list[top];
}

pop은 stack에서 원소 한 개를 제거하는 함수입니다.

현재 top은 새로운 원소가 추가될 위치이기 때문에 제거될 원소가 있는 위치로 가기 위해 -1을 해주고 원소를 return 해줍니다.

 

 

bool stack::stack_full() {
    if (top >= SIZE) return true;
    else return false;
}

stack_full은 stack이 꽉 찬 상태인지 확인하는 함수입니다.

즉, top의 값이 list의 size와 같으면 list는 꽉찼다는 의미이기 때문에 true을 return 해줍니다.

 

 

bool stack::stack_empty() {
    if(top == 0) return true;
    else return false;
}

stack_empty는 stack이 빈 상태인지 확인하는 함수입니다.

즉, 새로운 값이 들어갈 자리인 top의 값이 0이라면 원소가 없다는 뜻이기 때문에 true을 return 해줍니다.

 

main 함수 구현

---

int main() {
    stack s;
    int num[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, i, x;

    for(i = 0; i<10; i++) {
        if(num[i] % 2 == 0) s.push(num[i]);
    }

    while(!s.stack_empty()){
        x = s.pop();
        cout << x << endl;
    }
}

num 리스트에 10개의 숫자 원소를 넣어줍니다.

num 리스트의 원소를 하나씩 확인하면서 2의 배수이면 stack에 하나씩 Push합니다.

 

마지막으로 stack의 값을 하나씩 빼보면 나중에 들어온 값이 먼저 빠지기 때문에 10부터 잘 출력되는 것을 확인할 수 있습니다.

 

 

 

◡̈