스택(Stack)

인프런 - 파이썬으로 배우는 알고리즘 기초 강의 이미지

✔ 스택(Stack)

스택은 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 아주 많이 사용되는 자료 구조이다.

스택은 제한적으로 접근할 수 있는 나열 구조로 한쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO : Last-In First-Out) 구조이다. 즉, 가장 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

 

쉬운 예시로 프링글스 과자를 생각하면 된다.

프링글스 과자를 포장할 때 처음 과자가 통 맨 밑으로 들어가게 되고 그다음부터 위로 쌓이게 되고 구매자는 과자를 먹을 때 통 맨 위에서부터 하나씩 꺼내서 먹게 된다. 이 구조가 스택 자료 구조에 해당한다.

 

✔ 스택의 연산

스택은 가장 윗부분을 "top"이라 명칭 한다.

• top(): 스택의 가장 윗 데이터를 반환
• pop(): 스택의 가장 윗 데이터를 삭제
• push(x): 스택에 데이터 x를 삽입(맨 위로 들어간다)
• size(): 스택에 들어있는 데이터의 개수 반환
• empty(): 스택이 비었다면 "true"를 반환하고, 그렇지 않으면 "false"를 반환

"top", "pop"의 연산은 다르다. top 연산은 가장 윗 데이터의 값을 "return"하고, pop 연산은 가장 윗 데이터의 값을 스택에서 삭제하고 삭제 값을 "return"하지 않는다.

 

✔ 스택 동작 과정

• 스택에 데이터 삽입(push)

• 스택에 데이터 삭제

 

✔ 스택 구현(C++)

스택은 "C++" 라이브러리에 있기 때문에 라이브러리를 등록해서 사용하면 된다.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    
    cout << s.empty() << "\n";  // 0
    cout << s.size() << "\n";   // 4
    s.pop();
    
    cout << s.top() << "\n";    // 3
    s.push(5);
    while(!s.empty()) {
        cout << s.top() << " ";   // 5 3 2 1
        s.pop();
    }
    cout << "\n";
    cout << s.empty();  // 1
    return 0;
}

 

 

🔗 Reference

• 스택