[자료 구조] 스택(Stack) - 단일 연결 리스트와 배열을 이용한 스택, Java 구현

스택 자료구조에 대해 알아보고 java로 구현해 봅시다.

 

• 자료구조, 알고리즘 시리즈 모아보기

 

스택

`스택(stack)`은 이름 그대로 자료를 쌓아 놨다고 생각하는 `추상 자료 유형(Abstract Data Type)`입니다. 흔히 프링글스, 팬케이크로 예시를 듭니다. 가장 마지막에 프링글스 통에 넣은 프링글스 칩, 가장 마지막에 쌓은 팬케이크는 바로 먹을 수 있지만 가장 예전에 넣은(처음 넣은) 것은 꺼내기 힘듭니다. 스택은 위 예시와 같이 마지막에 넣은 것이 처음으로 나오는 `LIFO(Last In First Out)`구조로 최신 순으로 자료에 접근이 가능합니다.

출처: https://cloer.tistory.com

- 연산

스택은 추상 자료 유형으로 다음과 같은 연산(행위)으로 정의됩니다. 스택은 크게 push와 pop이라는 두 개의 연산으로 정의됩니다. 추가적으로 peek 연산도 있습니다.

• push: 새로운 요소를 자료 구조에 추가
• pop: 자료 구조에 저장되어 있는 요소 중 가장 최근에 저장된 요소를 삭제
• + peek: 자료구조의 변경 없이 저장되어 있는 요소 중 가장 최근에 저장된 요소를 확인

- 사용

스택은 연산에서 알 수 있듯 가장 최근에 저장한 자료를 사용할 때 사용됩니다. 

• 웹 브라우저 뒤로 가기(가장 최근에 방문한 페이지)
• 에디터의 실행 취소(가장 최근에 한 행위)
• 후위 표기법 (스택을 이용한 후위 표기법 연산 과정 예시)

 

Java 구현

스택은 배열 혹은 연결 리스트로 구현할 수 있습니다. 연결 리스트를 이용한 구현은 저번 포스트에서 구현한 단일 연결 리스트를 사용하겠습니다.

JDK에서 Stack 클래스로 스택의 구현체를 제공합니다. Stack 클래스는 벡터를 상속받아 만들어 졌습니다. (open JDK Stack 클래스 코드)

- 연결 리스트 이용

Stack 인터페이스를 정의 하고 연결 리스트로 구현하는 방법입니다. JDK에서 제공되는 LinkedList를 사용해도 되지만 앞서 만들었던 SinglyLinkedList에 push, pop, peek을 추가해 사용해도 됩니다. push, pop, peek의 구현은 각각 SinglyLinkedList의 addFirst, removeFirst, getFirst와 같습니다. 따라서 모두 𝛩(1)의 시간 복잡도를 갖습니다.

interface Stack<E> {
    public void push(E element);
    public E pop();
    public E peek();
}

- 배열 이용

배열은 가장 앞 요소의 추가, 삭제 시 뒤 요소들을 한 칸씩 밀어야 하기 때문에 𝛩(n)의 시간 복잡도를 갖습니다. 하지만 가장 끝 요소의 위치를 기억하고 있고 가장 끝에 요소를 추가, 삭제한다면 𝛩(1)의 시간 복잡도로 스택을 구현할 수 있습니다.

import java.util.StringJoiner;

class Stack<E> {
    private final int DEFAULT_CAPACITY = 32;
    private E[] buckets;
    private int capacity;
    private int size = 0;
    
    public Stack() {
        this.capacity = DEFAULT_CAPACITY;
        this.buckets = (E[]) new Object[DEFAULT_CAPACITY];
    }

    private void resize(int newCapacity) {
        E[] newBuckets = (E[]) new Object[newCapacity];
        for(int i=0; i<size; i++)
            newBuckets[i] = buckets[i];
        buckets = newBuckets;
        capacity = newCapacity;
    }
    private boolean isFull() {
        return size == capacity;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() { return size; }
    
    // Stack method: push
    public void push(E element) {
        if(isFull()) 
            resize(capacity * 2);
        
        buckets[size++] = element;
    }
    
    // Stack method: pop
    public E pop() {
        if(isEmpty())
            return null;
        return buckets[--size];
    }

    // Stack method: peek
    public E peek() {
        if(isEmpty())
            return null;
        return buckets[size - 1];
    }

    @Override
    public String toString() {
        StringJoiner sj = new StringJoiner(", ","(new) "," (old)");
        for(int i=size-1; i>=00; i--)
            sj.add(buckets[i].toString());
        return sj.toString();
    }
}