스택: 기본 개념과 구현

YeongJun Son·2024년 1월 6일

스택 자료구조

알고리즘을 배우다

목록 보기

3/6

들어가며

최초 작성일: 10/23 최초 작성

학습 목표

스택의 기본적인 개념과 연산을 이해한다.
자바의 제네릭을 이용해 스택 자료구조를 구현해본다.

학습 상황

단순히 자바에 있는 스택 클래스가 아니라, 그러한 스택 클래스가 어떻게 만들어지는지 고민해본다.
삼성 SW 역량테스트 B형에 대비해, 구현 과정에서도 stack interface를 implement하지 않는다.

스택: 기본 개념

스택(Stack)이란 무엇인가?

스택은 선입후출(LIFO, Last In First Out)이자 후입선출(FILO, First In Last Out)을 특징으로 합니다.
- 쉽게 생각해서: 식당 내 티슈통과 같은 방식으로 쓰이는 자료구조라고 생각하면 됩니다.
  
  Fig 1. 스택의 기본 구조
  출처: geeksforgeeks.com
- 따라서, 포인터가 항상 스택의 최상위에(즉, 가장 나중에 들어온 대상에) 있습니다.
스택의 종류
1. 고정 크기 스택(Fixed Size Stack)
  
  말 그대로, 스택이 크기가 자바 배열처럼 고정되어 있다고 보면 편합니다. 스택이 가득 차 있다면 오버플로우를, 스택이 비어있다면 언더플로우를 고려해야 합니다.
2. 동적 크기 스택(Dynamic Size Stack)
  
  요소의 추가나 삭제에 따라 스택의 크기가 줄어들거나 늘어날 수 있습니다. 연결 리스트(linked list)를 이용해 구현할 수 있습니다.

Fig 1. 스택의 기본 구조

출처: geeksforgeeks.com

스택의 기본 연산

💡 스택에서 최상위 요소가 항상 가장 나중에 들어온 요소임을 고려하면 이해가 쉽습니다.

push()
- 요소를 스택에 넣습니다. 따라서, 가장 나중에 들어온 요소가 최상위에 위치하게 됩니다.
- 스택이 가득 차 있다면, 요소가 더 넣을 수 없음을 감안해야 합니다.
pop()
- 요소를 스택에서 제거합니다. 따라서, 최상위 요소가 제거됩니다.
- 스택이 비어있다면, 요소를 더 뺄 수 없음을 감안해야 합니다.
peek()
- 스택의 최상위 요소를 반환합니다.
- 비어있을 때의 반환값을 고려해야 합니다.
isEmpty()
- 스택이 비어있는지 확인하며, boolean 값을 반환합니다.
size()
- 스택의 크기를 반환합니다.

복잡도

push(), pop(), top(), isEmpty(), size() 모두: O(1)
- 순회나 검색을 거치지 않으므로 O(1)의 시간 복잡도를 가집니다.

스택 구현: 자바

배열을 이용한 스택

 /* 코드는 수정될 수 있으며,
    참고한 코드는 참고자료 항목에 작성해두었습니다.
    코드는 수정될 수 있습니다.

	최초 작성일(yy/mm/dd): 2024/01/06    
    최종 수정일(yy/mm/dd): 2024/01/06 */

class ArrayStack<T> {
    private T[] elements;
    private int top;

    public ArrayStack(int initialCapacity) {
        elements = (T[]) new Object[initialCapacity];
        top = -1;
    }

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

    public boolean isFull() {
        return (top == elements.length-1);
    }

    public void push(T theElement) {
        if (isFull()) {
            throw new IllegalStateException("Stack is full");
        } else {
            top++;
            elements[top] = theElement;
        }
    }

    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        } else {
            T removedElement = elements[top];
            elements[top] = null;
            top--;
            return removedElement;
        }
    }

    public T peek() {
        if (isEmpty()) return null;
        return elements[top];
    }

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

연결 리스트를 이용한 스택

 /* 코드는 수정될 수 있으며,
    참고한 코드는 참고자료 항목에 작성해두었습니다.
    코드는 수정될 수 있습니다.
    
	최초 작성일(yy/mm/dd): 2024/01/06
    최종 수정일(yy/mm/dd): 2024/01/06 */

class ListStack<T> {

    private Node<T> top;
    private int size;
    
    private static class Node<T> {

        T data;
        Node next;
        
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
    
    public ListStack() { 
        this.top = null;
        this.size = 0;
    }

    public boolean isEmpty() { return size == 0; }

    public void push(T theElement) {
        Node<T> newNode = new Node<>(theElement);
        newNode.next = top;
        top = newNode;
        size++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }

        T removedElement = top.data;
        top = top.next;
        size--;
        return removedElement;
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }

    public int size() {
        return size;
    }

}