글 작성자: ST_
728x90





 

자료구조 관련 목록 링크 펼치기 

 

 

 








 

  • Stack

 

 

 

 

 

 

만약 이 글을 처음 접한다면 자바 컬렉션 프레임워크 (Java Collections Framework) 글과 스택 인터페이스 (Stack Interface)을 먼저 보고 오셨으면 한다. (필자가 앞서 언급했지만, Stack 인터페이스를 만들어 두고 이를 implements 하여 구체적으로 구현하고자 한다고 했다. 그러니 꼭 스택 인터페이스 글도 읽어오시길 바란다.)

 

또한 추가로 제네릭에 대한 이해를 필요로 하니 필요하다면 다음 글도 읽어오는 것을 추천드린다.

제네릭에 대한 이해

 

 

 

그리고 '반드시' ArrayList 구현 글을 읽고 오시길 바란다. 

기본적으로 Object[] 배열과 자료구조 기본 개념은 알고있어야 한다.

 

오늘은 후입선출/선입후출의 대표적 자료구조인 Stack을 구현하고자 한다. 스택 인터페이스 글을 보고오셨으면 알겠지만 Java 에서 제공하고 있는 Stack 라이브러리는 'Vector' 클래스를 상속받아 구현하고 있다.

 

즉, Stack 클래스에서도 Vector 클래스의 메소드들을 사용할 수 있게 되어 있는데 Vector 클래스는 기본적으로 'ArrayList'와 그 구조가 거의 같다.

 

기본적으로 Stack 클래스는 내부에서 최상위 타입 배열인 Object[] 배열을 사용하여 데이터들을 관리하고 있다. 그러면 스택의 구조를 한 번 보도록하자.

 

 

 

 

스택은 기본 원칙이 '후입선출(LIFO : Last in First out)' 이다. (또는 선입후출(FILO : First in Last out) 이라고도 한다. 여기서는 후입선출로 통일하겠다.)

후입선출.. 한자로 後入先出 이다. 말 그대로 '나중에 들어온 것이 먼저 나가는 방식'이다.

 

그림으로 보면 이렇다.

 

여러분들이 이사를 가기 위해 박스에 물건들을 넣는다고 생각해보자.

먼저 a라는 짐을 넣고, 다음으로 b, 그 다음 c를 순서대로 박스에 넣었다. 이제 이 박스를 들고 새로운 집에 도착했다. 그리고 박스를 열어 박스에 있던 짐들을 하나씩 꺼내려한다. 그럼 어떤 것 부터 꺼낼까? 가장 위에있던 물건부터 뺄 것이다.

 

즉, 먼저 들어온 것은 가장 아래에 있고, 가장 아래에 있는만큼 가장 나중에 빠져나오게 된다.

 

이러한 구조는 보통 어디서 쓰이냐면 '뒤로 가기', '실행 취소(undo)', 그리고 컴퓨터 구조에서 'stack memory'가 대표적이다.

 

스택의 장점은 후출선입인 만큼 직전의 데이터를 빠르게 갖고올 수 있다는 것이다. 또한 균형성 검사를 할 수 있기 때문에 수식, 괄호 등의 검사에서도 쓰인다.

 

 

그럼 스택을 어떻게 구현해야 할까?

일단 Object[] 배열을 사용한다는 것은 알았다. 좀 더 이해하기 쉽게 배열을 가로가 아닌 세로로 세워서 이해해보자.

 

 

이러한 구조로 되어있다고 보면 된다. 일단 하나하나 설명해보자면 이렇다.

 

Bottom : 가장 밑에 있는 데이터 또는 그 데이터의 인덱스를 의미한다.

Top : 가장 위에 있는 데이터 또는 그 데이터의 인덱스를 의미한다.

Capacity : 데이터를 담기 위한 용적

size : 데이터의 개수

 

 

 

그리고 데이터를 추가하는 작업을 push 라고 한다. (리스트에서의 add와 같은 역할이다.)

또한 데이터를 삭제하는 작업을 pop 이라고 한다. (리스트에서의 remove 와 같은 역할)

 

특징이라면 push는 데이터를 기존의 리스트와 같은 메커니즘으로 인덱스가 증가하면서 추가하지만, 삭제는 리스트와는 달리 '가장 마지막 데이터'를 삭제한다. (리스트에서의 remove()는 대개 가장 앞의 원소를 삭제한다.)

 

 

즉, 다음과 같다.

 

[push]

 

 

[pop]

 

 

 

그럼 본격적으로 Stack을 구현하기 전에 알아가야할 것이 있다.

모든 자료구조는 '동적 할당'을 전제로 한다. 가끔 ArrayList, Stack 같이 Object[] 배열을 사용하는 자료구조를 구현 할 때, 자료구조의 용적(Capacity)이 꽉 차면 리스트의 크기를 늘리지 않고 그냥 꽉 찼다고 더이상 원소를 안받도록 구현한 경우가 많은데 이는 자료구조를 구현하는 의미가 없다.

 

동적 할당을 안하고 사이즈를 정해놓고 구현한다면 메인함수에서 정적배열을 선언하는 것과 차이가 없다.

 

데이터의 개수를 알 수 없는데 배열을 쓰고 싶을 때 여러분은 어떤 방법을 선택하는가? ArrayList, LinkedList 등의 자료구조를 선택할 것이다. 왜냐면 사이즈를 정하지 않고 동적으로 활용할 수 있기 때문이다. 그렇기 때문에 당장은 어렵더라도 반드시 동적 할당이 가능한 형태로 구현하도록 노력을 하는 것이 좋다.

 

 

 

 

 

 







  • Stack 구현

 

 

 

 

 

- 사전 준비

 

[Stack Interface 소스]

더보기

 

[StackInterface.java]

package Interface_form;

/**
 * 
 * 자바 stack Interface입니다. <br>
 * StackInterface는 Stack에 의해 구현됩니다.
 * 
 * @author st_lab
 * @param <E> the type of elements in this Stack
 *
 * @version 1.0
 * 
 */


public interface StackInterface<E> {
	
	/**
	 * 스택의 맨 위에 요소를 추가합니다. 
	 * 
	 * @param item 스택에 추가할 요소 
	 * @return 스택에 추가된 요소 
	 */
	E push(E item);
	
	/**
	 * 스택의 맨 위에 있는 요소를 제거하고 제거 된 요소를 반환합니다.
	 * 
	 * @return 제거 된 요소 
	 */
	E pop();
	
	/**
	 * 스택의 맨 위에 있는 요소를 제거하지 않고 반환합니다.
	 * 
	 * @return 스택의 맨 위에 있는 요소 
	 */
	E peek();
	
	/**
	 * 스택의 상반 부터 특정 요소가 몇 번째 위치에 있는지를 반환합니다.
	 * 중복되는 원소가 있을경우 가장 위에 있는 요소의 위치가 반환됩니다.
	 * 
	 * @param value 스택에서 위치를 찾을 요소
	 * @return 스택의 상단부터 처음으로 요소와 일치하는 위치를 반환.
	 *         만약 일치하는 요소가 없을 경우 -1 을 반환 
	 */
	/*
	 *         ________
	 *         | a    |
	 * idx 3   |______|   search("w")
	 *         | e    |   --> 상단(idx 3)으로 부터 3번 째에 위치 
	 * idx 2   |______|       == return 되는 값 : 3
	 *         | w    |
	 * idx 1   |______| 
	 *         | k    |
	 * idx 0   |______|
	 * 
	 */
	int search(Object value);
	
	/**
	 * 스택의 요소 개수를 반환합니다.
	 * 
	 * @return 스택에 있는 요소 개수를 반환 
	 */
	int size();
	
	/**
	 * 스택에 있는 모든 요소를 삭제합니다.
	 */
	void clear();
	
	/**
	 * 스택에 요소가 비어있는지를 반환합니다.
	 * 
	 * @return 스택에 요소가 없을 경우 {@code true}, 그 외의 경우 {@code false}를 반환
	 */
	boolean empty();
}

 

 

[구현 바로가기]

 

<필수 목록>

◦ 클래스 및 생성자 구성

◦ resize 메소드 구현

◦ push 메소드 구현

◦ pop 메소드 구현

◦ peek 메소드 구현

◦ search, size, clear, empty 메소드 구현

 

<부가 목록>

◦ clone, toArray 구현

 

◦ 전체 코드

 

 

<Stack 확장>

◦ ArrayList를 상속한 Stack

 

 

 

 

 

 

 

 

 

 

[Stack 클래스 및 생성자 구성하기]

 

 

Stack 이름으로 생성해준 뒤 앞서 작성했던 StackInterface 인터페이스를 implements 해준다. implements 를 하면 class 옆에 경고표시가 뜰 텐데 인터페이스에 있는 메소드들을 구현하라는 것이다. 어차피 모두 구현해나갈 것이기 때문에 일단은 무시한다. (ArrayList 글을 보셨다면 코드가 거의 유사하다는 것을 볼 수 있다.)

 

[Stack.java]

import Interface_form.StackInterface;

public class Stack<E> implements StackInterface<E> {

	private static final int DEFAULT_CAPACITY = 10;	// 최소(기본) 용적 크기 
	private static final Object[] EMPTY_ARRAY = {};	// 빈 배열 
	
	private Object[] array;	// 요소를 담을 배열  
	private int size;	// 요소 개수 
	
	
	// 생성자1 (초기 공간 할당 X) 
	public Stack() {
		this.array = EMPTY_ARRAY;
		this.size = 0;
	}
	
	// 생성자2 (초기 공간 할당 O) 
	public Stack(int capacity) {
		this.array = new Object[capacity];
		this.size = 0;
	}
}

 

 

변수부터 먼저 차례대로 설명해주도록 하겠다.

 

DEFAULT_CAPACITY : 배열이 생성 될 때의 최초 할당 크기(용적)이자 최소 할당 용적 변수로 기본값은 10으로 설정해두었다. (capacity가 용적이라는 의미다)

EMPTY_ARRAY : 아무 것도 없는 빈 배열 (용적이 0인 배열)

array : 요소들을 담을 배열

size : 배열에 담긴 요소(원소)의 개수 변수 (용적 크기가 아니다. 절대 헷갈리지 말자)

 

 

그리고 DEFAULT_CAPACITY 변수와 EMPTY_ARRAY 변수는 상수로 쓸 것이기 때문에 static final 키워드를 붙인다.

 

 

그리고 보면 생성자가 2개를 두었다.

생성자 1의 경우 사용자가 공간 할당을 미리 안하고 객체만 생성하고 싶을 때, 즉 다음과 같은 상태일 때이다.

Stack<Integer> stack = new Stack<>();

 

이 때는 사용자가 공간 할당을 명시하지 않았기 때문에 array 변수를 EMPTY_ARRAY로 초기화 시켜 놓는다.

 

 

반면에 사용자가 데이터의 개수를 예측할 수 있어서 미리 공간 할당을 해놓고 싶을 경우, 즉 다음과 같이 생성할 경우 

Stack<Integer> stack = new Stack<>(100);

 

array의 공간 할당을 입력 된 수 만큼 (예제에서는 array = new Object[100]) 배열을 만든다. 그리고 마찬가지로 size 를 0으로 초기화 시켜놓는다.

 

(size는 요소(원소)의 개수를 의미하는 것이다. 공간을 할당해놓는 것하고는 다른 개념이다.)

 

 

 

 

 

 

[동적할당을 위한 resize 메소드 구현]

 

 

앞서 필자가 말했던 것 처럼 우리는 들어오는 데이터에 개수에 따라 '최적화'된 용적을 갖을 필요가 있다. 만약 데이터는 적은데 용적이 크면 메모리가 낭비되고, 반대로 용적은 적은데 데이터가 많으면 넘치는 데이터들은 보관할 수 없게 되는 상황을 마주칠 수 있다.

 

그렇기 때문에 size(요소의 개수)가 용적(capacity)에 얼마만큼 차있는지를 확인하고, 적절한 크기에 맞게 배열의 용적을 변경해야 한다. 또한 용적은 외부에서 마음대로 접근하면 데이터의 손상을 야기할 수 있기 때문에 private로 접근을 제한해주도록 하자.

 

private void resize() {
		
	// 빈 배열일 경우 (capacity is 0)
	if(Arrays.equals(array, EMPTY_ARRAY)) {
		array = new Object[DEFAULT_CAPACITY];
		return;
	}
		
	int arrayCapacity = array.length;	// 현재 용적 크기 
		
	// 용적이 가득 찰 경우
	if(size == arrayCapacity) {
		int newSize = arrayCapacity * 2;
		
		// 배열 복사
		array = Arrays.copyOf(array, newSize);
		return;
	}
		
	// 용적의 절반 미만으로 요소가 차지하고 있을 경우
	if(size < (arrayCapacity / 2)) {
			
		int newCapacity = (arrayCapacity / 2);
			
		// 배열 복사
		array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, newCapacity));
		return;
	}
}

 

현재 array의 용적(=array 길이)과 데이터의 개수(size)를 비교한다. 

 

조건문 1 :  if (Arrays.equals(array, EMPTY_ARRAY)) 

앞서 생성자에서 사용자가 용적을 별도로 설정하지 않은 경우 EMPTY_ARRAY로 초기화 되어있어 용적이 0인 상태다. 이 경우를 고려하여 이제 새로 array의 용적을 할당하기 위해 최소 용적으로 설정해두었던 DEFAULT_CAPACITY의 크기만큼 배열을 생성해주고 메소드를 종료한다.

또한 주소가 아닌 값을 비교해야 하기 때문에 Arrays.equals() 메소드를 사용하도록 하자.

 

 

 

조건문 2 :  if (size == arrayCapacity) 

데이터가 꽉 찰 경우에는 데이터(요소)를 더 받아오기 위해서 용적을 늘려야 한다. 즉, 데이터의 개수가 용적과 같을 경우는 꽉 차있는 경우를 말한다. 이 때는 새롭게 용적을 늘릴 필요가 있으므로 새로운 용적을 현재 용적의 2배로 설정하도록 한다. 

 

또한 기존에 담겨있던 요소들을 새롭게 복사해와야한다. 이 때 편리하게 쓸 수 있는 것이 Arrays.copyOf() 메소드다. Arrays.copyOf() 는 첫 번째 파라미터로 '복사할 배열'을 넣어주고, 두 번째 파라미터는 용적의 크기를 넣어주면 된다.

만약 복사할 배열보다 용적의 크기가 클 경우 먼저 배열을 복사한 뒤, 나머지 빈 공간은 null로 채워지기 때문에 편리하다.

 

 

 

조건문 3 :  if (size < (arrayCapacity / 2 )) 

데이터가 용적에 절반 미만으로 차지 않을 경우다. 이 경우 데이터는 적은데 빈 공간이 메모리를 차지하고 있어 불필요한 공간을 낭비할 뿐이다. 이럴 때에는 사이즈를 적적하게 줄여주는 것이 좋지 않겠는가?

데이터의 개수가 용적의 절반 미만이라면 용적도 절반으로 줄여주도록 하기 위해 새로운 용적(new_capacity)을 현재 용적의 절반으로 둔 뒤, Arrays.coptyOf() 메소드를 통해 새로운 용적의 배열을 생성해주도록 하자.

 

다만, 우리가 설정한 최소 용적(DEFAULT_CAPACITY)보다 아래로는 떨어지지 않도록 하기 위해 새로운 용적과 최소 용적 중 큰 것을 새로운 용적으로 설정하도록 한다.

 

 

 

 

 

 

 

 

 

 

 

[push 메소드 구현]

 

 

이제 본격적으로 Stack에 데이터를 추가할 수 있도록 해보자. 

 

Stack의 push는 항상 최상단(맨 위)에 데이터를 추가해야하므로 한 종류밖에 없다. 리스트로 치면 add(E value)와 같은 역할이다.

 

- 가장 마지막 부분(최상단)에 추가 - push(E item) 

 

물론 현재 자바에 내장되어있는 Stack에서는 Vector을 상속받다보니 중간 삽입같은 특정 위치의 삽입도 가능하다. 이는 가장 마지막에 다룰 ArrayList를 상속하여 구현하는 파트에서 볼 것이고, 지금은 Stack 자료구조 특징에 좀 더 집중하기 위해 push 단일 메소드만 구현 할 것이다.

 

push의 경우 아까 위의 그림에서 보았듯 가장 마지막 위치에 데이터를 추가하는 것이다. 다시 보자면 이렇다.

 

 

이를 토대로 구현해보자.

 

 

1. 기본삽입 : push(E item) 

 

구현 자체는 그리 어렵지 않다. push() 메소드를 구현하자면 이렇다.

(자바 내부에서 push메소드는 push 된 데이터를 리턴하기 때문에 E 타입을 반환하는 메소드로 구현해주었다)

@Override
public E push(E item) {
		
	// 용적이 꽉 차있다면 용적을 재할당 해준다. 
	if (size == array.length) {
		resize();
	}
	array[size] = item;	// 마지막 위치에 요소 추가 
	size++;	// 사이즈 1 증가 
		
	return item;
}

 

 

또한 필자가 '동적할당'을 강조했듯 용적이 가득찼다면 array의 용적을 늘려주어야 한다. 그렇기 때문에 앞서 구현한 resize() 메소드를 호출하여 용적을 재할당 해준 뒤 데이터를 추가해주도록 하자.

 

 

 

 

[push 메소드 묶어보기]

 

더보기 
@Override
public E push(E item) {

	if (size == array.length) {
		resize();
	}
	array[size] = item;
	size++;
	
	return item;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[pop 메소드 구현]

 

 

 

 

pop 메소드 또한 그리 어렵지 않게 만들 수 있다. push메소드 메커니즘을 반대로 구현하면 된다.

 

다만 중요한 점은 '삭제할 요소가 없는 경우' 즉, 스택이 비어있는 경우다. 이에 대한 예외로 필자는 EmptyStackException을 던지도록 하겠다.

 

pop의 구조 또한 매우 쉬우니 그림을 다시 한 번 보고 구현해보도록 하자.

 

 

 

 

 

 

 

 

 

1. pop() 메소드

 

 

@Override
public E pop() {
		
	// 만약 삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시키기
	if(size == 0) {
		throw new EmptyStackException();
	}
		
	@SuppressWarnings("unchecked")
	E obj = (E) array[size - 1];	// 삭제될 요소를 반환하기 위한 임시 변수 
		
	array[size - 1] = null;	// 요소 삭제 
		
	size--;	// 사이즈 1 감소 
	resize();	// 용적 재할당 
		
	return obj;
}

 

여기서 @SuppressWarnings("unchecked") 에 대해 잠깐 언급하고 가겠다.

@SuppressWarnings("unchecked")을 붙이지 않으면 type safe(타입 안정성)에 대해 경고를 보낸다. 반환되는 것을 보면 E 타입으로 캐스팅을 하고 있고 그 대상이 되는 것은 Object[] 배열의 Object 데이터다. 즉, Object -> E 타입으로 변환을 하는 것인데 이 과정에서 변환할 수 없는 타입을 가능성이 있다는 경고로 메소드 옆에 경고표시가 뜨는데, 우리가 push하여 받아들이는 데이터 타입은 유일하게 E 타입만 존재한다. 

그렇기 때문에 형 안정성이 보장된다. 한마디로 ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 것이 @SuppressWarnings("unchecked") 이다. 물론 절대 남발하면 안되고, 형 변환시 예외 가능성이 없을 확실한 경우에 최소한의 범위에서 써주는 것이 좋다. 그렇지 않으면 중요한 경고 메세지를 놓칠 수도 있기 때문이다.

 

 

 

 

 

 

 

 

[pop 메소드 묶어보기]

더보기 
@Override
public E pop() {
		
	// 만약 삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시키기
	if(size == 0) {
		throw new EmptyStackException();
	}
		
	@SuppressWarnings("unchecked")
	E obj = (E) array[size - 1];	// 삭제될 요소를 반환하기 위한 임시 변수 
		
	array[size - 1] = null;	// 요소 삭제 
		
	size--;	// 사이즈 1 감소 
	resize();	// 용적 재할당 
		
	return obj;
}

 

 

 

 

 

 

 

 

 

 

[peek() 메소드 구현]

 

 

 

가장 상단에 있는 데이터를 삭제하지 않고 확인만 하고싶을 때가 있다. 그럴 때 쓰는 것이 peek() 메소드다. 한마디로 pop() 메소드에서 삭제과정만 없는 것이 peek() 이다.

 

또한 마찬가지로 스택에 데이터가 없는 경우를 생각하여 예외를 던져주도록 하자.

 

 

 

 

 

1. peek() 메소드

 

@SuppressWarnings("unchecked")
@Override
public E peek() {
	// 만약 삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시키기
	if(size == 0) {
		throw new EmptyStackException();
	}
		
	return (E) array[size - 1];
}

 

마찬가지로 마지막 원소를 반환해야하는지라 Object 타입을 E 타입으로 캐스팅을 해주면서 경고창이 뜬다. 하지만 pop()메소드에서 설명했듯이 마지막 원소 또한 E Type 외에 들어오는 것이 없기 때문에 형 안정성이 확보되므로 경고표시를 무시하기 위해 @SuppressWarnings("unchecked")을 붙인다.

 

그리고 잘 생각해야 할 것이 항상 마지막 원소의 인덱스는 size 보다 1 작다. 그렇기 때문에 끝 점을 잘 생각하면서 참조해야한다.

 

 

 

 

 

 

 

[remove 메소드 묶어보기]

 

 

더보기 
@SuppressWarnings("unchecked")
@Override
public E peek() {
	// 만약 삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시키기
	if(size == 0) {
		throw new EmptyStackException();
	}
		
	return (E) array[size - 1];
}

 

 

 

 

 

 

 

 

 

 

 

 

[search, size, isEmpty, clear 메소드 구현]

 

 

 

이제 나머지 Stack 인터페이스에 있던 search, size, isEmpty, clear를 만들 차례다.

 

다른 메소드 구현에 비해 매우 쉬운지라 바로바로 넘어가도록 하겠다.

 

 

 

 

1. search(Object o) 메소드

 

Java API를 보면 search() 라는 메소드가 있다.

 

이는 '찾으려는 데이터가 상단의 데이터로부터 얼마만큼 떨어져 있는지'에 대한 상대적 위치 값이다. 말로는 어렵긴 하지만, 그림을 보면 이렇다.

 

 

 

쉽게 말하자면 Top으로부터 떨어져있는 거리를 의미한다. (단, 1부터 시작)

수식으로 표현하자면 size - index 값이 되겠다.

 

다만 일치하는 데이터를 찾지 못했을 경우는 -1 을 반환한다.

 

@Override
public int search(Object value) {
	// value가 null일 때는 eqauls(null)이되어 null pointer exception이 발생할 수 있으니,
	// == 로 null값을 비교해준다.
	if(value == null) {
		for(int idx = size - 1; idx >= 0; idx--) {
			if(array[idx] == null) {
				return size - idx;
			}
		}
	} else {
		for(int idx = size - 1; idx >= 0; idx--) {
	
			// 같은 객체를 찾았을 경우 size - idx 값을 반환 
			if(array[idx].equals(value)) {
				return size - idx;
			}
		}
	}
	return -1;
}

 

 

 

 

 

2. size() 메소드

 

size() 메소드는 현재 Stack에 있는 요소의 개수를 알려준다.

 

@Override
public int size() {
	return size;
}

 

 

 

 

 

 

 

 

3. clear() 메소드

 

 

clear()는 단어에서 짐작 할 수 있듯 모든 요소들을 비워버리는 작업이다. 예로들어 리스트에 요소를 담아두었다가 초기화가 필요할 때 쓸 수 있는 유용한 존재다. 또한 모든 요소를 비워버린다는 것은 요소가 0개라는 말로 size 또한 0으로 초기화해주고, 배열의 용적 또한 현재 용적의 절반으로 줄일 수 있도록 해준다.

 

왜 초기 값이 아니라 절반이죠? 라고 질문할 수도 있다. 물론 초기값으로 초기화 해주어도 되나 생각해보면 현재 배열의 용적은 결국 데이터를 해당 용적에 만족하는 조건만큼 썼다는 의미가 된다.

 

예로들어 데이터가 1500개였다고 가정해보자. 그럼 용적량은 10부터 2씩 곱해지므로 2560이었을 것이다.

요소들을 모두 초기화 했더라도 앞으로 들어올 데이터들 또한 데이터가 1500개일 가능성이 높다. 즉, 현재 용적량의 기대치에 근접할 가능성이 높기 때문에 일단은 용적량을 일단 절반으로만 줄이는 것이다.

(또한 그만큼 데이터를 쓰지 않더라도 삭제 과정에서 용적량을 줄이기 때문에 크게 문제되진 않는다.)

 

@Override
public void clear() {
		
	// 저장되어있던 모든 요소를 null 처리 해준다.
	for(int i = 0; i < size; i++) {
		array[i] = null;
	}
	size = 0;
	resize();
}

 

모든 배열을 명시적으로 null로 처리해주는 것이 좋다.

 

 

 

 

 

4. empty() 메소드

 

 

 

empty() 메소드는 단어 그대로 Stack이 비어있는지, 즉 요소가 한 개도 남아있지 않은지를 true 또는 false로 반환해주는 메소드다. 만약 요소가 하나도 없다면 true, 하나라도 존재한다면 true가 된다.

 

그렇다고 모든 요소들을 하나씩 검사해줄 필요는 없다. size 변수가 0이면 데이터가 없다는 뜻이므로 size 값에 따라 반환만 다르게 해주면 된다.

 

@Override
public boolean empty() {
	return size == 0;
}

 

 

 

 

 

 

 

이렇게  search, size, isEmpty, clear 메소드들을 만들어보았다. 해당 메소드들을 묶어서 한 눈에 보고싶다면 아래 더보기를 누르면 된다.

 

 

 

[search, size, isEmpty, clear 메소드 묶어보기]

 

 

더보기 
@Override
public int search(Object value) {
	if(value == null) {
		for(int idx = size - 1; idx >= 0; idx--) {
			if(array[idx] == null) {
				return size - idx;
			}
		}
	} else {
		for(int idx = size - 1; idx >= 0; idx--) {
			if(array[idx].equals(value)) {
				return size - idx;
			}
		}
	}
	return -1;
}

@Override
public int size() {
	return size;
}

@Override
public void clear() {
		
	for(int i = 0; i < size; i++) {
		array[i] = null;
	}
	size = 0;
	resize();
}
	
@Override
public boolean empty() {
	return size == 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<부가 목록>

 

 

[clone, toArray, sort 메소드 구현]

 

 

 

이 부분은 굳이 구현하는데 중요한 부분은 아니라 넘어가도 된다. 다만 조금 더 많은 기능을 원할 경우 추가해주면 좋은 메소드들이긴 하다. clone은 기존에 있던 객체를 파괴하지 않고 요소들이 동일한 객체를 새로 하나 만드는 것이다. 그리고 toArray는 사용자가 main 함수에서 특정 배열로 반환받고싶다거나 복사하고 싶을 때 Stack에 저장된 데이터들을 배열로 반환해주는 역할을 하기 위해 만들었다.

 

마지막으로 sort()메소드는 말 그대로 정렬해주는 메소드다.

 

 

 

 

1. clone() 메소드

 

만약 사용자가 사용하고 있던 Stack을 새로 하나 복제하고 싶을 때 쓰는 메소드다. 즉, 얕은 복사가 아닌 깊은 복사로 아예 다른 하나의 클론을 만드는 것이다.

단순히 = 연산자로 객체를 복사하게 되면 '주소'를 복사하는 것이기 때문에 복사한 객체에서 데이터를 조작할 경우 원본 객체까지 영향을 미친다. 즉 얕은 복사(shallow copy)가 된다는 것이다.

 

Stack<Integer> original = new Stack<>();
original.push(10);	// original에 10추가 

Stack<Integer> copy = original;
copy.push(20);	// copy에 20추가

System.out.println("original Stack");
int i = 0;
for(Object a : original.toArray()) {
	System.out.println("index " + i + " data = " + a);
	i++;
}

System.out.println("\ncopy Stack");
i = 0;
for(Object a : copy.toArray()) {
	System.out.println("index " + i + " data = " + a);
	i++;
}

System.out.println("original Stack reference : " + original);
System.out.println("copy Stack reference : " + copy);

 

 

[결과]

보다시피 객체의 주소가 복사되는 것이기 때문에 주소와 데이터 모두 같아져버리는 문제가 발생한다.

 

 

이러한 것을 방지하기 위해서 깊은 복사를 하는데, 이 때 필요한 것이 바로 clone()이다. Object에 있는 메소드이지만 접근제어자가 protected로 되어있어 구현해야 할 경우 반드시 Cloneable 인터페이스를 implement 해야한다.

 

즉, public class Stack<E> implements StackInterface<E> 에 Cloneable도 추가해주어야 한다.

그리고나서 clone()을 구현하면 되는데, 다음과 같이 재정의를 하면 된다.

@Override
public Object clone() throws CloneNotSupportedException {
		
	// 새로운 스택 객체 생성 
	Stack<?> cloneStack = (Stack<?>) super.clone();
		
	// 새로운 스택의 배열도 생성해주어야 함(내부 객체는 깊은 복사가 되지 않기 때문)
	cloneStack.array = new Object[size];
		
	// 현재 배열을 새로운 스택의 배열에 값을 복사함 
	System.arraycopy(array, 0, cloneStack.array, 0, size);
	return cloneStack;
}

 

조금 어려워 보일 수 있는데, 이해하지 못해도 된다. Stack에서 중요한 부분은 아니니... 다만 깊은 복사를 해주고 싶다면 구현해주는 것이 당연 좋긴 하다.

 

설명을 덧붙이자면, super.clone() 자체가 생성자 비슷한 역할이고 shallow copy를 통해 사실상 new Stack() 를 호출하는 격이라 제대로 완벽하게 복제하려면 clone한 스택의 array 또한 새로 생성해서 해당 배열에 copy를 해주어야 한다.

 

 

위와같이 만들고 나서 clone()한 것 까지 포함해서 테스트를 해보자.

 

Stack<Integer> original = new Stack<>();
original.push(10);	// original에 10추가 

Stack<Integer> copy = original;
Stack<Integer> clone = (Stack<Integer>) original.clone();

copy.push(20);	// copy에 20추가
clone.push(30);	// clone에 30추가

System.out.println("original Stack");
int i = 0;
for(Object a : original.toArray()) {
	System.out.println("index " + i + " data = " + a);
	i++;
}

System.out.println("\ncopy Stack");
i = 0;
for(Object a : copy.toArray()) {
	System.out.println("index " + i + " data = " + a);
	i++;
}

System.out.println("\nclone Stack");
i = 0;
for(Object a : clone.toArray()) {
	System.out.println("index " + i + " data = " + a);
	i++;
}

System.out.println("\noriginal stack reference : " + original);
System.out.println("copy stack reference : " + copy);
System.out.println("clone stack reference : " + clone);

 

 

[결과]

 

결과적으로 clone으로 복사한 Stack는 원본 Stack에 영향을 주지 않는다. 

 

 

 

 

 

 

 

 

2. toArray() 메소드

 

toArray()는 크게 두 가지가 있다.

하나는 아무런 인자 없이 현재 있는 Stack의 리스트를 객체배열(Object[]) 로 반환해주는 Object[] toArray() 메소드가 있고,

다른 하나는 Stack를 이미 생성 된 다른 배열에 복사해주고자 할 때 쓰는 T[] toArray(T[] a) 메소드가 있다.

 

즉 차이는 이런 것이다.

 

Stack<Integer> stack = new Stack<>();

// get Stack to array (using toArray())
Object[] Stack1 = stack.toArray();

// get Stack to array (using toArray(T[] a)
Integer[] Stack2 = new Integer[10];
stack2 = stack.toArray(Stack2);

 

1번의 장점이라면 Stack에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환된다는 점이다.

2번의 장점이라면 객체 클래스로 상속관계에 있는 타입이거나 Wrapper(Integer -> int) 같이 데이터 타입을 유연하게 캐스팅할 여지가 있다는 것이다. 또한 스택에 원소 5개가 있고,stack2 배열에 10개의 원소가 있다면 stack2에 0~4 index에 원소가 복사되고, 그 외의 원소는 기존 stack2배열에 초기화 되어있던 원소가 그대로 남는다.

 

두 메소드 모두 구현해보자면 다음과 같다.

 

public Object[] toArray() {
	return Arrays.copyOf(array, size);
}
	
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
	if (a.length < size)
		return (T[]) Arrays.copyOf(array, size, a.getClass());

	System.arraycopy(array, 0, a, 0, size);

	return a;
}

 

 

Object[] toArray() 메소드의 경우 원본배열(array)를 요소 개수(size)만큼 복사하여 Object[] 배열을 반환해주는 메소드다. 이 것을 그대로 써서 반환해주면 되기 때문에 크게 어렵지 않다.

 

두 번째 T[] toArray(T[] a) 메소드를 보자.

이 부분은 제네릭 메소드로, 우리가 만들었던 Stack의 E타입하고는 다른 제네릭이다. 예로들어 E Type이 Integer라고 가정하고, T타입은 Object 라고 해보자.

Object는 Integer보다 상위 타입으로, Object 안에 Integer 타입의 데이터를 담을 수도 있다. 이 외에도 사용자가 만든 부모, 자식 클래스 같이 상속관계에 있는 클래스들에서 하위 타입이 상위 타입으로 데이터를 받고 싶을 때 쓸 수 있도록 하기 위함이다.

즉, 상위타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭메소드를 구성하는 것이다.

 

그리고, 들어오는 배열(a)가 현재 array의 요소 개수(size)보다 작으면 size에 맞게 a의 공간을 재할당 하면서 array에 있던 모든 요소를 복사한다.

 

쉽게 이해해보면 Stack의 array의 요소가 4개 {1, 2, 3, 4} 있다고 치자. 그리고 Object[] copy = new Object[1]라는 배열을 하나 만들었는데, 공간이 한 개 밖에 없다.

그러면 array의 요소 1개만 복사하는 것이 아니라 copy 배열의 사이즈가 1에서 4로 증가하여 copy배열에 {1, 2, 3, 4}가 모두 담기게 되는 것이다.

 

또한 앞서 상위타입에 대해서도 담을 수 있도록 하기 위해 copyOf메소드에서 Class라는 파라미터를 마지막에 넣어준다.(a.getClass()) 그런다음 Object[] 배열로 리턴 된 것을 T[] 타입으로 캐스팅하여 반환해주면 된다.

 

반대로 파라미터로 들어오는 배열의 크기가 현재 Stack에 있는 array보다 크다면 앞 부분부터 array에 있던 요소만 복사해서 a배열에 넣고 반환해주면 된다.

 

 

 

 

 

 

 

3. sort() 메소드

 

 

 

이 부분은 ArrayList에서는 따로 다루지는 않았으나 이왕 구현하는김에 한 번 설명하도록 하겠다.

 

만약 LinkedList글을 읽었었다면 대강 구조는 알 것이다. (참고 : st-lab.tistory.com/167)

 

 

 

일단 자바의 비교기에 대해 알아야 한다.

자바의 데이터 정렬을 위한 비교기는 크게 두 가지가 있다. 하나는 Comparable, 다른 하나는 Comparator다. 정말정말 쉽게 말하자면 Comparable을 쓰는 경우는 해당 객체의 기본 정렬 방법을 설정할 때이고, Comparator의 경우는 특정한 경우에 임시적으로 쓸 수 있게 정렬을 정의할 때 쓰인다.

 

 

우리가 흔히 쓰는 int[] 배열, String[] 배열 등 수많은 클래스들은 기본적으로 자체 정렬 방식을 지원하기 때문에 Comparator을 쓰지 않아도 정렬 할 수 있었다.

 

만약 래퍼(Wrapper) 클래스 타입(ex. Integer, String, Double ...)이라면 따로 Comparator 을 구현해주지 않아도 되지만, 사용자 클래스, 예로들어 Student 클래스를 만든다거나.. 이러한 경우는 사용자가 따로 해당 객체에 Comparable를 구현해주거나 또는 Comparator를 구현해주어 파라미터로 넘겨주어야 한다.

 

Arrays.sort() 메소드를 뜯어본 분들은 알겠지만 Arrays.sort()의 종류중에서는 인자를 두 개 받는 경우가 있다. 정렬을 해보신 분은 알겠지만 가끔 2차원 배열을 정렬하고 싶을 때 다음과 같이 쓰지 않았는가?

 

int[][] arr = new int[10][10];

Arrays.sort(arr, new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		// 구현부
	}
});

 

이러한 메소드가 바로 아래 사진의 메소드로 간다.

 

 

 

위 사진을 보면 크게 if(c == null) 일 경우와 아닌 경우로 나뉜다.

즉, Comparator 인자가 있는지, 또는 없는지를 말해주는데, Comparator 인자(c)가 없는 경우 해당 객체의 Comparable 구현이 있는지를 확인하고 있으면 정렬하며, 구현되지 않았을 경우 에러를 뱉는다.

 

결과적으로 sort() 메소드를 만들 때, 기본적으로 두 가지 경우를 생각해야 한다는 것이다. 첫 번째는 객체에 Comparable이 구현되어 있어 따로 파라미터로 Comparator를 넘겨주지 않는 경우고, 다른 하나는 Comparator을 넘겨주어 정의 된 정렬 방식을 사용하는 경우다.

 

public void sort() {
	/**
	 *  Comparator를 넘겨주지 않는 경우 해당 객체의 Comparable에 구현된
	 *  정렬 방식을 사용한다.
	 *  만약 구현되어있지 않으면 cannot be cast to class java.lang.Comparable
	 *  에러가 발생한다.
	 *  만약 구현되어있을 경우 null로 파라미터를 넘기면
	 *  Arrays.sort()가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
	 */
	sort(null);
}

@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
	Arrays.sort((E[]) array, 0, size, c);
}

 

여기서 Comparator<? super E> 는 상속관계이면서 부모 클래스에서 정렬 방식을 따르는 경우도 생각하여 <? super E>로 하였다. 이러한 경우를 고려하지 않는다면 Comparator<E>로 해주어도 종속관계 영향을 안받는 객체의 경우는 괜찮다.

 

그런다음 Object[] 배열을 Arrays.sort()메소드를 통해 정렬해주면 된다.

 

이때 Comparator를 넘겨주는 방식은 크게 두 가지가 있는데, 그 중 하나인 Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) 를 쓸 것이다.

관련 API 문서는 아래 링크로 남겨두겠다.

 

docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html#sort(T%5B%5D,int,int,java.util.Comparator)

 

Arrays (Java SE 11 & JDK 11 )

Compares two int arrays lexicographically over the specified ranges. If the two arrays, over the specified ranges, share a common prefix then the lexicographic comparison is the result of comparing two elements, as if by Integer.compare(int, int), at a rel

docs.oracle.com

 

 

 

그럼 한 번 테스트를 해보자. 

 

Student 클래스를 통해 이름과 성적을 입력받고, 이를 정렬하는 테스트를 해보도록 한다.

 

<Student 클래스가 Comparable을 구현하지 않았을 경우>

 

[Test.java]

package _04_Stack;


public class Test {

	public static void main(String[] args) {
		Stack<Student> stack = new Stack<>();

		stack.push(new Student("김자바", 92));
		stack.push(new Student("이시플", 72));
		stack.push(new Student("조시샵", 98));
		stack.push(new Student("파이손", 51));
		
		stack.sort();
		
		for(Object a : stack.toArray()) {
			System.out.println(a);
		}
	}
}

class Student {
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}
}

 

[결과]

 

이렇게 Comparable을 구현하지 않아 해당 객체의 정렬 방법을 몰라 빨갛게 에러를 뱉어준다. 즉, 명시적으로 Arrays.sort()에 정렬 방법을 알려주던가, Student 클래스에 정렬 방법을 구현하던가 해야한다.

 

 

 

 

 

 

<Comparator의 구현을 통해 명시적으로 Arrays.sort()에 파라미터로 넘기는 방법>

 

[Test.java]

package _04_Stack;

import java.util.Comparator;

public class Test {

	public static void main(String[] args) {
		Stack<Student> stack = new Stack<>();

		stack.push(new Student("김자바", 92));
		stack.push(new Student("이시플", 72));
		stack.push(new Student("조시샵", 98));
		stack.push(new Student("파이손", 51));
		
		stack.sort(customComp);	// Comparator을 넘겨준다. 
		
		for(Object a : stack.toArray()) {
			System.out.println(a);
		}
	}
	
	// 사용자 설정 comparator(비교기)
	static Comparator<Student> customComp = new Comparator<Student>() {
		@Override
		public int compare(Student o1, Student o2) {
			return o2.score - o1.score;
		}
	};
}

class Student {
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}
}

 

 

이렇게 하면 정렬이 될까? 당연하겠지만 된다.

 

 

[결과]

 

 

 

 

 

 

<Comparable의 구현을 통해 객체의 정렬 방법을 설정하는 방법>

 

객체 기본 정렬방식을 설정해주는 방법. 즉 Comparable 구현 방법으로도 가능하다.

 

package _04_Stack;

public class Test {

	public static void main(String[] args) {
		Stack<Student> stack = new Stack<>();

		stack.push(new Student("김자바", 92));
		stack.push(new Student("이시플", 72));
		stack.push(new Student("조시샵", 98));
		stack.push(new Student("파이손", 51));
		
		stack.sort();	// Comparator 인자가 필요하지 않음
		
		for(Object a : stack.toArray()) {
			System.out.println(a);
		}
	}
	
}

class Student implements Comparable<Student> {
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}

	@Override
	public int compareTo(Student o) {
		return o.score - this.score;
	}
}

 

 

이러면 sort() 내부에서 Comparator가 없으니 해당 클래스의 Comparable에서 compareTo() 을 구현한 내용을 찾아 작성한대로 정렬을 해준다.

 

[결과]

 

참고로 ArrayList 구현 할 때에도 sort() 메소드를 구현하고 싶다면 위와 같은 방법으로 구현하면 된다.

 

 

 

 

 

 

[clone, toArray, sort 메소드 묶어보기]

 

더보기

 

@Override
public Object clone() throws CloneNotSupportedException {
	Stack<?> cloneStack = (Stack<?>) super.clone();	
	cloneStack.array = new Object[size];

	System.arraycopy(array, 0, cloneStack.array, 0, size);
	return cloneStack;
}

	
public Object[] toArray() {
	return Arrays.copyOf(array, size);
}
	
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
	if (a.length < size)
		return (T[]) Arrays.copyOf(array, size, a.getClass());

	System.arraycopy(array, 0, a, 0, size);

	return a;
}
    
public void sort() {
	/**
	 *  Comparator를 넘겨주지 않는 경우 해당 객체의 Comparable에 구현된
	 *  정렬 방식을 사용한다.
	 *  만약 구현되어있지 않으면 cannot be cast to class java.lang.Comparable
	 *  에러가 발생한다.
	 *  만약 구현되어있을 경우 null로 파라미터를 넘기면
	 *  Arrays.sort()가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
	 */
	sort(null);
}

@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
	Arrays.sort((E[]) array, 0, size, c);
}

 

 

 

 

 

 

 

 

 






  • 전체 코드

 



 

import java.util.Arrays;
import java.util.Comparator;
import java.util.EmptyStackException;

import Interface_form.StackInterface;

/**
 * 
 * @author (st-lab.tistory.com)
 *
 * @param <E> the type of elements in this stack
 */

public class Stack<E> implements StackInterface<E>, Cloneable {

	private static final int DEFAULT_CAPACITY = 10;	// 최소(기본) 용적 크기 
	private static final Object[] EMPTY_ARRAY = {};	// 빈 배열 
	
	private Object[] array;	// 요소를 담을 배열  
	private int size;	// 요소 개수 
	
	
	// 생성자1 (초기 공간 할당 X) 
	public Stack() {
		this.array = EMPTY_ARRAY;
		this.size = 0;
	}
	
	// 생성자2 (초기 공간 할당 O) 
	public Stack(int capacity) {
		this.array = new Object[capacity];
		this.size = 0;
	}
	
	

	private void resize() {
		
		// 빈 배열일 경우 (capacity is 0)
		if(Arrays.equals(array, EMPTY_ARRAY)) {
			array = new Object[DEFAULT_CAPACITY];
			return;
		}
		
		int arrayCapacity = array.length;	// 현재 용적 크기 
		
		// 용적이 가득 찰 경우
		if(size == arrayCapacity) {
			int newSize = arrayCapacity * 2;
			
			// 배열 복사
			array = Arrays.copyOf(array, newSize);
			return;
		}
		
		// 용적의 절반 미만으로 요소가 차지하고 있을 경우
		if(size < (arrayCapacity / 2)) {
			
			int newCapacity = (arrayCapacity / 2);
			
			// 배열 복사
			array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, newCapacity));
			return;
		}
	}
	
	@Override
	public E push(E item) {
		
		// 용적이 꽉 차있다면 용적을 재할당 해준다. 
		if (size == array.length) {
			resize();
		}
		array[size] = item;	// 마지막 위치에 요소 추가 
		size++;	// 사이즈 1 증가 
		
		return item;
	}

	@Override
	public E pop() {
		
		// 만약 삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시키기
		if(size == 0) {
			throw new EmptyStackException();
		}
		
		@SuppressWarnings("unchecked")
		E obj = (E) array[size - 1];	// 삭제될 요소를 반환하기 위한 임시 변수 
		
		array[size - 1] = null;	// 요소 삭제 
		
		size--;	// 사이즈 1 감소 
		resize();	// 용적 재할당 
		
		return obj;
	}


	@SuppressWarnings("unchecked")
	@Override
	public E peek() {
		// 만약 삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시키기
		if(size == 0) {
			throw new EmptyStackException();
		}
		
		return (E) array[size - 1];
	}

	@Override
	public int search(Object value) {

		// value가 null일 때는 eqauls(null)이되어 null pointer exception이 발생할 수 있으니,
		// == 로 null값을 비교해준다.
		if(value == null) {
			for(int idx = size - 1; idx >= 0; idx--) {
				if(array[idx] == null) {
					return size - idx;
				}
			}
		} else {
			for(int idx = size - 1; idx >= 0; idx--) {
		
				// 같은 객체를 찾았을 경우 size - idx 값을 반환 
				if(array[idx].equals(value)) {
					return size - idx;
				}
			}
		}
		return -1;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public void clear() {
		
		// 저장되어있던 모든 요소를 null 처리 해준다.
		for(int i = 0; i < size; i++) {
			array[i] = null;
		}
		size = 0;
		resize();
	}
	
	@Override
	public boolean empty() {
		return size == 0;
	}
	
	@Override
	public Object clone() throws CloneNotSupportedException {
		
		// 새로운 스택 객체 생성 
		Stack<?> cloneStack = (Stack<?>) super.clone();
		
		// 새로운 스택의 배열도 생성해주어야 함(내부 객체는 깊은 복사가 되지 않기 때문)
		cloneStack.array = new Object[size];
		
		// 현재 배열을 새로운 스택의 배열에 값을 복사함 
		System.arraycopy(array, 0, cloneStack.array, 0, size);
		return cloneStack;
	}

	
	public Object[] toArray() {
		return Arrays.copyOf(array, size);
	}
	
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            return (T[]) Arrays.copyOf(array, size, a.getClass());

        System.arraycopy(array, 0, a, 0, size);

        return a;
    }
    
    
	public void sort() {
		/**
		 *  Comparator를 넘겨주지 않는 경우 해당 객체의 Comparable에 구현된
		 *  정렬 방식을 사용한다.
		 *  만약 구현되어있지 않으면 cannot be cast to class java.lang.Comparable
		 *  에러가 발생한다.
		 *  만약 구현되어있을 경우 null로 파라미터를 넘기면
		 *  Arrays.sort()가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
		 */
		sort(null);
	}

	@SuppressWarnings("unchecked")
	public void sort(Comparator<? super E> c) {
		Arrays.sort((E[]) array, 0, size, c);
	}
    
}

 

 

 

 

 

 

 

 

 

 

 

 

 

[ArrayList를 상속한 Stack]

 

 

 

Stack 에 대한 기본 자료구조는 끝났다.

 

이 부분은 앞서 맨 처음에 Stack은 Vector를 상속받는다고 했고, Vector는 ArrayList와 구조가 유사하다고 했다. (차이점은 동기화를 지원하냐 안하냐가 가장 크다.)

 

그러면 우리가 앞서 구현했던 ArrayList를 상속하여 쓸 수도 있지 않겠는가? 그러면 ArrayList에 있는 메소드들도 쓸 수 있고, 기본 구조는 크게 다르지 않아 별다르게 구현을 따로 해줄 부분이 별로 없기 때문에 훨씬 쉽게 구현이 가능할 것이다.

 

일단 어레이리스트 (ArrayList) 구현하기 를 보고 오시길 바란다.

 

ArrayList 클래스의 구현부는 더보기로 남겨놓겠다.

더보기

 

package _01_ArrayList;

import Interface_form.List;
import java.util.Arrays;

/**
 * 
 * @author (st-lab.tistory.com)
 *
 * @param <E> the type of elements in this list
 */

public class ArrayList<E> implements List<E>, Cloneable {


	private static final int DEFAULT_CAPACITY = 10;	// 최소(기본) 용적 크기 
	private static final Object[] EMPTY_ARRAY = {};	// 빈 배열
    
	private int size;	// 요소 개수 

	Object[] array;	// 요소를 담을 배열 

	// 생성자1 (초기 공간 할당 X)
	public ArrayList() {
		this.array = EMPTY_ARRAY;
		this.size = 0;

	}

	// 생성자2 (초기 공간 할당 O)
	public ArrayList(int capacity) {
		this.array = new Object[capacity];
		this.size = 0;
	}

	
	private void resize() {
		int array_capacity = array.length;

		// if array's capacity is 0
		if (Arrays.equals(array, EMPTY_ARRAY)) {
			array = new Object[DEFAULT_CAPACITY];
			return;
		}

		// 용량이 꽉 찰 경우  
		if (size == array_capacity) {
			int new_capacity = array_capacity * 2;

			// copy
			array = Arrays.copyOf(array, new_capacity);
			return;
		}
		// 용적의 절반 미만으로 요소가 차지하고 있을 경우 
		if (size < (array_capacity / 2)) {
			int new_capacity = array_capacity / 2;

			// copy
			array = Arrays.copyOf(array, Math.max(new_capacity, DEFAULT_CAPACITY));
			return;
		}
	}
	
	@Override
	public boolean add(E value) {
		addLast(value);
		return true;
	}

	public void addLast(E value) {

		// 꽉차있는 상태라면 용적 재할당
		if (size == array.length) {
			resize();
		}
		array[size] = value;	// 마지막 위치에 요소 추가
		size++;	// 사이즈 1 증가
	}


	@Override
	public void add(int index, E value) {

		if (index > size || index < 0) {	// 영역을 벗어날 경우 예외 발생 
			throw new IndexOutOfBoundsException();
		}
		if (index == size) {	// index가 마지막 위치라면 addLast 메소드로 요소추가
			addLast(value);
		} 
		else {
				
			if(size == array.length) {	// 꽉차있다면 용적 재할당
				resize();
			}
				
			// index 기준 후자에 있는 모든 요소들 한 칸씩 뒤로 밀기
			for (int i = size; i > index; i--) {
				array[i] = array[i - 1];
			}

			array[index] = value;	// index 위치에 요소 할당
			size++;
		}
	}
	
	public void addFirst(E value) {
		add(0, value);
	}

	
	@SuppressWarnings("unchecked")
	@Override
	public E get(int index) {
		if(index >= size || index < 0) {	// 범위 벗어나면 예외 발생
			throw new IndexOutOfBoundsException();
		}
		// Object 타입에서 E타입으로 캐스팅 후 반환
		return (E) array[index];
	}

	 
	@Override
	public void set(int index, E value) {
		if (index >= size || index < 0) {	// 범위를 벗어날 경우 예외 발생
			throw new IndexOutOfBoundsException();
		} 
		else {
			// 해당 위치의 요소를 교체
			array[index] = value;
		}
	}
	
	
	@Override
	public int indexOf(Object value) {
		int i = 0;
	    
		// value와 같은 객체(요소 값)일 경우 i(위치) 반환
		for (i = 0; i < size; i++) {
			if (array[i].equals(value)) {
				return i;
			}
		}
		// 일치하는 것이 없을경우 -1을 반환
		return -1;
	}

	public int lastIndexOf(Object value) {
		for(int i = size - 1; i >= 0; i--) {
			if(array[i].equals(value)) {
				return i;
			}
		}
		return -1;
	}
	
	
	@Override
	public boolean contains(Object value) {

		// 0 이상이면 요소가 존재한다는 뜻
		if(indexOf(value) >= 0) {
			return true;
		}
		else {
			return false;
		}
	}



	@SuppressWarnings("unchecked")
	@Override
	public E remove(int index) {

		if (index >= size || index < 0) {
			throw new IndexOutOfBoundsException();
		}

		E element = (E) array[index];	// 삭제될 요소를 반환하기 위해 임시로 담아둠
		array[index] = null;
	    
		// 삭제한 요소의 뒤에 있는 모든 요소들을 한 칸씩 당겨옴
		for (int i = index; i < size; i++) {
			array[i] = array[i + 1];
			array[i + 1] = null;
		}
		size--;
		resize();
		return element;
	}

	@Override
	public boolean remove(Object value) {

		// 삭제하고자 하는 요소의 인덱스 찾기
		int index = indexOf(value);

		// -1이라면 array에 요소가 없다는 의미이므로 false 반환
		if (index == -1) {
			return false;
		}

		// index 위치에 있는 요소를 삭제
		remove(index);
		return true;
	}


	@Override
	public int size() {
		return size;	// 요소 개수 반환
	}
	
	@Override
	public boolean isEmpty() {
		return size == 0;	// 요소가 0개일 경우 비어있다는 의미이므로 true반환
	}

	@Override
	public void clear() {
		// 모든 공간을 null 처리 해준다. 
		for (int i = 0; i < size; i++) {
			array[i] = null;
		}
		size = 0;
		resize();
	}

	
	// 부록 메소드
	@Override
	public Object clone() throws CloneNotSupportedException {

		// 새로운 객체 생성
		ArrayList<?> cloneList = (ArrayList<?>)super.clone();

		// 새로운 객체의 배열도 생성해주어야 함 (객체는 얕은복사가 되기 때문)
		cloneList.array = new Object[size];

		// 배열의 값을 복사함
		System.arraycopy(array, 0, cloneList.array, 0, size);

		return cloneList;
	}


	@SuppressWarnings("unchecked")
	public void sort() {
		final E[] copy = (E[])this.toArray();
		Arrays.sort(copy);
		this.array = copy;
	}


	public Object[] toArray() {
		return Arrays.copyOf(array, size);
	}
		

	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
		if (a.length < size) {
			// copyOf(원본 배열, 복사할 길이, Class<? extends T[]> 타입)
			return (T[]) Arrays.copyOf(array, size, a.getClass());
		}
		// 원본배열, 원본배열 시작위치, 복사할 배열, 복사할배열 시작위치, 복사할 요소 수 
		System.arraycopy(array, 0, a, 0, size);
		return a;
	}
	
}

 

 

 

 

그럼 한 번 해보도록 하자. 클래스 이름은 StackExtendArrayList로 하겠다.

 

맨 처음 구현했을 때 처럼  작성했던 List 인터페이스를 implements 해준다. 그리고 ArrayList를 상속하기 위해 extends ArrayList를 해준다. (필자의 경우 필자가 구현한 ArrayList는 _01_ArrayList라는 패키지에 있으므로 해당 경로의 ArrayList를 import해준다.)

 

 

[StackExtendArrayList.java]

public class StackExtendArrayList<E> extends ArrayList<E> implements StackInterface<E> {

	// 초기 용적 할당 X
    public StackExtendArrayList() {
    	super();
    }
    
	// 초기 용적 할당 O
    public StackExtendArrayList(int capacity) {
    	super(capacity);
    }
}

 

 

그리고 우리가 ArrayList에서도 용적을 초기에 할당하느냐 안하느냐를 나눴기 때문에 위 클래스에서도 생성자를 둘로 나눠 각각 상황에 맞게 super()로 ArrayList 생성자로 보내도록 하자.

 

 

그리고 우리가 구현해야 할 것은 크게 'push', 'pop', 'peek', 'search', 'size', 'empty' 였다.

 

여기서 size메소드는 부모클래스(ArrayList)와 이름이 같으므로 따로 구현하지 않아도 size()메소드 호출이 가능하니 이 것만 제외하면 총 5개만 구현해주면 된다.

 

기존에 ArrayList에 구현되어 있는 메소드들을 활용하면 끝나기 때문에 한 번에 보여주도록 하겠다.

 

 

import java.util.EmptyStackException;

import Interface_form.StackInterface;
import _01_ArrayList.ArrayList;

/**
 * 
 * @author (st-lab.tistory.com)
 *
 * @param <E> the type of elements in this stack
 */

public class StackExtendArrayList<E> extends ArrayList<E> implements StackInterface<E> {

    public StackExtendArrayList() {
    	super();
    }
    
    public StackExtendArrayList(int capacity) {
    	super(capacity);
    }

	@Override
	public E push(E item) {
		addLast(item);	// ArrayList의 addLast() 
		return item;
	}

	@Override
	public E pop() {
		int length = size();
		E obj = remove(length - 1);	// ArrayList의 remove() 
		
		return obj;
	}

	@Override
	public E peek() {
		
		int length = size();
        if (length == 0)
            throw new EmptyStackException();
        
		E obj = get(length - 1);	// ArrayList의 get() 
		
		return obj;
	}

	@Override
	public int search(Object value) {
		int idx = lastIndexOf(value);	// ArrayList의 lastIndexOf() 
		
		if(idx >= 0) {
			return size() - idx;
		}
		return -1;
	}

	@Override
	public boolean empty() {
		return size() == 0;
	}
}

 

 

 

 

이렇게 아주아주 쉽게 구현 가능하다.

 

아래 깃허브에서도 소스 코드를 편리하게 보실 수 있다. 또한 깃허브에 올라가는 코드들은 조금 더 기능을 추가하거나 수정되어 올라가기에 약간의 차이는 있을 수 있지만 전체적인 구조는 바뀌지 않으니 궁금하시거나 참고하실 분들은 아래 링크로 가서 보시는 걸 추천한다.

 

이 번 Stack 코드는 ArrayList를 상속한 코드로 올라갈 예정이다. 만약 상속받지 않고 더 많은 코드를 구현하고 싶은 경우 ArrayList의 메소드들을 그대로 복사해서 가져다 써도 무방하다.

 

 

 

[소스코드 모아보기]

 

github 자료구조 모음

 

kdgyun/Data_Structure

Contribute to kdgyun/Data_Structure development by creating an account on GitHub.

github.com

 

 

 

 

 

 

 







  • 정리

 



Stack에 대한 기본적인 메소드를 구현해보았다. 또한 ArrayList를 상속받아 활용하는 방법까지.. 물론 이 방법이 항상 정답은 아니지만, 최대한 이해하기 쉽게 메소드를 구현하려고 노력했다.

 

특히나 우리가 기존에 구현해놓은 클래스들을 재활용 할 수 있다는 점은 매우 큰 장점이라는 것을 알아두셨으면 좋겠다. 또한 필자가 참고하라는 글은 어지간하면 참고하면 좋다. 만약 이미 알고있던 내용이라면 크게 문제는 안되지만 보통은 필자의 포스팅을 차례대로 보는 사람은 드물기 때문에..

 

 

 

또한 어렵거나 이해가 안되는 부분, 또는 질문이 있다면 언제든 댓글을 남겨주시면 된다. 최대한 빠르게 답변드리겠다.

 

 

 

 

 

 

 

저작자표시 비영리 변경금지

'자료구조 > Java' 카테고리의 다른 글

자바 [JAVA] - 배열을 이용한 Queue (큐) 구현하기  (27) 2020.12.07
자바 [JAVA] - Queue Interface (큐 인터페이스)  (2) 2020.12.01
자바 [JAVA] - Stack Interface (스택 인터페이스)  (12) 2020.11.19
자바 [JAVA] - Doubly LinkedList (이중 연결리스트) 구현하기  (12) 2020.11.18
자바 [JAVA] - Singly LinkedList (단일 연결리스트) 구현하기  (41) 2020.11.08

티스토리툴바