Stack

스택(Stack)이란?

마지막에 넣은 것이 가장 먼저 나오는 자료구조로 LIFO(Last in, First Out)라고 부른다.

 

가장 좋은 비유는 접시 쌓기로, 접시를 쌓을 때는 위에서부터 하나씩 쌓고, 꺼낼 때도 맨 위에 있는 것부터 꺼내기 떄문에, 맨 밑에 있는 접시를 꺼내려면 위에 있는 걸 다 치워야 합니다.

 

스택의 핵심 연산

연산 의미 시간복잡도

push	맨 위에 데이터 추가	O(1)
pop	맨 위 데이터 꺼내면서 제거	O(1)
peek (또는 top)	맨 위 데이터를 제거 없이 확인만	O(1)
isEmpty	비어있는지 확인	O(1)

 

왜 항상 O(1)인가?

배열이었다면 맨 앞에 넣고 뺼 떄마다 전체를 밀어야 했지만, 스택은 항상 "맨 위(head)"에서만 작업하니 연결 리스트의 추가/삭제 방식과 완벽하게 맞아떨어진다.

 

 

class Node<E> {
	E data;
    Node<E> next;
    Node(E data) { this.data = data; }
}

class StackEx<E> {
	private Node<E> top; // 맨 위를 가리키는 참조
    private int size = 0;
    
    // push : 맨 위에 새 노드를 얹음 -> O(1)
    public void push(E value) {
    	Node<E> newNode = new Node<>(value);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    // pop : 맨 위 노드를 꺼내면서 제거 -> O(1)
    public E pop() {
    	if(isEmpty()) {
        	throw new RuntimeException("스택이 비어있습니다.");
        }
        
        E value = top.data;
        top = top.next;
        size--;
        return value;
    }
    
    // peek : 맨 위 값만 확인, 제거는 안 함 -> O(1)
    public E peek() {
    	if (isEmpty()) {
        	throw new RuntimeException("스택이 비어있습니다.");
		}
    	return top.data;
    }
    
    public boolean isEmpty() {
    	return top == null;
    }
    
    public int size() {
    	return size;
	}
    
}

public class StackEx {
	public static void main(String[] args) {
    	StackEx<Integer> stack = new StackEx<>();
        
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("맨 위 값 확인: " + stack.peek()); // 30 (제거 안 됨)
        
        System.out.println("pop: " + stack.pop()); // 30
        System.out.println("pop: " + stack.pop()); // 20
        System.out.println("pop: " + stack.pop()); // 10

        System.out.println("비어있나? " + stack.isEmpty()); // true
    }
}

 

참고

실무에서는 Stack 클래스보다 Deque 인터페이스의 ArrayDeque를 스텍으로 쓰는 게 더 권장된다.