스택이란?
스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형 자료구조이다.
기본적으로 Stack 클래스는 내부에서 최상위 타입 배열인 Object[] 배열을 사용하여 데이터를 관리하고 있다.
스택의 작동원리
스택은 기본적으로 후입선출(나중에 들어온 데이터가 가장 먼저 나가는) 구조로 이루어져 있다.
위의 그림을 보면 가장 먼저 들어온 a 데이터가 가장 마지막에 쌓여있고 가장 나중에 들어온 c 데이터가 가장 위에 놓여져 있다. 데이터를 넣고 빼는 입구가 하나뿐인 스택은 가장 위에 쌓인 데이터를 먼저 꺼내도록 작동한다.
스택 제공 연산 종류
pop(): 스택에서 가장 위에 있는 항목을 제거한다.push(item): item 하나를 스택의 가장 윗 부분에 추가한다.peek(): 스택의 가장 위에 있는 항목을 반환한다.isEmpty(): 스택이 비어 있을 때true를 반환한다.
스택의 구조
스택은 아래 그림과 같은 구조로 이루어져 있다.
Bottom : 가장 밑에 있는 데이터 또는 인덱스
Top : 가장 위에 있는 데이터 또는 인덱스
Capacity : 스택에 담을 수 있는 데이터의 총 용량
Size : 현재 스택에 담겨져있는 데이터의 개수
스택 구현
public class MyStack<E> {
private static final Object[] EMPTY_ARRAY = {};
private static final int DEFAULT_SIZE = 10;
private Object[] array;
private int size;
public MyStack() {
this.array = EMPTY_ARRAY;
this.size = 0;
}
public MyStack(final int capacity) {
this.array = new Object[capacity];
this.size = 0;
}
private void resize() {
if (Arrays.equals(array, EMPTY_ARRAY)) {
array = new Object[DEFAULT_SIZE];
return;
}
int arrayCapacity = array.length;
if (size == arrayCapacity) {
int newSize = arrayCapacity * 2;
array = Arrays.copyOf(array, newSize);
return;
}
if (size < arrayCapacity / 2) {
int newSize = arrayCapacity / 2;
array = Arrays.copyOf(array, Math.max(DEFAULT_SIZE, newSize));
}
}
public E push(E item) {
if (size == array.length) {
resize();
}
array[size] = item;
size++;
return item;
}
public E pop() {
if (size == 0) {
throw new EmptyStackException();
}
@SuppressWarnings("unchecked")
E object = (E) array[size - 1];
array[size - 1] = null;
size--;
resize();
return object;
}
@SuppressWarnings("unchecked")
public E peek() {
if (size == 0) {
throw new EmptyStackException();
}
return (E) array[size - 1];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
}위 코드에서 생성자를 2개 생성하였는데 첫 번째 생성자의 경우는 아래 코드와 같은 상태일 때이다.
Stack<String> stack = new Stack<>();두 번째 생성자는 데이터 개수가 정해져있어 미리 스택의 크기를 정해놓고 싶을 경우이다. 아래 코드와 같다.
Stack<String> stack = new Stack<>(50);동적 할당을 위한 resize 메소드
private void resize() {
if (Arrays.equals(array, EMPTY_ARRAY)) {
array = new Object[DEFAULT_SIZE];
return;
}
int arrayCapacity = array.length;
if (size == arrayCapacity) {
int newSize = arrayCapacity * 2;
array = Arrays.copyOf(array, newSize);
return;
}
if (size < arrayCapacity / 2) {
int newSize = arrayCapacity / 2;
array = Arrays.copyOf(array, Math.max(DEFAULT_SIZE, newSize));
}
}
public E push(E item) {
if (size == array.length) {
resize();
}
array[size] = item;
size++;
return item;
}동적 할당을 하는 이유는 만약 데이터가 적은데 해당 자료구조(여기서는 스택)의 크기가 크다면 메모리가 낭비되고, 반대로 자료구조의 크기가 데이터보다 작다면 데이터들을 보관할 수 없는 상태가 된다.
따라서 데이터의 개수 size 를 파악하고 적절한 크기에 맞게 배열의 크기를 변경해야 한다. 또한 외부에서 마음대로 접근하면 데이터의 손상을 발생시킬 수 있으므로 private 접근 제어자로 외부에서의 접근을 차단하도록 한다.
Arrays.copyOf(): 첫 번째 값 복사할 배열, 두 번째 값 배열의 크기를 입력하면 된다. 데이터를 추가하고 남은 공간은null이 자동으로 입력된다.Arrays.equals(): 주소가 아닌 값을 비교한다.
데이터 입력 메서드 - push 메서드
스택에 데이터를 추가하는 작업은
push()로 이루어진다.
Stack에 데이터를 추가하면 가장 마지막 부분(최상단)에 추가된다. 스택에 데이터를 추가하는 push 작업은 인덱스를 증가하면서 이루어진다.
자바에서 push 메서드는 추가된 데이터를 리턴하기 때문에 E 타입을 반환하는 메소드로 구현.
public E push(final E item) {
// 크기가 꽉 차있다면 크기를 늘려 재할당한다.
if(size == array.length){
resize();
}
array[size] = item; // 마지막 위치에 요소 추가
size++; // 사이즈 1 증가
return item;
}동적 할당을위해 array 크기를 확인한 후 재할당하는 기능을 추가했다.
데이터 삭제 메서드 - pop 메서드
스택에 데이터를 삭제하는 작업은
pop()으로 이루어진다.
스택에 데이터를 삭제하는 작업은 가장 위에 있는(가장 마지막에 추가된 데이터) 마지막 데이터를 제거한다.
데이터 삭제시 중요한 점은 스택이 비어있어 삭제할 데이터가 없는 경우이다.
public E pop() {
if(size == 0){
throw new EmptyStackException();
}
@SuppressWarnings("unchecked")
E obj = (E) array[size -1]; // 삭제될 요소를 반환하기 위한 임시 변수
array[size -1] = null; // 요소 삭제
size--; // 사이즈 1 감소
resize(); // 크기 재할당
return obj;
}SuppressWarnings("unchecked")
형 변환시 변환할 수 없는 타입일 가능성이 있다는 경고를 무시하겠다는것을 의미한다.
@SuppressedWarnings("uncheck") 를 붙이지 않으면 type safe(타입 안정성)에 대해 경고를 보낸다.
위 코드에서 Object -> E 타입으로 타입을 변환하고 있는데 이 과정에서 변환할 수 없는 타입일 가능성이 있다는 경고로 메소드에 경고표시가 뜬다. 하지만, 우리가 push하는 데이터는 유일하게 E 타입만 존재한다. 그렇기 때문에 형 안정성이 보장된다.
한마디로 ClassCasetException이 뜨지 않으니 이 경고를 무시하겠다는것을 의미한다.
@SuppressedWarnings("uncheck") 는 남발해서는 안되고 형 변환시 예외 가능성이 없을 확실한 경우에만 최소한의 범위안에서 사용하는것이 좋다.
최상단 데이터 확인 메소드 - peek 메서드
peek()는 가장 상단에 있는 데이터를 삭제하지않고 확인만 하고 싶을때 사용하는 메서드이다.
pop() 에서 삭제과정만 없는 것이 peek() 이다.
@SuppressWarnings("unchecked")
public E peek() {
// 삭제할 요소가 없다면 Stack 이 비어있다는 의미이므로 예외를 발생시킨다.
if (size == 0) {
throw new EmptyStackException();
}
return (E) array[size - 1];
}pop() 과 마찬가지로 마지막 원소를 반환하는 과정에서 Object 타입을 E 타입으로 변환하면서 경고창이 뜬다. 역시 @SuppressedWarnings("uncheck") 를 이용해서 경고를 무시한다.
또한, 마지막 원소의 인덱스는 size 보다 1이 작기 때문에 이점을 주의해야한다.
데이터 유무 확인 메서드 - isEmpty 메서드
isEmpty()는 Stack이 비어있는지 확인하는 메서드이다.
Stack이 비어있으면 true 저장된 데이터가 있으면 false를 반환하는 메서드이다.
public boolean isEmpty() {
return size == 0;
}size 만 0인지 검사하여 값만 반환해주면 된다.
스택 시간복잡도
스택은 상수 시간에
i번째 항목에 접근할 수 없다. 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
스택의 삽입이나 삭제시 맨 위의 데이터를 삭제하기 때문에 시간복잡도는 늘 O(1) 이다. 하지만 특정 데이터를 찾을때는 데이터를 찾을때까지 순차적으로 수행해야 하므로 O(n) 시간복잡도를 갖는다.
스택의 활용
스택이 유용한 경우는 재귀 알고리즘을 사용할 때다.
재귀적으로 함수를 호출하는 경우에 임시 데이터를 스택에 넣어 주고, 빠져 나와 백 트래킹을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 주는 형식으로 사용하면 된다.
또한 스택은 재귀 알고리즘을 반복적 형태를 통해서 구현할 수 있게 해준다.
스택 활용 - 함수호출
프로그래밍에서의 함수 호출과 복귀에 따른 순서를 관리
재귀에 따른 함수 호출을 생각해 보면 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행 순서를 관리한다.
함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다.
함수의 실행이 끝나면 시스템 스택의 top원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어 있던 복귀 주소를 확인하고 복귀한다.
함수 호출과 복귀에 따라 이 과정을 반복하면서 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.
스택활용 - 기타
- 괄호의 짝 검사
- 괄호의 짝, 괄호의 순서 검사.
- 웹 브라우저 방문기록(뒤로 가기)
- 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기
- 가장 나중에 입력된 문자부터 출력한다.
- 실행 취소(undo)
- 가장 나중에 실행된 것부터 실행을 취소한다.
- 수식의 괄호 검사
- 연산자 우선순위 표현을 위한 괄호검사.
[Reference]
st-lab
포스트it 의 개발자 도전기
resize를 이렇게 할 수 있군요.. 좋은 글 감사합니다