[Data Structure] 스택(Stack)

Stack

스택(Stack)은 후입선출(LIFO, Last In First Out)의 원칙을 따르는 선형 자료구조로, 데이터의 삽입과 삭제가 한쪽 끝(Top) 에서만 이루어진다. 중간 데이터에 직접 접근할 수 없으며, 반드시 마지막에 들어온 데이터부터 제거해야한다.

출처 https://taekyounglee1224.tistory.com/57

 

 

추상 자료형(ADT) 관점에서 바라보면 스택은 다음 연산을 기본으로 정의한다.

연산	설명	시간 복잡도
push(item)	스택의 Top에 요소 삽입	O(1)
pop()	Top 요소 제거 및 반환	O(1)
peek()	Top 요소 확인 (삭제 X)	O(1)
isEmpty()	스택이 비어있는지 확인	O(1)
size()	요소 개수 반환	O(1)

 

java에서 배열 기반으로 Stack를 직접 구현해 보았다.

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 (top == capacity - 1) System.out.println("Stack Overflow") return;
        arr[++top] = item;
    }

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

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

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

 

또한, 재귀적인 함수의 호출은 스택 방식으로 동작하는데, 함수가 호출 될때마다 해당 함수의 Stack Frame이 운영체제가 할당한 스택 영역에 쌓이게 된다.

 

스택은 컴퓨터 운영체제에서 프로그램 실행 흐름의 관리, 함수 호출과 반환 처리, 그리고 메모리의 효율적 관리를 위한 핵심 메커니즘이다. 스택의 작동원리와 다양한 응용 사례를 깊이 있게 학습하면, 단순한 자료구조의 이해를 넘어서 컴퓨터 내부 구조와 운영체제, 컴파일러 등의 실제 동작을 이해하는데 도움이 된다. 앞으로 운영체제와 프로세스 메모리에 관한 포스팅을 진행하면서, 스택 구조가 어떻게 동작하는지 설명하겠다.