[자료구조] 스택 (Stack)

스택 개념

스택이란 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조를 말한다.

LIFO : 마지막으로 들어온 값이 처음으로 나가는 것
FILO : 처음 들어온 값이 마지막에 나가는 것

스택은 완전히 꽉 찼을 때 Overflow 상태라고 하며 완전히 비어 있으면 Underflow 상태라고 한다.
삽입(Push)과 제거(Pop)는 모두 Top이라는 스택의 한쪽 끝에서만 일어난다.

스택 연산

• pop(): 스택에서 가장 위에 있는 항목을 제거한다.
• push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

스택의 장단점

장점

• 구조가 단순하기 때문에 구현이 쉽다.
• 데이터의 저장 및 읽기 속도가 빠르다.

단점

• 데이터의 최대 갯수를 미리 정해야한다.
• 파이썬의 경우 재귀함수는 1000번까지만 호출이 가능하다.
• 저장공간의 낭비가 발생할 수 있다.
• 최대 갯수만큼 미리 저장공간을 확보해야 한다.

시간복잡도

• Insertion : O(1)
• Deletion : O(1)
• Search : O(n)

삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가진다.
하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가진다.

스택을 사용하는 경우

• 재귀 알고리즘을 사용하는 경우 스택이 유용하다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 함수를 호출시 현재 진행중인 명령어 주소를 스택에 저장한다.
• 인터럽트 처리를 할 때에 현재 진행중인 명령어 위치를 스택에 push하고 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행중이던 명령어 위치를 스택에서 pop을 통해 받아온다.

구현

C++

#include <iostream>
#define stack_size 100
using namespace std;
 
struct stack {
    int top = -1;
    int arr[stack_size];
    void push(int data) {
        if (top == stack_size-1) {
            printf("stack is full\n");
            return;
        }
        arr[++top] = data;
    }
    int pop() {
        if (empty()) {
            printf("stack is empty\n");
            return -1;
        }
        return arr[top--];
    }
    int peek() {
        if (empty()) {
            printf("stack is empty\n");
            return -1;
        }
        return arr[top];
    }
    bool empty() {
        return top <= -1;
    }
};
int main() {
    stack st;
    //현재 스택은 비워져있는 상태
    cout << "is stack empty? "<<st.empty() << endl;
    cout << st.pop() << endl;
    cout << st.peek() << endl;
 
        //for 루프가 돌면 스택은 1개만 저장 가능한 상태
    for (int i = 0; i < stack_size-1; i++)
        st.push(i + 1);
 
        cout << endl;
        cout << "after for loop"<<endl;
    st.push(15);
        //스택은 전부 채워져 있는 상태
    st.push(120);
        //스택에서 한 개가 비워짐, 1개 채울 수 있는 상태
    st.pop();
 
    st.push(120);
 
    cout<<endl;
        //스택이 비워지면 while루프 종료
    while(!st.empty())
        cout << st.pop() << endl;
     
}

STL

#include<iostream>
#include<stack>

using namespace std;

int main(){
    stack<int> s; //스택 생성

    //push : top에 원소를 추가
    s.push(1);
    s.push(2);
    s.push(3);

    //pop : top에 있는 원소 삭제
    s.pop();

    //top : top에 있는 원소 반환
    cout << "top element is " << s.top();

    //size : 스택 사이즈 반환
    cout << "Size of stack is " << s.size();
    //empty : 스택이 비어있으면 True, 비어있지 않으면 False 반환
    cout << "Is it empty? " << s.empty();

}