스택 (Stack)

스택 (Stack)

스택은 프로그램에서 가장 자주 사용하는 추상 자료형 중 하나로, '쌓아놓은 더미'를 뜻한다. 책상 위에 쌓아놓은 책, 설거지를 위해 쌓아놓은 식판, 창고에 쌓인 박스 등이 모두 스택이다. 스택 구조를 일반적으로 후입선출 (LIFO:Last-In First-Out) 구조라 부르며, 가장 나중에 들어온 데이터가 가장 먼저 빠져나가게 된다. 스택에서의 삽입, 삭제는 한 쪽 끝에서만 일어난다고 생각하면 된다. 인터넷 브라우저의 '되돌리기' 기능이 스택의 대표적인 기능 중 하나이다. 

 

 

 

스택에서 일반적으로 생각해볼 수 있는 메소드들은 다음과 같다.

 

• push - 스택 맨위에 항목을 삽입
• pop - 스택 맨위에 항목 삭제
• peek or top - 스택의 맨 위(top)를 표시
• isEmpty - 스택이 비어있는지 확인
• isFull - 스택이 가득 차 있는지 확인
• getSize - 스택에 있는 요소 수를 반환

 

프로그래머가 직접 만들어 사용하는 스택을 사용자 스택(User Stack)이라고 하고, 컴퓨터 내부의 시스템 소프트웨어가 만들어 사용하는 스택을 시스템 스택(System Stack)이라 한다. 예를 들어 함수의 실행이 끝나면 자신을 호출한 함수로 되돌아가야 하는데 이때 스택은 복귀할 주소를 기억하는데 사용된다. 시스템 스택에는 함수가 호출될 때마다 활성 레코드가 만들어지며 복귀 주소는 이곳에 저장된다. 활성 레코드에는 자신이 넘겨받은 파라미터(Argument, Value Parameter)값 외에도 지역 변수(Local Variable) 값, 자신을 호출한 함수에게 실행 결과를 리턴 할 장소(Return Value), 실행이 끝나면 되돌아가야 할 자신을 호출한 함수의 명령문 주소(Return Address) 등이 포함되어 있다. 

 

 

구현

스택은 리스트와 마찬가지로 배열을 이용하거나 연결 리스트를 이용해서 구현할 수 있다. 배열을 사용하면 구현이 간단하지만 크기가 정적이므로 런타임에 줄거나 늘일 수 없다는 단점이 있고 연결 리스트는 크기가 동적이므로 런타임 시 필요에 따라 크기를 줄이거나 늘일 수 있지만 포인터를 위한 추가 메모리 공간이 필요하다는 단점이 있다.

 

배열을 이용한 구현은 다음과 같다.

 

public static class Stack {
    private int[] stack = new int[MAX];
    private int top = -1;   // stack이 비어있을 때의 초기값

    private boolean isEmpty() {  // 빈 스택인지 검사
        if(top < 0) return true;
        else return false;
    }
    private boolean isFull() {   // 스택이 꽉 차있는지 검사
        if(top >= MAX - 1) return true;
        else return false;
    }

    public void push(int item) {	// 아이템 추가
        if(isFull()) {		// 스택이 꽉 찼다면 오버플로우
            System.out.println("Overflow");
            return;
        }
        stack[++top] = item;
    }
    public int pop() {		// 아이템 가져오기 & 삭제
        if(isEmpty()) {		// 빈 스택이라면 언더플로우
            System.out.println("Underflow");
            return -1;
        }
        return stack[top--];
    }
}

 

 

연결 리스트를 이용한 구현은 다음과 같다.

 

private static class Node {     // 하나의 노드
    private int data;
    private Node next;

    private Node(int data) {
        this.data = data;
    }
}

private Node top;

public boolean isEmpty() {  // 빈 스택인지 확인
    if(top == null) return true;
    else return false;
}

public int peek() {     // 스택의 최상위 원소 확인
    if(!isEmpty()) return top.data;
    else return -1;
}

public void push(int data) {    // 스택에 데이터 추가
    Node node = new Node(data);
    if(!isEmpty()) {    // 빈 스택이 아니라면
        node.next = top;    // 현재 노드를 최상위 위치로 옮김.
    }
    top = node;     // 최상위 노드를 현재 노드로 설정
}

public int pop() {      // 스택의 최상위 원소 반환 및 제거
    if(isEmpty()) return -1;    // 빈 스택이라면 오류
    int data = top.data;        // 최상위 스택의 데이터 저장
    top = top.next;     // 최상위 스택의 다음 스택이 새로운 최상위 스택
    return data;
}

 

 

 

시간 복잡도

스택의 삽입이나 삭제시 맨 위의 데이터를 삭제하기 때문에 시간복잡도는 늘 O(1) 이다.

하지만 특정 데이터를 찾을때는 데이터를 찾을때까지 순차적으로 수행해야 하므로 O(n) 시간복잡도를 갖는다.

 

 

스택의 활용

1. 백 스페이스 키
2. 후위표현(Post-Fix Expression)의 연산
3. 진법 변환
4. 문자열 뒤집기
5. 괄호 매칭
6. 재귀 함수

 

 

 

[참고 자료]

C/C++로 배우는 자료구조론

https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95