스택 (Stack)

스택이란?

후입선출(LIFO, Last In First Out) 의 원칙을 따르는 선형 자료구조
즉, 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조로, 쌓아올린 접시 나 서적 더미 와 같은 형태로 동작
재귀적 문제 , 괄호의 유효성 검사 , 문자열 뒤집기 , 그래프 탐색 등에 자주 사용

주요 연산

1. push: 스택의 맨 위에 새로운 요소를 추가
2. pop: 스택의 맨 위에 있는 요소를 제거하고 반환
3. peek 또는 top: 스택의 맨 위에 있는 요소를 반환 (제거하지 않음)
4. isEmpty: 스택이 비어 있는지 여부를 확인
5. size: 스택에 있는 요소의 개수를 반환

특징

1. 후입선출 (LIFO): 마지막에 삽입된 데이터가 가장 먼저 삭제됨
2. 제한된 접근: 오직 스택의 맨 위에서만 삽입과 삭제가 이루어짐
3. 연산의 단순성: 삽입, 삭제 연산이 O(1)의 시간 복잡도를 가짐

장점

1. 연산이 간단하고 빠름: 삽입과 삭제가 스택의 맨 위에서만 이루어지므로, 연산이 매우 단순하고 빠름
2. 재귀적인 문제 해결: 함수 호출 시, 함수의 실행 상태를 스택에 저장하므로 재귀적 문제를 쉽게 해결할 수 있음

단점

1. 메모리 제한: 메모리 크기 제한이 있을 경우, 스택 오버플로우(Stack Overflow)가 발생할 수 있음
2. 선형 탐색 불가: 스택은 후입선출 구조이므로, 중간에 있는 데이터를 탐색하려면 모든 요소를 확인해야 함

사용 예시

1. 함수 호출 스택: 프로그래밍 언어의 런타임 시스템에서 함수 호출을 관리하는 데 스택이 사용
2. 괄호의 유효성 검사: 여는 괄호가 스택에 쌓이고, 닫는 괄호가 등장할 때마다 스택에서 꺼내어 유효성을 검사
3. 후위 표기법 계산: 스택을 이용하여 후위 표기법(Postfix notation)으로 작성된 수식을 계산
4. 웹 브라우저의 뒤로 가기: 새로운 페이지로 이동할 때마다 현재 페이지를 스택에 push하고, 뒤로 가기 버튼을 누르면 스택에서 pop하여 이전 페이지로 돌아감

스택은 후입선출 구조를 활용하여, 재귀적 문제나 순서가 중요한 문제 해결에 적합한 자료구조

스택의 구현 방법

배열 기반 스택

배열을 사용하여 스택을 구현하는 방식
배열의 마지막 인덱스를 스택의 top으로 간주하여, push와 pop 연산을 수행

#include <iostream>
using namespace std;

#define MAX 1000

class Stack {
    int top;  // 스택의 맨 위 요소를 가리키는 인덱스

public:
    int arr[MAX];  // 스택 배열 (크기: 1000)

    Stack() { top = -1; }  // 초기화

    // 스택에 새로운 요소를 추가
    bool push(int x) {
        if (top >= (MAX - 1)) {  // 스택 오버플로우 방지
            cout << "Stack Overflow";
            return false;
        }
        arr[++top] = x;
        cout << x << " pushed into stack
";
        return true;
    }

    // 스택에서 요소 제거 및 반환
    int pop() {
        if (top < 0) {  // 스택 언더플로우 방지
            cout << "Stack Underflow";
            return 0;
        }
        int x = arr[top--];
        return x;
    }

    // 스택의 맨 위 요소를 반환
    int peek() {
        if (top < 0) {
            cout << "Stack is Empty";
            return 0;
        }
        return arr[top];
    }

    // 스택이 비어있는지 확인
    bool isEmpty() {
        return (top < 0);
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    cout << stack.pop() << " popped from stack";  // 30 popped from stack
    cout << "Top element is " << stack.peek() << endl;  // Top element is 20

    return 0;
}

연결 리스트 기반 스택

연결 리스트를 사용하여 스택을 구현하면, 스택의 크기가 동적으로 조정되므로 메모리 낭비가 줄어듬

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class Stack {
public:
    Node* top;  // 스택의 맨 위 노드를 가리킴

    Stack() { top = nullptr; }  // 초기화

    // 스택에 새로운 요소를 추가
    void push(int x) {
        Node* newNode = new Node();
        newNode->data = x;
        newNode->next = top;
        top = newNode;
        cout << x << " pushed into stack";
    }

    // 스택에서 요소 제거 및 반환
    int pop() {
        if (top == nullptr) {  // 스택 언더플로우 방지
            cout << "Stack Underflow";
            return 0;
        }
        int x = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return x;
    }

    // 스택의 맨 위 요소를 반환
    int peek() {
        if (top == nullptr) {
            cout << "Stack is Empty";
            return 0;
        }
        return top->data;
    }

    // 스택이 비어있는지 확인
    bool isEmpty() {
        return (top == nullptr);
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    cout << stack.pop() << " popped from stack";  // 30 popped from stack
    cout << "Top element is " << stack.peek() << endl;  // Top element is 20

    return 0;
}

라이브러리

std::stack은 기본적으로 deque 컨테이너를 기반으로 구현되어 있지만, vector나 list와 같은 다른 컨테이너를 사용하여 구현 가능

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

int main() {
    stack<int> s;

    // 요소 추가
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "스택 크기: " << s.size() << endl;
    cout << "스택 맨 위 요소: " << s.top() << endl;

    // 요소 제거
    s.pop();
    cout << "pop 후 맨 위 요소: " << s.top() << endl;

    // 스택이 비어있는지 확인
    cout << "스택이 비어있나요? " << (s.empty() ? "예" : "아니오") << endl;

    // 스택의 모든 요소 출력
    cout << "스택의 모든 요소: ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    return 0;
}