스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조로 되어 있으며, 데이터를 넣는 것을 Push, 데이터를 꺼내는 것을 Pop이라고 한다. 마지막에 들어간 것이 먼저 나온다는 후입선출(LIFO - Last In First Out)의 특징을 가지고 있다.
1. 배열로 Stack 구현
top은 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값이다. 데이터를 넣을 때 top은 위로 이동하고, 데이터를 꺼낼 때는 top이 아래로 이동하며, 최솟값으로 -1을 가지고 최댓값으로 배열의 마지막 index를 가진다.
* top의 변경 범위
-1 <= top <= array.length -1
1) Push
1. top을 1 증가
2. 증가된 top을 배열의 index로 접근하여 데이터를 삽입
2) Pop
1. top을 배열의 index로 접근하여 데이터를 먼저 꺼내고 임시 저장
2. top을 배열의 index로 접근하여 null을 저장
3. top을 1 감소
* null 값을 저장하는 이유
스택 인스턴스가 스택에 저장된 인스턴스를 참조하지 않게 하기 위함이다.
ArrayStack arrayStack = new ArrayStack(4);
arrayStack.push(new Person(...));
arrayStack.push(new Person(...));
arrayStack.push(new Person(...));
arrayStack.pop();
pop() 메서드 호출 시 인스턴스를 참조하지 않도록 null 값을 저장하면 참조할 수 없는 Person 인스턴스는 가비지 컬렉터에 의해 수집 대상이 된다.
결론적으로 가비지 컬렉터에 의해 수집 되도록 null 값을 저장한다.
Push와 Pop시 주의할 점
1. 데이터를 꺼낼 때 top이 -1인 경우는 데이터가 없다는 뜻으로, top을 이동시키면 안된다.
2. 데이터를 넣을 때 top이 배열의 마지막 index와 동일하면 스택이 꽉 찼다는 뜻으로 top을 이동시키면 안된다.
일반 배열로 구현 시 한계점
런타임(실행) 환경에서 스택에 넣어야 할 데이터가 배열의 크기보다 클 경우 스택의 공간을 늘릴 수 없기 때문에 미리 많은 메모리 공간을 사용하여 대응해야 하는데 사용하지 않을 경우 메모리 공간의 낭비가 발생한다. 이 문제를 해결하기 위해서는 가변 배열을 이용한 방식이나, 연결 리스트를 이용한 방식으로 대응해야 한다.
2. 리스트로 Stack 구현
top은 head와 동일하며, 항상 head가 가리키는 노드로 추가한다.
1) Push
1. 새로운 노드는 head가 가리키는 노드의 참조값을 저장
2. head는 새로운 노드의 참조값 저장
2) Pop
1. 삭제할 노드의 데이터를 임시 저장
2. head는 삭제할 노드의 다음 노드의 참조값을 저장
3. 삭제할 노드의 데이터에 null값을 저장하고, 삭제할 노드의 next 변수에도 null 값을 저장 (next 변수에 null 값을 저장하지 않아도 순환 참조가 아니기 때문에 가비지 컬렉터에 의해 처리됨)
Pop시 주의할 점
head가 null값인 경우는 데이터가 없다는 뜻으로 예외 처리를 해야 함
참조
https://www.codelatte.io/courses/java_data_structure
'6. 자료구조 & 알고리즘 > 6-1. 자료구조' 카테고리의 다른 글
자료구조 - [ 이진 트리 순회 ( 깊이 우선 / 너비 우선 ) ] (0) | 2022.08.10 |
---|---|
자료구조 - [ 재귀 - 점화식 관점 / 분할 관점 / 백트래킹 관점 ] (0) | 2022.08.08 |
자료구조 - [ Queue ] (0) | 2022.08.08 |
자료구조 - [ 이중 연결 리스트 ] (0) | 2022.08.06 |
자료구조 - [ 단일 연결 리스트 ] (0) | 2022.08.05 |