스택은 선입후출 구조로 먼저 들어온 값이 맨 아래로 깔려서 맨 나중에 들어온 값부터 차례대로 삭제해야 맨 마지막에 맨 처음에 들어온 값을 빼내는 구조이다.
스택을 구현하는 자료구조로는 ArrayList와 LinkedList가 있다.
[Stack Interface]
package arrays;
public interface Stack{
public boolean isEmpty();
public void push(Integer element);
public Integer pop();
public Integer peek();
public int size();
}
[ArrayList로 구현한 Stack]
package arrays;
import java.util.Arrays;
import java.util.EmptyStackException;
public class ArrayStack implements Stack{
final int defaultSize = 100;
Integer[] elements;
int top;
public ArrayStack() {
this.elements = new Integer[this.defaultSize]
this.top = -1;
}
/**top이 -1로 초기화 설정 되어 있기에 아무것도 없으면 보다 작다.
그러므로 top이 0보다 작을 때 스택이 비어있다.
**/
@Override
public boolean isEmpty() {
return this.top < 0;
}
@Override
public void push(Integer element) {
/**기본으로 설정한 Array 크기보다 더 커진 경우라면 사이즈를 늘려서 새로운 객체를 만들어 준다.
* 이때 객체를 다 복사해서 넣어주어야 한다. **/
if( this.elements.length <= this.top+1 ){
Integer [] newElements = new Integer[this.elements.length + this.defaultSize];
System.arraycopy(this.elements, 0, newElements, 0,this.elements.length);
this.elements = newElements;
}
this.top ++;
this.elements[this.top] = element;
}
@Override
public Integer pop() {
if(isEmpty()){
throw new EmptyStackException();
}
Integer value;
value = elements[this.top];
elements[this.top] = null;
this.top--;
return value;
}
@Override
public Integer peek() {
if(isEmpty()) {
throw new EmptyStackException();
}
return elements[this.top];
}
@Override
public int size() {
return this.top+1;
}
@Override
public String toString() {
//stack의 배열 중 원소가 저장된 부분만 출력
StringBuilder line = new StringBuilder();
for (int i = 0; i <= this.top; i++){
line.append((line.length()!=0 ? " ": "")+this.elements[i]);
}
return line.toString();
}
}
Stack에 저장되는 데이터는 Array를 이용해 저장한다. Integer 배열 elements가 이에 해당한다.
isEmpty()
해당 stack의 맨 위를 가르키는 부분이 top부분이기에 이 부분이 0보다 작다면 stack이 비어있는 것이므로 true를 돌려준다.
push()
기본으로 주어진 Integer[this.defaultSize]보다 크기가 커지게 된다면 새로운 크기의 객체를 생성해서 돌려주는데 이때 객체 복사를 통해서 객체에 기존에 있던 객체 값들을 다 복사해서 넣어주어야 한다.
기본적으로 설정해준 사이즈보다 커지지 않은 경우에 push를 한다면 이때는 elements[this.top] = element; 배열에 해당 top 위치에 추가해줄 요소를 넣어준다.
pop()
해당 stack이 비어있다면 예외처리를 해준다.
Iteger Value라는 변수를 만들어 현재 top값에 있는 값을 저장한 뒤 null처리해준다(참조 해제를 해야 가비지처리가 된다)
이때 pop()은 스택의 맨 위에 부분에 있는 값을 돌려준다.(돌려주는 과정에서 해당 값은 stack에서는 삭제된다.)
peek()
pop()과 마찬가지로 해당 stack이 비어이있다면 예외처리를 해준다.
peek()은 pop()과 달리 해당 스택에 가장 위에 있는 값이 무엇인지를 삭제하지 않고 준다.(stack에서 해당 top에 있는 값이 삭제되지 않고 넘어간다.)
