[자료구조] 스택(Stack)이란?

스택의 개념

• 스택은 '쌓다'와 같은 뜻을 가진 용어로, 접시를 쌓아 놓은 형태와 비슷한 자료구조
  • 즉, 데이터를 순서대로 쌓는 자료구조
• 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 후입선출(LIFO: Last In First Out) 구조
  • 가장 마지막에 들어온 데이터를 먼저 처리할 때 사용
• 사용처
  
  • 웹 브라우저의 '뒤로가기'
  • 실행 취소(뒤돌리기)의 'undo'
  • 수식 계산 또는 수식 괄호 검사
  • ...

 

스택의 특징

• 후입선출(LIFO) 구조
  • 가장 늦게 들어온 데이터가 제일 먼저 빠져나가는 구조
• 단방향 입출력 구조
  • 데이터가 들어오는 방향과 나가는 방향이 같음
  • 정해진 방향으로만 쌓을 수 있음
• 데이터를 하나씩만 넣고 뺄 수 있음
• 깊이 우선 탐색(DFS)에 이용
• 재귀 함수의 동작 흐름과 같은 구조를 가짐

 

자바에서 스택 사용하기

메서드	설명
Stack<E> stack = new Stack<>();	Stack 선언하기
E push(E item)	Stack에 객체(item)를 저장한다.
E pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. 비어있을 경우, EmptyStackException이 발생한다.
E peek()	Stack의 맨 위에 저장된 객체를 반환한다. pop()과 달리 객체를 꺼내지 않는다. 비어있을 경우, EmptyStackException이 발생한다.
boolean empty()	Stack이 비어있는지 알려준다.
int Search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환한다. 못 찾을 경우 -1을 반환한다. 배열과 달리 위치는 1부터 시작한다. (0이 아니다!)
int size()	Stack에 저장된 객체의 수를 반환한다. 참고로 Vector 클래스의 메서드이다. (∵ Stack 클래스는 Vector 클래스 상속받음)

 

예시

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        // 스택 선언하기
        Stack<Integer> stack = new Stack<>();

        // 객체 저장하기
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 객체 꺼내기
        System.out.println(stack.pop()); // 3
        System.out.println(stack.pop()); // 2

        // 맨 위에 저장된 객체 찾기
        System.out.println(stack.peek()); // 1

        // 스택이 비었는지 확인
        System.out.println(stack.isEmpty()); // false

        // 주어진 객체 찾기
        System.out.println(stack.search(1)); // 1

        // 객체 꺼내기
        System.out.println(stack.pop()); // 1

        // 스택이 비었는지 확인
        System.out.println(stack.isEmpty()); // true
    }
}

 

Vector 클래스를 상속받는 자바의 스택

자바의 스택은 Vector 클래스를 상속받는다. 그래서 Vector의 특징인 Thread-Safe하다는 특징을 스택도 가진다. 

 

그러나 Vector의 문제점이 존재해서 가급적으로 Vector와 Stack을 사용하지 않는 것이 좋다. 아직 사용하는 사람들이 있어 Deprecated 되지는 않았지만, 자바 공식 문서에도 Stack 클래스보다 Deque 클래스를 사용할 것을 권장하고 있다.

 

※ Deprecated란? 앞으로 지원되지 않을 것이니 사용을 자제해달라는 의미

 

Vector의 문제점

Vector의 주요 메서드들은 synchronized 키워드를 달고 있다. synchronized 키워드는 멀티쓰레드 환경에서 두 개 이상의 쓰레드가 하나의 변수에 동시에 접근할 때 경쟁 상태(Race condition)가 발생하지 않도록 한다. 즉, 주요 메서드들이 각각 동기화를 진행한다.

public synchronized boolean add(E e) {}

public synchronized void addElement(E obj) {}

public synchronized E get(int index) {}

 

동기화를 진행하니까 멀티쓰레드 환경에서 안전하고 좋을 것이라고 생각할 수 있다. 그러나 메서드를 호출하는 과정에서 락을 얻는 과정이 일일이 수행된다. 따라서 동기화가 되어 있지 않은 ArrayList와 성능 차이가 발생한다. 

 

Vector와 ArrayList의 성능 차이

	테스트 1	테스트 2
실행 결과

 

import java.util.ArrayList;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Vector<Integer> vector = new Vector<>();
        long beforeTime = System.currentTimeMillis();
        for (int i = 0; i < 10_000_000; i++) {
            vector.add(i);
        }
        long afterTime = System.currentTimeMillis();
        System.out.println("Vector add() 소요 시간: " + (afterTime - beforeTime) + "ms");

        ArrayList<Integer> arrayList = new ArrayList<>();
        beforeTime = System.currentTimeMillis();
        for (int i = 0; i < 10_000_000; i++) {
            arrayList.add(i);
        }
        afterTime = System.currentTimeMillis();
        System.out.println("ArrayList add() 소요 시간: " + (afterTime - beforeTime) + "ms");

        System.out.println();

        beforeTime = System.currentTimeMillis();
        for (int i = 0; i < 10_000_000; i++) {
            vector.get(i);
        }
        afterTime = System.currentTimeMillis();
        System.out.println("Vector get() 소요 시간: " + (afterTime - beforeTime) + "ms");

        beforeTime = System.currentTimeMillis();
        for (int i = 0; i < 10_000_000; i++) {
            arrayList.get(i);
        }
        afterTime = System.currentTimeMillis();
        System.out.println("ArrayList get() 소요 시간: " + (afterTime - beforeTime) + "ms");
    }
}

 

Stack의 문제점

Stack 자체적으로도 부족한 점이 존재한다.

1. 용량에 대한 설정이 불가능하다.
   • 스택은 오로지 하나의 생성자만을 가지며 용량에 대한 설정이 불가능해서 Vector의 초기 용량인 10을 사용한다.
   • 따라서 크기가 큰 스택을 자주 생성해서 사용할 경우, 배열을 복사하는 일이 빈번하게 일어날 수 있어 성능적으로 손해를 볼 수 있다.
   • 반면에 ArrayDeque는 생성자를 통해 Array의 크기를 지정할 수 있다.
2. LIFO 구조 위반
   • 스택 구조상, 데이터는 최상단을 통해서만 저장되어야 한다.
   • 그러나 Vector 클래스를 상속받기 때문에, add(int index, E element) 메서드를 통해서 원하는 위치에 자유롭게 저장할 수 있다.

 

스택 대신 사용할 것

• LIFO 기능을 사용하고자 할 때, 단일 스레드에서는 ArrayDeque를 사용하자.
  • 불필요한 동기화 없이 offerLast()와 pollLast() 메서드로 Stack 기능을 완벽히 대체할 수 있다!

---

참고

https://ittrue.tistory.com/200

https://jaehee329.tistory.com/27

https://velog.io/@soyoungdl/%EC%8A%A4%ED%83%9D-%ED%81%90-%EC%82%AC%EC%9A%A9-%EC%82%AC%EB%A1%80

https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-Stack-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%A0%95%EB%A6%AC