이번 포스트에서는 스택을 직접 구현해 볼 것이다. 하지만 단순히 스택의 구현을 알아보는 것이 목표가 아니라, 스택의 구현 방식에 따른 문제점과 이를 해결하기 위해 필요한 지식들을 살펴볼 것이다. 따라서 가장 기초적인 방식부터 시작해 단점을 차근차근 보완해 업그레이드 해보자.
고정 용량 스택
구현이 굉장히 간단하지만 String만을 대상으로 작동하고 용량도 지정해야만 하고 반복자도 지원하지 않는다.
인스턴스 배열 a[]에 스택의 아이템들을 담고 인스턴스 변수N은 스택에 담긴 아이템들의 갯수를 기록한다. 항목을 삭제할때는 N을 하나 빼고 a[N]을 리턴한다. 항목을 추가할때는 a[N]에 넣고 N을 하나 더한다.
이 구현의 중요한 성능적 특징은 푸시와 팝의 작동 시간이 스택의 크기와 상관없이 일정하다는 것이다. 하지만 스택의 활용성이 떨어지는 단점이 존재한다.
고정 용량 스택의 구현
public class FixedCapacityStackOfStrings {
private String[] a; // 스택 항목을 담는 배열
private int N; // 스택의 크기
public FixedCapacityStackOfStrings(int size)
{ a = new String[size]; }
public boolean isEmpty() { return N==0; }
public int size() { return N; }
public void push(String item)
{ a[N++] = item; }
public void pop()
{ return a[--N]; }
}제네릭
위와 같은 스택은 String 객체만을 지원한다는 문제점이 있다. Integer처럼 다른 뎅이터 타입의 스택을 만들고 싶다면 일일히 새로 구현해야 한다. 이때, 자바가 지원하는 파라미터화(제네릭)을 사용하면 쉽게 해결이 가능하다.
그럼 이제 다양한 데이터 타입을 지원하는 FixedCapacityStack을 구현해보자!
FixedCapacityStack의 구현
public class FixedCapacityStack<Item>{
private Item[] a; // 스택 항목을 담는 배열
private int N; // 스택의 크기
public FixedCapacityStack(int size)
{ a = (Item[]) new Object[size]; }
public boolean isEmpty() { return N==0; }
public int size() { return N; }
public void push(Item item)
{ a[N++] = item; }
public Item pop()
{ return a[--N]; }
}Item이 추가된 것 외에는 바뀐게 거의 없다.
-
String외에도 다양한 객체 타입을 지원하기 때문에 클래스의 이름이String을 위한 고정된 용량의 스택에서고정된 용량의 스택으로 바뀌었다. -
기존의
String을Item으로 바꿔주었다. 갑자기 뭔지 모를Item들이 나타났다고 당활할 필요 없다. 단순히Item자리에 객체 타입이 들어온다고 생각하면 된다. 즉,Item대신String,Integer,Double과 같은 타입들이 유연하게 들어올 수 있게된 것이다. -
a배열을 만드는 코드에서a = new Item[size];가 아닌
a = (Item[]) new Object[cap];라고 적었는데 이는 첫번째 줄 코드처럼 작성시 에러를 일으키기 때문이다. 첫번째 줄과 같은 제네릭 배열은 자바에서 허용되지 않는데, 그 이유는 오래된 기술적 문제로 굳이 알 필요가 없다고 한다. 따라서 두번째 줄과 같이
타입 캐스팅을 사용해 배열을 만든다.
배열 크기 변경
이제 우리의 스택은 String뿐만 아니라 다양한 객체 타입도 지원한다. 그런데 크기가 고정돼있어 스택의 최대 크기를 미리 알아야 한다. 얼마나 커야할지 모른다고 단순히 큰 용량의 스택을 만드는것은 효율적인 해결책이 아니다. 그만큼 메모리가 낭비되고, 현실적으로 사용될 때에는 스택의 크기가 어떻게 될지 전혀 예상할 수 없기 때문이다. 따라서 모든 아이템을 수용할 만큼 크면서도 메모리를 낭비하지 않도록 스택을 업그레이드 할 것이다.
먼저 push()와 pop()을 수정해야 하고 resize()라는 메서드를 추가해야 한다. push()를 할때는 우선 아이템이 들어갈 자리가 있는지 확인한다. 만약에 자리가 없다면 resize()를 이용해 배열의 아이템들을 더 큰 배열을 만들어 옮긴다. pop()을 수행할때는 우선 아이템을 삭제한 후, 배열에 낭비되는 자리가 많다면 배열을 줄인다. 이렇게 유동적으로 크기가 조정되고 메모리를 낭비하지 않는 스택을 구현할 수 있다.
사이즈 조정 스택 업그레이드 구현
...
// 아이템들을 배열 a에서 더 큰 배열로 옮기기
private void resize(int max){
Item[] temp = (Item[]) new Object[max];
for(int i=0; i<N; i++){
temp[i] = a[i];
}
a = temp;
}
// 자리가 있는지 먼저 확인하도록 수정
public void push(Item item){
// item을 추가하려는데 a가 꽉차있으면 두 배 크기의 배열로 늘리기
if(N==a.length) resize(2*a.length);
a[N++] = item;
}
// a배열이 1/4만 채워있으면 크기를 절반으로 줄이기
public Item pop(){
Item item = a[--N];
a[N] = null; // 로이터링 방지, 아래에서 설명
if (N>0 && N == a.length/4) resize(a.length/2);
return item;
}
...이로써 우리의 스택은 push 할 때 자리가 없으면 배열을 두배로 늘리고, pop 할 때 배열이 1/4만 사용하고 있다면 배열을 절반으로 줄임으로써 배열의 절반 크기만 사용하도록 효율을 높였다.
로이터링(loitering)
pop()의 구동방식을 살펴보면 item을 배열의 마지막 아이템으로 지정하고 리턴하는 방식이다. 만약
a[N] = null;위 코드가 없다면 pop된 아이템이 배열에 그대로 버려져 고아 상태가 되며 다시는 접근되지 않는다. 자바는 사용되지 않는 객체를 가비지 컬렉션 정책으로 메모리에서 해제해 주는데 위의 코드가 없다면 자바는 남겨진 참조가 사용되지 않는다는 것을 알지 못한다. 이러한 상황을 로이터링이라고 한다.
로이터링이란 더 이상 필요없는 객체의 참조를 유지하는 상황이다.
순회 반복
컬렉션의 아이템들을 순회하는 가장 기본적인 방법은 자바의 foreach 구문으로 반복자를 루핑(looping) 하는 것인데, 이를 위해서 스택의 반복자를 구현해줘야 한다. 굳이 반복자를 구현해 주는 이유는 foreach구문이 클라이언트 코드를 간결하게 해준다는 장점보다 큰 의미가 있으며, 아래에서 설명한다.
자바에서는 어떤 클래스가 특정 메서드를 지원함을 표시하기 위해 인터페이스라는 메커니즘을 지원한다. 인터페이스란 완전히 추상적인 클래스인데, 연관된 메서드들을 묶어준다. 우리의 스택이 반복자를 지원한다고 나타낼 수 있도록 자바에서 자체적으로 필수 인터페이스를 이미 정의하고 있다.
스택의 반복자를 구현하기 위해서 우선 iterator를 임포트 해줘야 한다.
import java.util.Iterator;Iterable은 java.lang에 정의되어 있지만 Iterator는 역사적인 이유로 java.lang에 포함되어 있지 않다.
이후, 클래스의 선언부에
implements Iterable<Item>이라고 작성해 주면 된다. 이는 "Iterable 인터페이스를 따릅니다" 라는 뜻이다. 자바 문법에 관한 내용인데, 인터페이스의 메서드에 접근하기 위해서는 implements 키워드로 위처럼 작성해야 한다.
아래는
java.lang.Iterable에 정의돼 있는Iterable인터페이스의 정의이다.public interface Iterable<Item> { Iterator<Item> iterator(); }
다시 돌아와서 스택의 반복자를 구현할때 스택은 저장한 배열을 역순으로 순회해야 하므로 반복자의 이름을 ReverseArrayIterator라고 붙이고 아래처럼 메서드를 추가해주자.
public Iterator<Item> iterator(){
return new ReverseArrayIterator();
}이제 ReverseArrayIterator를 스택안에 중첩된 클래스로서 정의한다.
private class ReverseArrayIterator implements Iterator<Item>{
private int i = N;
public boolean hasNext() { return i>0; }
public Item next() { return a[--i] }
public void remove() { }
}여기서 remove()는 구현을 안하는데 반복자가 순회하는 도중에 데이터 구조를 변경하는 상황은 만들지 않는 것이 바람직하기 때문이다. 또 위 반복자 클래스는 스택 클래스에 중첩돼있으므로 인스턴스 변수인 N에 접근할 수 있다.
또, 기술적으로 반복자 표준을 준수하기 위해 아래 두 가지 익셉션을 구현해야 한다.
- 클라이언트가
remove()를 호출하면UnsupportedOperationException을 발생시켜야 하고i가 0일때next()를 호출하면NoSuchElementException을 발생시켜야 한다.
다만 반복자를 foreach에서만 호출한다면 생략해도 무방하다.
이로써 반복자의 구현은 완성이다! 이제 클라이언트에서 foreach 구문을 사용할 수 있다. 반복자의 구현은 단순히 클라이언트가 foreach 구문을 사용할 수 있다는 것보다 큰 의미를 가지고 있다. 반복자를 구현함으로써 클라이언트는 스택의 구현과 분리 된다. 따라서 스택의 데이터 표현 방식을 클라이언트의 눈치(?)를 안 보고 바꿀 수 있으며, 클라이언트 입장에서도 스택이 어떻게 구현 됐는지 알 필요가 없어진 것이다.
ResizingArrayStack 구현
import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<Item>
{
private Item[] a = (Item[]) new Object[1]; // 아이템을 저장하는 배열
private int N = 0; // 스택에 저장된 아이템 개수
public boolean isEmpty() { return N==0; }
public int size() { return N; }
private void resize(int max)
{
// 크기가 max인 새 배열로 이동
Item[] temp = (Item[]) new Object[max];
for(int i=0; i<N; i++) temp[i] = a[i];
a = temp;
}
public void push(Item item)
{
// 스택 위에 새로운 아이템 추가
if(N==a.length) resize(2*a.length);
a[N++] = item;
}
public Item pop()
{
// 스택 위에서 항목 제거&꺼내기
Item item = a[--N];
a[N] = null;
if (N>0 && N == a.length/4) resize(a.length/2);
return item;
}
public Iterator<Item> iterator()
{ return new ReverseArrayIterator(); }
public class ReverseArrayIterator implements Iterator<Item>
{
// LIFO 반복자 지원
private int i = N;
public boolean hasNext() { return i>0; }
public Item next() { return a[--i] }
public void remove() { }
}
}이제 우리의 스택은 배열의 크기를 자동으로 조정하고, 반복자를 지원하며, 제네릭 타입이 추가돼 다양한 데이터 타입을 지원한다.
하지만 이러한 지금의 스택도 완벽하진 않다. push, pop을 하다 보면 크기가 조정되는데 이 작업은 스택의 크기와 시간적으로 비례하므로 작업 시간이 매우 오래 걸릴 수도 있고, 특정 상황에서는 매우 비효율적일 것이다. 때문에 다음 포스트에서 전혀 다른 기초적인 데이터 구조를 사용해 이 단점을 극복해 보자.
출처: Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
