스택(Stack)이란

자료구조 중 하나로, 데이터가 들어가는 배열이라 생각하면 편하며
후입선출(LIFO: Last In First Out) 구조를 가진다.              // 가장 최근에 들어온 데이터가 가장 먼저 나가는 구조

1. 스택의 기본 구조

스택은 현재 들어와 있는 데이터의 최상단을 가리키는 top과 각 데이터의 요소, 삽입-삭제(push-pop) 메소드를 가진다.

다음은 스택을 C++의 객체를 이용하여 간단히 구현한 것이다. ( 이때 스택의 요소는 정수형으로 하였다 )

#define MAX_STACK_SIZE 5

class Stack{
private:
    int top;
    int array[MAX_STACK_SIZE];
public:
    Stack(){ top = -1; }
    ~Stack(){}
    bool isEmpty(){ return top == -1; }
    bool isFull(){ return top == MAX_STACK_SIZE -1; }
    void push(int i){
        if(!isFull()) array[++top] = i;
        else return;
    }
    int pop(){
        if(!isEmpty()){ return array[top--]; }
    }
    void display(){
        for (int i = 0; i <= top; i++){
            cout << array[i] << " ";
        }
        cout << endl;
    }
};

Stack 객체 설명

• private으로 top(스택의 최상단 인덱스를 가리킴), array(스택의 데이터를 삽입하기 위한 방식)를 선언하였다.
• Stack(){} // 생성자 함수로 객체 생성 시 to을 -1로 초기화한다.
• bool isEmpty(){} // 스택이 비어있는 지 확인한다, 비어있으면 true를 반환한다.
• bool isFull(){} // 스택이 꽉 차 있는 지를 확인한다, 꽉 차 있을 경우 true를 반환한다.
• void push(int i){} // isFull을 확인하고 아닐 경우 top의 값을 1 더한 후 array에서 top번째 요소를 i로 지정한다.
• int pop(){} // isEmpty를 확인하고 아닐 경우 array에서 top번째 요소를 리턴하고, top의 값을 1 뺀다.
• void display(){} // 스택의 요소를 top의 크기까지 디스플레이한다.

2. main() 함수 예제

int main(){
    Stack s; // 스택 s 선언
    s.push(1); // 1 추가
    s.push(2); // 2 추가
    s.push(3); // 3 추가
    s.push(4); // 4 추가
    s.push(5); // 5 추가
    s.push(6); // isFull이 true이기에 추가 x
    cout <<s.pop() << endl; // 스택의 최상단 값이었던 5가 반환, 이후 top--
    s.push(7); // 7 추가
    s.display(); // 1 2 3 4 7

    return 0;
}

3. output

5
1 2 3 4 7

정리,
스택은 후입선출 - 선입후출 구조를 가지는 자료구조
다양한 문제를 해결하기 위한 알고리즘에서 활용할 수 있다. - ex. 괄호 검사 알고리즘, BFS(깊이 우선 탐색) 알고리즘 etc…