자바(Java)로 구현한 스택 예제
 |
| 스택(Stack) 컨셉 |
스택(Stack)이란 무었인가?
스택은 같은 타입의 자료를 "하나 다음 하나"라는 컨셉으로 순차적으로 저장하는 직선형 자료 구조이다. 우리가 스택에서 자료를 추출하고 삽입할 때 우리는 순렬의 끝에만 접근이 가능하다. 위 그림을 잠시 보자. 새로운 데이터는 스택의 최상위에 위치하게되고, 데이터 추출시, 우리는 오직 가장 최근에 삽입된 데이터만(최상위) 접근이 가능하다. 이 이유때문에 스택은 보통 "LIFO(Last In First Out)" 구조 라는, 가장 최근에 들어간게 가장 먼져 나온다는 뜻을 가진 어문으로 표현되기도 한다.
스택(Stack)은 실제로 어디에 사용되는가?
- Operating Systems
- 프로그램에서 불러지는 함수(Method)들을 모두 Stack 이라는 자료형에 저장한다.
- Compilers(컴파일러)
- 컴파일러에서 수학기호들을 기계어(Machine Code)로 변환시, 괄호들을 매칭하거나 할 때.
- JVM(Java Virtual Machine)자바 가상 머신
- 자바 프로그램이 실행될 때 사용되는 JVM 에서도 스택은 사용된다. 각각의 스레드는 1개의 스택을 가지고 모든 메소드들을 트랙킹한다. 새로운 메소드들이 호출 될 때 마다, 새로운 프레임이 스택에 삽입되고, 메소드가 끝날 때 마다 스택에서 제거된다
스택(Stack)은 어떻게 구현될수 있을까?
앞에서 다룬 링크드 리스트와 달리 스택(Stack)은 추상 자료형(Abstract Data Type)이다. 추상 자료형이란 수학적 모델을 가진 자료형이고, 이는 곧 매우 다양한 방법으로 구현될 수 있음을 의미한다. 가장 자주 쓰이는 2가지 구현방법들은, ArrayList(어레이리스트)와 LinkedList(링크드 리스트)이다. 스택은 몇가지 필수적인 메소드들을 가지고 있는데 이는 아래와 같다
- pop(추출)
- 가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다
- 이 작업은 O(1)의 복잡도를 가진다
- push(삽입)
- 스택의 최 상위에 새로운 자료를 삽입한다
- 이 작업은 O(1)의 복잡도를 가진다
- isEmpty
- clear
- peek
- 가장 최 상위에 위치한 자료를 추출한다
- pop 메소드와는 달리 스택에서 제거하지는 않는다.
- 이 작업은 O(1)의 복잡도를 가진다
 |
| 스택 Push 메소드 |
 |
| 스택 Pop 메소드 |
아래는 자바의 어레이리스트 api(java.util.ArrayList)로 구현한 스택(Stack) 자료형 이다
public class StackWithArrayList {
import java.util.*;//import arrayList
public class StackWithArrayList {
private ArrayList stack;
/**
* 스택 인스턴스를 생성하는 컨스트럭터(Constructor)
*/
public StackWithArrayList() {
stack = new ArrayList();
}
/**
* 스택을 최소 사이즈 s 로 생성한다
*
* @param s 구현할 스택의 최소 사이즈
*/
public StackWithArrayList(int s) {
stack = new ArrayList();
stack.ensureCapacity(s);
}
/**
* 스택을 비운다
*/
public void clear() {
stack.clear();
}
/**
* 스택이 Empty 상태인지 확인한다
*
* @return 스택이 Empty 상태이면 true값을, 아니면 false 값을 반환한다.
*/
public boolean isEmpty() {
return stack.isEmpty();// 또는 "stack.size() == 0"를 이용할수도 있다
}
/**
* 새로운 요소를 삽입한다
*
* @param e 삽입될 새로운 요소
*/
public void push(Object e) {
stack.add(e);// ArrayList의 가장 마지막 index 에 새로운 요소를 삽입한다
}
/**
* 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
*
* @return 스택에서 가장 최 상위에 위치한 데이터
*/
public Object pop() {
if (isEmpty()) {// 우선 스택이 empty 인걸 확인한 하고
throw new EmptyStackException();
// 그렇다면 Exception 을 던진다
} else {
return stack.remove(stack.size() - 1);
// ArrayList.remove 메소드는 어레이에서 주어진 인덱스의 데이터를 제거후, 리턴한다
}
}
/**
* 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
*
* @return 스택에서 가장 최 상위에 위치한 데이터
*/
public Object peek() {
if (isEmpty()) {
throw new EmptyStackException();
} else {
return stack.get(stack.size() - 1);
// ArrayList.get 메소드는 주어진 인덱스에 저장된 값을 반환한다.
}
}
}
아래는 자바의 링크드리스트 api(java.util.LinkedList)로 구현한 스택(Stack) 자료형 이다
import java.util.EmptyStackException;
import java.util.LinkedList;
public class StackWithLinkedList {
private LinkedList stack;
public StackWithLinkedList() {
this.stack = new LinkedList();
}
/**
* 스택을 비운다
*/
public void clear() {
stack.clear();
}
/**
* 스택이 Empty 상태인지 확인한다
*
* @return 스택이 Empty 상태이면 True 값을, 아니면 false 값을 리턴한다
*/
public boolean isEmpty() {
return stack.isEmpty();// 또는 "stack.size() == 0" 구문을 이용할 수도 있다
}
/**
* 스택에 새로운 데이터를 삽입한다.
*
* @param e 삽입할 데이터
*/
public void push(Object e) {
stack.addLast(e);// 어레이리스트의 가장 마지막 인덱스에 추가한다.
}
/**
* 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
*
* @return 스택에서 가장 최 상위에 위치한 데이터
*/
public Object pop() {
if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
throw new EmptyStackException();
// empty 상태라면 Exception 을 던진다.
} else {
return stack.removeLast();
// ArrayList.removeLast 메소드는 가장 마지막 인덱스에 위치한 자료를 어레이에서 리턴하고 제거한다
}
}
/**
* return 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
*
* @return 스택에서 가장 최 상위에 위치한 데이터
*/
public Object peek() {
if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
throw new EmptyStackException();
// empty 상태라면 Exception 을 던진다.
} else {
return stack.getLast();
// ArrayList.getLast 메소드는 가장 마지막 인덱스에 위치한 데이터를 리턴한다.
}
}
}
잘 보았습니다.
답글삭제http://blog.daum.net/andro_java/913
감사합니다.