[Data Structure기초] Stack

Study for Backend/Data Structure

[Data Structure기초] Stack

지미니박 2024. 2. 19. 23:01

Stack (스택)

- 데이터를 차곡차곡 쌓아올린 형태, 선형 자료구조

- 가장 마지막에 삽입된 자료가 가장 먼저 삭제됨 (Last In First Out , 후입선출)

- 정해진 방향으로 쌓을 수 있고 top 으로 정한 곳을 통해서만 접근 가능

- 문서 편집기에서 undo 기능을 구현할 때 stack 을 사용

Stack 시간복잡도

삽입(Push) : O(1)
삭제(Pop) : O(1)
읽기(Peek) : O(1)
탐색(Search) : O(n)
접근(Access) : O(n)

연산
push()	삽입. 스택이 가득 차 있으면 오류 발생 후 종료 , 공간이 있으면 top 증가 시킨 후 데이터 추가
pop()	삭제. 스택이 비어있으면 오류 발생 후 종료 , 스택이 비어있지 않으면 top 이 가리키는 데이터를 제거, top 감소
peek()	데이터 확인. top이 가리키고 있는 데이터를 조작없이 읽기만 함
isEmpty()	공간 유무 확인. 스택이 비어있으면 true, 비어있지 않으면 false
size()	스택 크기 리턴.
contains()	특정 value 포함 여부 확인. 포함하면 true 포함하지 않으면 false
search()	value의 위치를 반환. value가 여러개면 마지막 위치를 반환하고 찾는 값이 없으면 -1을 반환

//스택 사용예제
Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(0);     // stack에 값 0 추가
stack.push(1);     // stack에 값 1 추가
stack.size();      // stack의 크기 출력 : 1 
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(0)  // stack에 0 이 있는지 check (있다면 true)

장점

- 스택에 저장된 데이터를 가져오는 속도가 매우 빠르다.
데이터를 삽입, 삭제하는데 모든 데이터를 순회할 필요가 없기 때문이다.

- 자바에서는 스택을 기본 자료 구조로 제공

단점

- Thread-safe

멀티스레드 환경이 아닐 때 사용하면 lock 거는 작업때문에 오버헤드가 발생할 수 있다.

- 스택 오버플로우가 발생할 수 있다.
스택은 한계가 있어서, 요소를 계속해서 푸시하면 스택 오버플로우(Stack Overflow) 오류가 발생할 수 있다.
- 메모리를 관리하는데 부담이 될 수 있다.
스택에 데이터를 저장하는 동안 메모리를 사용하게 되며, 스택 오버플로우를 방지하기 위해 충분한 메모리를 확보해야 한다.

- 초기 용량 설정을 할 수 있는 생성자가 없어서 삽입이 많으면 배열을 복사해야하는 일이 빈번하게 발생한다.