Stack

Dave.kim·2024년 2월 21일

스택 자료구조

자료구조

목록 보기

1/2

스택이란?

스택(Stack)이란, 어떤 데이터를 쌓아 올린 형태의 자료구조이다.
박스 안에 책을 쌓아두고, 꺼내는 행위를 스택의 구조와 연산들과 대비해 생각해보면 됩니다.

스택의 특징

후입선출( Last In First Out, LIFO ) 자료구조
데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용합니다.
스택이 비어있을 때 데이터를 꺼내려는 시도를 하면 스택 언더플로우(Stack Underflow)가 발생하며
스택이 꽉 차 있을때 데이터를 넣으려는 시도를 하면 스택 오버플로우(Stack Overflow)가 발생하게 됩니다.

스택의 활용 예시

계산기의 수식 계산 (후위 표기법 계산)
함수 콜 스택 (재귀, 함수 콜백)
인터럽트 처리
깊이 우선 탐색(DFS)

스택의 작동원리

Stack 사용법 (Java)

자바에서는 java.util.Stack을 import하여 사용할 수 있다.
일반적인 동작은 두가지가 있는데,

push : 스택에 데이터를 추가하는 동작
pop : 스택에서 데이터를 빼오는 동작

Coding (Java)

import문

import java.util.Stack;

Stack 선언

class Main{
	public static void main(String[] args){
    	Stack<Integer> intStack = new Stack<>(); // Integer형 스택
        Stack<String> stringStack = new Stack<>(); // String형 스택
        Stack<Boolean> booleanStack = new Stack<>(); // Boolean형 스택
    }
}

일반적으로 스택의 선언은 Stack<T> 스택 이름 = new Stack<>(); 형태로 선언할 수 있으며, 데이터 타입은 클래스 또는 래퍼 클래스로 선언할 수 있다.
ex) Stack<School> exStack = new Stack<>();

Stack 요소 넣기

Object push(Object item) : Stack에 객체(item)를 저장한다

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack); // [1, 2, 3]

Stack 요소 꺼내기

Object pop() : Stack의 맨 위에 저장된 객체를 꺼낸다
- 비어있을 경우 EmptyStackException 발생

System.out.println(stack.pop()); // 3
        
System.out.println(stack); // [1, 2]

System.out.println(stack.pop()); // 2
System.out.println(stack.pop()); // 1

System.out.println(stack); // []

Stack 최상단 요소 가져오기

Object peek() : Stack의 맨 위에 저장된 객체를 반환한다
- pop()과 달리 Stack에서 객체를 꺼내지는 않는다
- 비어있을 경우, EmptyStackException 발생

stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek()); // 3

Stack 공간 비어있는지 확인

만약에 스택에 데이터가 존재하지 않는 상황에서, pop이나 peek을 하게 되면 EmptyStackException 예외가 발생하게 된다. 따라서 항상 메서드 호출 시에 스택에 데이터가 존재하는지 확인해야 한다.

Stack<Integer> stack = new Stack<>();
stack.push(1);

// 스택이 비어있지 않다면 안전하게 요소를 제거
if(!stack.isEmpty() {
	stack.pop();
}

Stack 사이즈

Stack 클래스는 Vector 클래스를 상속했으며, Vector 클래스는 List 인터페이스를 구현하므로 size() 메서드를 사용할 수 있다.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.size()); // 3

Stack 시간복잡도

삽입 : O(1)
삭제 : O(1)
탐색 : O(N)

기술면접

예전에 타 기업 기술면접 질문으로, M개의 데이터가 있다고 가정했을때, Vector에 Push Back을 하게되면 내부적으로 어떻게 추가될까? 라는 질문을 받은적이 있다.
- 난 여기서 "Vector는 배열 메커니즘으로 데이터를 저장하는데, 데이터가 추가될 때마다 해당 배열의 용량을 검사하여 필요한 경우 용량을 늘립니다 -> (좀 더 상세히 설명..)" 이렇게 설명을 했었다. 물론 해당 기술면접은 합격했지만, 이 질문에 대한 답변으로 정확한지는 모른다.
Stack은 메모리에도 존재한다. 스택&힙은 몰라서는 안되는, 기초중의 기초지식이다.

핵심은..

Stack 클래스의 경우 ArrayList, Vector 처럼 동적 구현체라 별도의 사이즈를 명시하지 않아도 된다.
- 처음 스택이 생성되었을때 10개의 데이터를 저장할 수 있는 공간이 할당된다.
- push() 메소드를 통해 요소가추가되어 10개가 넘어가면, 현재 스택 사이즈의 2배에 해당하는 공간을 할당하고 기존 데이터를 복사하게 된다.

참고

Dave.kim

다음 포스트