자바 [JAVA] - Stack Interface (스택 인터페이스)

 

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

 

 

 

 0. 자바 컬렉션 프레임워크 (Java Collections Framework)

 1. 리스트 인터페이스 (List Interface)

 2. 어레이리스트 (ArrayList)

 3. 단일 연결리스트 (Singly LinkedList)

 4. 이중 연결리스트 (Doubly LinkedList)

 5. 스택 인터페이스 (Stack Interface) - [현재 페이지]

 6. 스택 (Stack)

 7. 큐 인터페이스 (Queue Interface)

 8. 배열 큐 (Array Queue)

 9. 연결리스트 큐 (LinkedList Queue)

10. 배열 덱 (Array Deque)

11. 연결리스트 덱 (LinkedList Deque)

12. 힙 (Heap)

13. 우선순위 큐 (PriorityQueue)

14. 셋 인터페이스 (Set Interface)

15. 해시 셋 (Hash Set)

16. 연결 해시 셋 (Linked Hash Set)

17. 이진 탐색 트리 (Binary Search Tree)

 

 

 

 

 

 

 

---

 

• Stack Interface

 

 

 

 

 

만약 이 글을 처음 접한다면 자바 컬렉션 프레임워크 (Java Collections Framework) 글을 먼저 보고 오셨으면 한다.

 

 

이 번에는 스택 자료구조를 포스팅 하기 전에 스택 인터페이스를 하나 만들고 시작하려 한다. Interface 장점이 해당 인터페이스를 implements 하는 클래스는 인터페이스에 선언 된 메소드들을 강제적으로 구현하도록 하고 있기 때문에 깜빡 잊어먹고 구현을 안하는 실수를 방지할 수 있다.

 

 

일단 스택(Stack)에 대해 간략하게 설명하겠다.

 

Stack은 말 그대로 '~을 쌓다'는 의미다. 

좀 더 쉽게 이해하자면 여러분들이 벽돌을 쌓는다고 생각해보자. 그러면 먼저 들어온 벽돌은 가장 아래에 위치할 것이고, 가장 나중에 들어온 벽돌은 가장 위에 위치할 것이다.

그리고 다시 이 벽돌들을 치운다고 생각해보자. 그러면 하단에 있는 벽돌부터 뺄 것인가? 물론 가능은 하겠지만 보통같으면 위에 있는 벽돌들부터 빼낼 것이다.

 

이렇게 먼저 들어온 데이터가 마지막에 나가는 구조를 후입선출(LIFO = Last in First out) 또는 선입후출(FILO = First in Last out)이라고 한다. (둘 다 같은 말이다.)

 

한 번쯤 코딩하다보면 'java.lang.StackOverflowError' 를 경험할텐데 보통은 재귀가 깊어지면서 발생할 것이다. 이는 메소드를 호출 할 때마다 메소드 내에 정의 된 변수들의 값이 stack 메모리에 쌓이게 되는데 재귀가 깊어지면 stack 메모리에 이 값들이 쌓이면서 해당 총량이 할당 된 메모리 양보다 커질 때 내뱉게 된다.

 

 

 

참고로 자바 내부에서는 스택은 Vector 클래스를 상속받아 사용한다. Vector 자료구조는 ArrayList와 크게 다르지 않다. 내부 구조는 Object[] 배열로 데이터들을 관리하며 전체적인 메소드 구조 또한 많이 유사하다. 다만 차이점은 동기화를 지원하냐 안하냐의 여부인데, ArrayList에서는 동기화를 지원하지 않고, Vector에서는 동기화를 지원한다. 그렇다보니 속도 자체는 ArrayList가 조금 더 빠르지만, Thread safe 하지 않다.

 

쉽게 생각해서 멀티스레드 환경에서는 Vector를, 아닐경우 ArrayList를 쓰는 것이 현명하다.

 

여기서는 자료구조에 중점을 둘 것이라 동기화나 Vector를 상속하는 것 까지는 고려하진 않을 것이다. 만약 ArrayList를 구현했었다면 ArrayList를 상속받아 쉽게 구현할 수 있으니 응용해보는 것도 좋을 것이다.

 

 

 

 

그럼 실생활에서 Stack과 같은 형태는 어떻게 응용되고 있을까?

 

 

[Stack의 활용]

1. 페이지 뒤로가기

2. 실행 취소

3. 수식 괄호 검사

 

가장 대표적인 것은 위 3개일 것이다.

 

페이지 뒤로가기는 우리가 대표적으로 가장 친숙하게 이용하는 스택 자료구조 형태다. 가장 최근에 방문했던 페이지가 가장 상단에 위치한다. 실행 취소(undo) 또한 마찬가지다.

 

수식 괄호 검사의 경우 처음 보는 분들에게는 조금 생소 할 수 있지만 괄호 검사를 가장 쉽게 할 수 있는 방법 중 하나다.

생각해보자. 여는 괄호'(' 가 있으면 반드시 닫는 괄호')' 가 있어야 한다. 어느 하나라도 부족하거나 많을 경우 올바른 수식을 완성 할 수 없다.

 

이 예시는 이후 백준 문제풀이에서 다뤄보도록 하겠다.

 

 

 

 

그럼 이제 Stack 인터페이스에 구현된 메소드들을 살펴보아야 겠다. 여기서 모든 메소드들을 살펴볼 수는 없고, 몇가지 자주 사용하는 메소드들이 있다.

 

 

<Stack Interface에 선언된 대표적인 메소드>

 

 

 

 

그리고 중요한 것이 있다.

search() 메소드는 스택 내부 배열의 인덱스 값이 아니라 스택의 '상단으로부터 몇 번째에 위치 하는지'를 반환하는 것이다. 즉, 거리 개념이라고 보면 된다. 어떤 의미인지 모르겠다면 아래 인터페이스 구현에서 자세히 설명해놓았으니 참고하시길 바란다.

 

앞서 더보기를 통해 추가 설명을 들었다면 알겠지만, 자바에서는 Vector 클래스를 상속받다보니 위의 클래스보다 훨씬 많은 메소드를 지원한다. 즉, Vector 클래스에 있는 메소드 + 위에서 선언된 메소드를 합쳐야 하지만 이번에는 '스택'이 무엇인지에 좀 더 집중하고자 위의 메소드와 몇 가지 메소드를 추가하여 구현 할 것이다.

 

 

그럼 이를 토대로 앞으로 구현 할 인터페이스를 만들어보자. 또한 여러분들도 자료구조를 만들고자 할 때, 인터페이스들은 같은 프로젝트 폴더 안에 다른 package를 하나 만들어서 그 안에 모아놓는 것을 추천한다.(필자는 Interface_form이라는 패키지에 저장할 것이다.)

 

그리고 필자는 이를 토대로 앞으로 구현해나갈 것이니 참고하시길.

 

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();
}

 

 

 

 

이 번에 메인으로 구현할 스택의 경우 Stack 이라는 이름이 겹쳐 이번 파트에 한에서만 인터페이스 이름을 StackInterace로 할 것이다.

 

또한 기본적으로 여러분들이 재정의(Override), 예외처리(throw), 객체(Object), 인터페이스(nterface), 제네릭(Generic) 이렇게 5개에 대한 기본 지식은 있다는 전제하에 설명 할 것이다. 그렇지 않고 하나하나 설명하다보면 길이 너무 길어져 핵심을 못짚게 되어 결정했다.

 

 

 

 

 

 

---

• 정리

 

 

오늘은 간단하게 Stack에 대해 알아보고 앞으로 사용할 Stack Interface를 간단하게 만들어놓았다. 이를 토대로 Stack 클래스를 만들 것이다. 혹여 앞으로의 포스팅에 있어 모르거나 헷갈리는 것이 있다면 언제든 댓글 남겨주시면 감사하겠다.

 

물론 자료구조 자체가 프로그래밍 입문 후 대개 첫번째 난관으로 말할 만큼 쉽지는 않은 내용이긴하나, 필자도 최대한 쉽게 구현하고 만들 수 있도록 최대한 노력하겠다. 이러한 과정 중에 혹여 지적할 부분이 있다면 언제든 댓글 남겨주시면 빠르게 피드백하여 수정할 것은 수정하고, 보완할 점은 보완할 것이니 부담없이 댓글 남겨주시길 바란다.