입/출력순서는 LIFO(Last In First Out)이다 👉 데이터가 아래부터 순차적으로 쌓이면 꺼낼때는 위부터 순차적으로 뺄 수 있다. 👉 스택사용시 데이터의 순서가 반전된다.
용어 ?
push : 스택에 데이터를 넣는 작업 pop : 스택에서 데이터를 꺼내는 작업 Top / 꼭대기 : 스택에서 데이터가 들어오고 나가는 쪽 (위쪽) Bottom / 바닥 : 스택에 가장 최하단 쪽
스택 기능 ?
코드 ?
// 스택을 구현해 본 코드
public class IntStack {
private int[] stk; // 스택용 배열
private int capacity; // 스택 용량
private int ptr; // 스택 포인터
// 실행 시 예외 : 스택이 비어 있음
public class EmptyIntStackException extends RuntimeException{
public EmptyIntStackException(){}
}
//실행 시 예외 : 스택이 가득 참
public class OverflowIntStackException extends RuntimeException{
public OverflowIntStackException(){}
}
// 생성자
public IntStack(int capacity){
ptr = 0 ;
this.capacity = capacity;
try{
stk = new int[capacity];
}catch (OutOfMemoryError e){
capacity = 0;
}
}
//스택으로 값을 push하기 위한 메서드
public int push(int x) throws OverflowIntStackException{
if(ptr >= capacity) // 스택 포인터가 스택의 용량과 같을 때 예외발생
throw new OverflowIntStackException();
return stk[ptr++] = x; //현재 스택 포인터에 값을 넣고 포인터를 다음 위치로 이동
}
//스택에서 값을 pop하기 위한 메서드
public int pop() throws EmptyIntStackException{
if(ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
// 스택 top에 위치한 값을 확인하는 메서드
public int peek() throws EmptyIntStackException{
if(ptr <= 0)
throw new EmptyIntStackException();
return stk[ptr - 1];
}
// 스택의 모든 요소를 삭제하는 메서드
public void clear(){
ptr = 0;
}
// 스택에서 원하는 값이 포함되어 있는지? 있다면 어느 위치에 있는지? 확인하는 메서드
public int indexOf(int x){
// 꼭대기 부터 찾는다.
// 동일한 값이 스택에 있다면 pop을 할 때 꼭대기에서부터 꺼내기에
for(int i = ptr - 1; i >= 0 ; i--){
if(stk[i] == x)
return i; // 찾을 시 위치 반환
}
return -1; // 없을 시 -1 반환
}
// 스택의 용량을 확인하는 메서드
public int getCapacity(){
return capacity;
}
//스택에 쌓여 있는 데이터 개수를 반환
public int size(){
// 배열에서는 0부터 시작 하며 쌓일 때마다 포인터가 1씩 증가한다.
// 이해를 위해 한 가지 예로 처음에는 포인터가 0을 가르키고 있다.
// 이때, 데이터가 하나 push되면 포인터는 1로 이동한다. 그리고 데이터도 현재 1개가 쌓였다.
return ptr;
}
// 스택이 비어 있는가 ?
public boolean isEmpty(){
// 비교 연산이기에 boolean을 한다. 그리고 비어 있으면 포인터는 0을 가르킬 것이다.
return ptr <= 0;
}
//스택이 가득 찼는가?
public boolean isFull(){
// 스택을 위한 배열은 (용량 -1)이 마지막 인덱스이다.
// ptr은 항상 현재 데이터가 마지막으로 저장되어 있는 인덱스+1을 가르킨다.
// 배열의 마지막 인덱스까지 값이 저장되었다면 ptr == capacity와 값은 값이 된다.
// 여기서 다시 값을 넣으려고 하면 배열의 저장 범위를 넘어감으로 예외가 발생한다.
return ptr >= capacity;
}
// 스택 안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
public void dump(){
if(ptr <= 0)
System.out.println("스택이 비어 있습니다");
else{
for(int i = 0 ; i < ptr ; i++)
System.out.print(stk[i]+ " ");
}
System.out.println();
}
}
보충설명 ?
스택 사이즈 , 용량 , 포인터 위치와 관련하여 영향을 받는 메서드(기능)는 비교연산자가 사용된 것을 확인할 수 있다.
용량이 가득 찼을 경우) if(ptr >= capacity) 비어 있을 경우) if(ptr <= 0)
이때 , == 연산자를 사용해도 되는데 <= , >= 을 사용한 부분이 있었다. 이 부분에 대해서는 프로그램 오류 등으로 프로그램 수행 중 의도하지 않게 값이 증가하거나 감소하여 ptr이 0보다 작거나 capacity보다 클 수 있다. 이때 위와같이 부등호를 붙여주면 스택 배열의 범위를 벗어나는 접근을 막을 수 있다. 이러한 안정성 문제를 고려하여 작성하면 안정성을 향상 시킬 수 있다.
