Stack 자료구조를 구현해 보자.
Stack은 LIFO. 후입선출인 자료구조이다.
스택에서는 배열과 tos(Top Of Stack)이라는 인스턴스 변수가 선언되어야 한다.
tos가 필요한 이유
스택은 후입 선출이다. 늦게 저장된 데이터를 우선순위로 빼내어준다.
후에 배울 Queue와는 반대되는 개념의 자료구조이다.
그러므로 Front, Rear 변수를 만들어 앞 뒤 연산을 지원하는 Queue와는 달리 Stack은 마지막에서 연산이 발생하기 때문에 tos가 필요하다.
나는 tos를 size로 대체했다.
tos와 size의 차이점은 tos는 마지막 요소의 인덱스를 가르키고 size는 요소의 총 갯수를 의미한다. 그러므로 tos = size - 1 이다.
resize 함수
스택을 배열로 구현하기 때문에 resize함수가 필요하다.
공간이 부족하면 늘려주고, 반대로 너무 많다면 줄여준다.
구현중에 주의할 점은 만약 resize함수로 배열의 사이즈가 어디까지 줄여질 수 있냐는 것이다.
1. 최대길이
최대길이는 당연히 index의 타입인 int의 최대 길이일 것이다.
만약 사이즈가 넘어버린다면 예외처리를 해줘야 한다.
그리고 그 예외를 막기 위한 방법을 생각해봤다.
int의 최대 사이즈를 넘는다면 인덱스의 타입을 long으로 바꾸면 해결되지 않을까 라는 생각을 해봤는데 당연히 안됐다.
배열의 생성자로 받는 size는 무조건 int형이다. long을 받을 수 없다.
2. 최소길이
최소길이는 0까지 바뀔 수 있다.
정확히는 resize 함수로 0까지 바뀌는 것이 아니라 clear함수나 생성자의 호출로 인한 초기 상황이다.
배열의 길이를 늘려줄 때 나는 size2의 길이로 늘려줬다.
근데 만약 초기상황같이 size가 0이라면?
배열의 길이가 늘어나지 않을 것이다.
그래서 (size 2)와 64를 대소비교하여 할당되는 사이즈가 64보다 크게 했다.
3. resize가 호출되는 시점
그렇다면 resize함수가 호출되는 시점은 언제일까?
당연히 배열의 사이즈가 바뀔 때 해야한다.
Stack에서는 배열의 사이즈가 바뀌는 연산으로 pop, push가 있다.
push에서 배열에 요소를 넣기 전에 size를 체크해서 만약 공간이 부족하다면 resize를 호출해야 한다.
그리고 pop에서 배열에 요소를 빼고 나서 size가 줄어들게 된다.
그 후에 배열의 공간이 너무 많다면 resize를 호출해서 줄여준다.
clear함수
모든 요소들을 돌아서 명시적으로 지워줬다.
또한 참조변수 array를 null로 초기화한 것이 아닌 빈 배열을 만들어서 참조하게 했다.
이렇게 null이아닌 size가 0인 빈 배열로 초기화 해줌으로써 NPE를 방지할 수 있다.
전체코드
package Stack;
public class MyStack<E> implements StackInterface<E> {
E[] array;
int size;
public MyStack(){
array = (E[])new Object[10];
size = 0;
}
private void resize(){
if(size == array.length) {
int newCapacity = Math.max(array.length*2, 64);
E[] newArray = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
return;
}
if(size < array.length / 2){
E[] newArray = (E[]) new Object[array.length / 2];
for(int i = 0; i < size; i++){
newArray[i] = array[i];
}
}
}
@Override
public E push(E item) {
if(size == array.length)
resize();
array[size++] = item;
return array[size-1];
}
@Override
public E pop() {
if(empty())
return null;
E returnData = array[--size];
array[size] = null;
resize();
return returnData;
}
@Override
public E peek() {
if(empty())
return null;
return array[size-1];
}
@Override
public int search(Object value) {
for(int i = 0; i < size; i++){
if(array[i].equals(value))
return size - i;
}
return -1;
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
for(int i = 0; i < size; i++){
array[i] = null;
}
size = 0;
array = (E[])new Object[0];
}
@Override
public boolean empty() {
return size == 0;
}
}