[바미] 자료구조 - 스택(Stack)

스택(Stack)

스택(Stack)은 자료 구조 중 하나로, 데이터가 LIFO(Last In, First Out) 방식으로 관리되는 구조입니다. 

즉, 가장 나중에 삽입된 데이터가 가장 먼저 제거되는 구조를 가진 자료 구조죠.

스택의 주요연산

스택은 다음과 같은 주요 연산을 제공합니다.

• Push: 스택의 맨 위에 데이터를 삽입하는 연산.
• Pop: 스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산.
• Peek (or Top): 스택의 맨 위에 있는 데이터를 제거하지 않고 반환하는 연산.
• IsEmpty: 스택이 비어 있는지 확인하는 연산.
• IsFull: 스택이 가득 찼는지 확인하는 연산 (배열 기반 스택의 경우).

코드(Java)

class Stack {
    private int[] arr;
    private int top;
    private int capacity;

    // 스택 생성자
    public Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    // 스택에 요소를 추가
    public void push(int item) {
        if (isFull()) {
            System.out.println("Stack is full");
            return;
        }
        arr[++top] = item;
    }

    // 스택에서 요소를 제거
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        }
        return arr[top--];
    }

    // 스택이 비어있는지 확인
    public boolean isEmpty() {
        return top == -1;
    }

    // 스택이 꽉 찼는지 확인
    public boolean isFull() {
        return top == capacity - 1;
    }

    // 스택의 크기 반환
    public int size() {
        return top + 1;
    }
    
    // 스택의 top 요소 확인
    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        }
        return arr[top];
    }
}

// 메인 클래스
public class Main {
    public static void main(String[] args) {
        // 스택의 크기를 5로 설정하여 새로운 스택 생성
        Stack stack = new Stack(5);

        // 스택에 요소를 추가
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);

        // 스택의 최상위 요소를 출력
        System.out.println("Top element is: " + stack.peek());

        // 스택에서 요소를 제거
        stack.pop();

        // 스택의 최상위 요소를 출력
        System.out.println("Top element is: " + stack.peek());

        // 스택의 크기를 출력
        System.out.println("Stack size is " + stack.size());

        // 스택에서 모든 요소를 제거
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();

        // 스택이 비어 있는지 확인하고 출력
        if (stack.isEmpty()) {
            System.out.println("Stack is empty");
        }
    }
}

코드 설명

Stack 클래스와 Main 클래스로 나뉩니다. 먼저 Stack 클래스부터 설명드리겠습니다.

Stack 클래스

private int[] arr;  // 스택의 요소를 저장할 배열
private int top;    // 스택의 최상위 요소를 가리키는 인덱스
private int capacity; // 스택의 최대 크기

 

위에서 각 필드들을 선언해줍니다.

public Stack(int size) {
    arr = new int[size];
    capacity = size;
    top = -1;
}

스택 생성자부분입니다. 스택의 크기를 설정하고 배열을 초기화시켰습니다.

top을 -1로 설정함으로써 스택이 비어 있음을 나타냅니다.

 

public void push(int item) {
    if (isFull()) {
        System.out.println("Stack is full");
        return;
    }
    arr[++top] = item;
}

스택의 요소를 추가하는 메소드 부분입니다. 먼저 스택이 가득 찼는지 확인하는데 가득 차면 메시지를 출력하고 리턴합니다. 그렇지 않으면 top을 증가시키고 해당 위치에 요소를 추가하는 형태입니다.

 

public int pop() {
    if (isEmpty()) {
        System.out.println("Stack is empty");
        return -1;
    }
    return arr[top--];
}

요소를 제거하는 메소드 부분입니다. 먼저 스택이 비어 있는지 확인하고, 비어 있으면 메시지를 출력하고 -1을 반환하고,

그렇지 않으면 현재 top 위치의 요소를 반환하고 top을 감소시킵니다.

 

public boolean isEmpty() {
    return top == -1;
}

public boolean isFull() {
    return top == capacity - 1;
}

스택이 꽉 찼는지, 비어있는지 확인하기위해 사용하는 메소드들입니다.

top이 -1이면 스택이 비어있다는 것을, top이 capacity - 1이면 스택이 가득 찼다는 것을 의미합니다.

 

public int size() {
    return top + 1;
}

현재 스택의 크기를 반환해주는 메소드입니다.

public int peek() {
    if (isEmpty()) {
        System.out.println("Stack is empty");
        return -1;
    }
    return arr[top];
}

스택의 최상위 요소를 반환해주는 메소드입니다.

먼저 스택이 비어 있는지 확인하고, 비어 있으면 메시지를 출력하고 -1을 반환하고, 그렇지 않으면 현재 top 위치의 요소를 반환해주죠.

---

Main 클래스

이제 Main 클래스 부분입니다.

Stack stack = new Stack(5);

먼저 크기가 5인 새로운 스택을 생성시켜줍니다.

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);

그리고 스택이 차례대로 1~5까지 추가할 수 있게 만들어줍니다.

System.out.println("Top element is: " + stack.peek());

현재 스택의 최상위 요소를 출력합니다. 현재 최상위 요소는 당연히 5겠죠?

 

stack.pop();

이제 요소 하나를 제거해보겠습니다. 그 후 제거가 제대로 됐는지 확인해 볼까요?

System.out.println("Top element is: " + stack.peek());

스택의 최상위 요소를 다시 출력해봅시다. 이제 최상위 요소는 4가 되겠죠?

 

System.out.println("Stack size is " + stack.size());

스택의 현재 크기를 출력해줍니다. 현재 크기는 4가 되겠군요.

 

stack.pop();
stack.pop();
stack.pop();
stack.pop();

이제 이 모든 요소를 제거해봅시다. 4, 3, 2, 1이 차례로 제거될겁니다.

if (stack.isEmpty()) {
    System.out.println("Stack is empty");
}

이제 스택이 비어있는지 확인하고 비어 있으면 "Stack is empty"를 출력하도록 만들었습니다.

---

스택은 어느정도의 크기까지 만들어 낼 수 있는가?

주로 사용하는 언어와 환경에 따라 결정되는데 크게 프로그래밍 언어에 따라, 운영 체제, 하드웨어에 따라, 컴파일러, 런타임 설정에 따라 스택의 요소를 제한되고 있습니다.

⚠ 주의
스택의 크기는 제한적이므로, 재귀 함수 호출이 너무 깊어지거나 스택을 과도하게 사용하는 경우 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.

❓ 스택오버플로우 (Stack Overflow)
프로그램이 할당된 스택 메모리를 초과하여 더 이상 사용할 수 없는 상태를 의미합니다.

프로그래밍 언어에서

Java의 경우 기본적으로 각 스레드마다 고정된 스택의 크기가 있습니다. 각 스레드에 대해 1MB의 스택 크기가 기본적으로 할당되고, -Xss 옵션을 사용하여 크기를 조정할 수 있습니다.

 

C/C++의 경우 일반적으로 1MB ~ 8MB 사이로 설정되는데 컴파일러나 링커 옵션을 사용하여 크기를 조정할 수 있습니다.

 

Python의 경우 기본적으로 8MB의 스택 크기가 할당되며 sys.setrecursionlimit() 함수를 사용하여 재귀 한도를 설정할 수 있습니다.

운영 체제 및 하드웨어에서

스택은 메모리의 특정 영역에 할당되며, 운영 체제와 하드웨어의 메모리 구조에 따라 크기가 결정되는데 32bit 시스템과 

 

컴파일러 및 런타임 설정

위 '프로그래밍에서' 부분에서 설명 드린 것처럼 컴파일러 옵션이나 런타임 설정을 통해 스택 크기를 조정할 수 있습니다.