[알고리즘] 2.1. 자료구조 : 배열 기반 스택(Stack) 구현

  개요

스택이 무엇인지, 어디에 사용하고 무엇으로 만드는지에 대한 전체적인 내용은 이전 게시물을 참고하시면 됩니다.

배열 기반 스택의 프로퍼티(속성) 으로는 top(데이터 삽입/삭제하는 위치), maxSize(배열의 최대크기), stackArray(배열)으로 구성되어 있습니다. 메쏘드(함수)로는 pop(삭제), push(삽입), peek(탐색)이 있고, 부수적인 함수로는 isEmpty(스택이 비어있는지 확인)가 있습니다. 

  배열을 이용한 스택 구현

public class ArrStack {

private int top; //마지막 위치 (삽입,삭제가 이루어질 위치)

private int maxSize;

private Object[] stackArray;

//생성자 : 프로퍼티 초기

public ArrStack(int size){

this.top = -1;

this.maxSize = size;

this.stackArray = new Object[maxSize];

}

//스택이 비어있는지 확인

public boolean isEmpty(){

return (top==-1);

}

//데이터 삽입

public void push(Object item){

//스택에 가득찼을 때 예외처리

if(top >= maxSize-1) throw new ArrayIndexOutOfBoundsException((top+1)+">="+maxSize);

stackArray[++top] = item;

}

//데이터 읽기

public Object peek(){

//스택이 비어있을 때 예외처리

if(isEmpty()) throw new ArrayIndexOutOfBoundsException(top);

return stackArray[top];

}

//데이터 삭제 : 삭제된 데이터 반환(백업용도)

public Object pop(){

Object item = peek();

top--;

return item;

}

}

//배열 기반 스택을 사용하는 main함수

public class main {

public static void main(String[] args) {

ArrStack stackA = new ArrStack(5);

stackA.push(3);

stackA.push("Hi");

stackA.push("Monsieur");

stackA.push("Songsong");

while(!stackA.isEmpty()){

System.out.println(stackA.pop());

}

}

}

ArrStack이라는 클래스를 만든 후 메인 함수에서 사용하였습니다. 앞서 설명하였듯이, 구현보다 중요한 것은 자료구조를 어떻게 사용하는가인데요. Stack의 사용방법은 너무나도 쉽습니다. 

1) 스택 객체를 생성할 때 최대 크기를 정해줍니다. new ArrStack(5);

2) 생성된 스택 객체를 이용하여 원하는 데이터를 삽입합니다. stackA.push("Hi");

3) 데이터를 읽기만 하고 싶을때는 peek함수를 , 삭제하면서 읽고 싶을 때는 pop메소드를 사용하면 됩니다. stackA.pop()

(1) 생성자

구현 방법은 우선 생성자를 통해 프로퍼티를 초기화 합니다. 이때, top의 위치는 -1인데, 그 이유는 배열의 인덱스 때문입니다. 만약 top을 0으로 초기화 한다면 다음에 push의 위치는 1이 됩니다. 그러면 배열의 0번째 인덱스는 비어 있는 상태가 되어버립니다. 

(2) 삽입 push()

push메소드는 삽입 함수로 우선 top의 위치를 하나 더해 준 후 그 위치에 원하는 data를 삽입하면 됩니다.

(3) 삭제 pop()

pop메소드를 쉽게 구현하려면 단순히 top의 위치를 하나 빼주기만 하면 됩니다. 하지만 데이터의 삭제할 때 실수를 한다면 치명적이므로 만약을 대비하여 삭제될 데이터를 백업해야 합니다. 

*Object 라는 데이터 타입은 쉽게 생각해서 int, string, double 모든 타입을 포함한다고 생각하면 됩니다.

  예외처리 (Overflow, Underflow)

push(), peek() 함수 내부에 if문으로 예외처리한 부분이 있습니다. 

if(top >= maxSize-1) throw new ArrayIndexOutOfBoundsException((top+1)+">="+maxSize);

배열 특성상 실행 하기 이전에 배열의 최대 크기를 정해주어야 합니다. 그런데 삽입을 여러번 하여 이 최대크기보다 많은 데이터를 삽입하였을 경우 error가 생기게 됩니다. 이러한 error를 overflow라고 합니다. 반대로 스택에 아무것도 없을 경우 pop() 데이터 삭제를 하면 또한 error가 생기는데 이를 underflow라고 합니다. 이러한 error들을 처리하기 위해 if문을 사용하여 예외처리를 하였습니다.