Stack
Stack이란?
데이터(data)를 순서대로 쌓는 자료 구조
- 자료 구조 Stack의 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있음
- 이런 Stack 자료 구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 함
- Stack에 데이터를 넣는 것을 ‘PUSH’, 데이터를 꺼내는 것을 ‘POP’이라고 함
Stack의 특징
LIFO(Last In First Out)
먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조를 가지고 있음
데이터는 하나씩 넣고 뺄 수 있음
Stack 자료 구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺌.
한꺼번에 여러 개를 넣거나 뺄 수 없음
하나의 입출력 방향을 가지고 있음
Stack 자료 구조는 데이터의 입출력 방향이 같음
만약, 입출력 방향이 여러 개라면 Stack 자료 구조라고 볼 수 없음
Stack 자료 구조의 장점
1. 스택은 후입선출(LIFO) 구조를 가지기 때문에,
- 스택에 저장된 데이터를 가져오는 속도가 매우 빠름
후입선출(LIFO) 구조를 가지기 때문에, 삽입과 삭제가 항상 스택의 맨 위에서 이루어짐
이 과정은 스택의 크기와는 상관없이 항상 매우 빠르게 처리됨
데이터를 삽입, 삭제하는데 모든 데이터를 순회할 필요가 없기 때문
2. 자바에서는 스택을 기본 자료 구조로 제공하기 때문에,
- 별도의 라이브러리나 모듈을 설치할 필요가 없음
자바에서는 따로 스택을 구현하지 않아도 이미 Stack 클래스가 구현되어 있음
Stack 자료 구조의 단점
- 1. 크기 제한이 없음
데이터를 저장할 때 크기가 제한되지 않기 때문에, 메모리 사용량이 불필요하게 증가할 수 있음
이러한 문제를 해결하기 위해서는 스택의 크기를 미리 정해놓거나,
동적으로 크기를 조절하는 방법을 사용해야 함
2. Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어,
- 크기를 동적으로 조정하지 않습니다. (Java에서 제공하는 Stack 클래스 한정입니다)
이 배열의 크기는 처음에 지정된 크기만큼만 할당되고,
스택에 저장되는 데이터의 개수가 배열의 크기를 초과하면 새로운 배열을 할당하고,
기존 데이터를 새로운 배열로 복사하는 작업을 수행
이 작업은 성능에 영향을 미치기 때문에,
크기가 자주 변하는 스택에서는 다른 자료 구조를 사용하는 것이 더 효율적일 수 있습니다.
3. Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어,
- 중간에서 데이터를 삽입, 삭제를 할 수 있게 됩니다. (Java에서 제공하는 Stack 클래스 한정입니다)
stack 클래스에서는 Vector 클래스에서 상속받은 메서드 중에서
일부 메서드를 오버라이딩하여 구현하고 있습니다.
이러한 구현 방식은 스택의 의도된 동작을 방해할 수 있기 때문에,
해당 클래스를 사용할 때 주의가 필요합니다.
Stack 선언
import java.util.Stack;
Stack<자료형> 변수명 = new Stack<>();
자료형에 넣은 자료형만 삽입, 삭제 가능
Stack 변수명 = new Stack();
어떤 자료형이든 삽입, 삭제 가능(이전에 int형을 넣었어도 String형 삽입 가능)
1. 삽입
stack.push(삽입할 value);ㄴ 반환 값(삽입한 value의 자료형): 삽입한 value
stack.add(삽입할 value);- ㄴ 반환 값(boolean): true(성공) / false(실패; StackOverflow)*
2. 삭제
stack.pop();ㄴ 반환 값(삭제한 value의 자료형): 삭제한 value / 공백 스택일 때 Exception(“EmptyStackException”) 발생
stack.remove(index);- ㄴ 반환 값(삭제한 value의 자료형): 삭제한 value / 옳지 않은 index입력 시 Exception(“ArrayIndexOutOfBoundsException”) 발생*
(index는 삽입된 순서대로 0 ~ stack.size()-1)
3. 스택의 top에 있는 원소 반환
stack.peek();ㄴ 반환 값(top에 저장된 value 자료형): stack의 top에 저장된 값
4. 크기
stack.size();ㄴ 반환 값(int): 현재 스택에 저장된 value의 개수
5. 스택이 비어있는가?
stack.isEmpty();stack.empty();ㄴ 반환 값(boolean): 공백상태 true / 공백상태가 아닐 때 false
6. 스택 안에 해당 원소가 있는가?
stack.search(찾을 value);ㄴ 반환 값(int): top에서부터 몇 번째에 존재하는지? (1 ~ stack.size()) / 존재하지 않으면 -1
7. 스택 값 변경
stack.set(index, 변경할 value);ㄴ 반환 값(변경 전 value의 자료형): 변경 전 value / 옳지 않은 index 입력 시 Exception(“ArrayIndexOutOfBoundsException”) 발생
*(index는 삽입된 순서대로 0 ~ stack.size()-1)
8. 해당 인덱스에 존재하는 값 반환
stack.elementAt(index);ㄴ 반환 값(int): 해당 인덱스에 저장된 값 / 옳지 않은 index 입력 시 Exception(“ArrayIndexOutOfBoundsException”) 발생
*(index는 삽입된 순서대로 0 ~ stack.size()-1)
9. 스택 초기화(= 공백 스택 만들기)
stack.clear();ㄴ 반환 값(void): X