스택(Stack)
스택의 정의
데이터의 삽입과 삭제가 top이라 불리는 한쪽 끝에서만 발생하는 선형 구조이다.
가장 늦게 들어간 데이터가 가장 먼저 삭제되고, 가장 먼저 들어간 데이터가 가장 늦게 삭제된다.
이를 LIFO(Last In First Out)구조 , 혹은 FILO(First In Last Out)구조라고 할 수 있다.
스택의 연산
push
스택의 가장 위(top)에 데이터를 삽입한다.
pop
스택의 가장 위(top) 데이터를 삭제한다.
peek
스택의 가장 위(top) 데이터를 반환한다.
isEmpty
스택이 비어있는지 확인한다.
isFull
스택이 꽉 차있는지 확인한다.
getSize
스택에 현재 저장된 데이터의 수를 반환한다.
스택의 구현
스택을 구현하는 방법에는 두 가지 방법이 있다.
배열을 통해 구현하는 방법과, 연결리스트를 이용하여 구현하는 방법이다.
배열을 이용한 스택의 구현
public class ArrayStack {
int top = -1;
Object[] stack;
public ArrayStack(int size) {
this.stack = new Object[size];
}
void push(Object data) {
if(isFull()) {
throw new IllegalStateException("Stack is full.");
}
stack[++top] = data;
}
Object pop() {
if(isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack[top--];
}
Object peek() {
if(isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack[top];
}
boolean isFull() {
return top<=(stack.length-1);
}
boolean isEmpty() {
return top <=-1;
}
}
- push 연산 시, stack이 이미 꽉 차 있지 않은지 확인해주어야 한다. 꽉 찬 경우 에러 처리를 해주었다.
- pop/peek 연산 시, stack이 비어있지 않은지 확인해주어야 한다. 빈 경우 에러 처리를 해주었다.
연결리스트를 이용한 스택의 구현
import java.util.EmptyStackException;
class Node<T> {
public Node(T data, Node<T> link) {
this.data = data;
this.next = link;
}
T data;
Node<T> next;
}
public class ListStack<T> {
Node<T> top = null;
void push(T data) {
Node<T> newNode = new Node<T>(data,top);
top = newNode;
}
T pop() {
if(isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
Node<T> pastTop = top;
T popData = top.data;
top = pastTop.next;
pastTop.data = null;
pastTop.next = null;
return popData;
}
T peek() {
if(isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return top.data;
}
boolean isEmpty() {
return top == null;
}
}- 연결 리스트로 구현된 스택의 경우, 메모리가 다 차지 않는한 크기 제한이 없기 때문에 isFull 메서드를 구현하지 않았다.
* pop()시 pastTop.data = null; pastTop.next = null; 을 해주는 이유
연결리스트에서 노드를 제거할 때 해당 노드의 참조를 제대로 해제하지 않으면 프로그램이 오래 실행됨에 따라 사용하지 않는 참조가 유지되면서 메모리 누수가 발생할 수 있다.
따라서 노드의 참조를 모두 제거하여 가비지 컬렉터에 의해 해당 메모리가 제거될 수 있도록 한다.
각 구현의 장단점
배열
장점: 구현이 간단하다. 메모리를 동적으로 생성하지 않으므로 데이터의 삽입과 삭제가 빠르다.
단점: stack의 크기가 고정되어있다. 따라서 메모리가 낭비될 가능성이 있다. (고정된 크기의 배열을 전부 사용하지 않을 경우)
연결리스트
장점: stack의 크기를 가변적으로 사용할 수 있다.
단점: 메모리를 동적으로 생성하므로 배열보다 데이터 처리에 속도가 느리다.