스택을 구현하는 방법은 아래와 같이 2가지로 분류된다.
- 배열로 구현
- 연결리스트로 구현
1. 배열로 스택 구현
전체 소스코드는 아래와 같다. 주석으로 섹션을 표현했으니, 이 부분을 참고해서 아래 설명을 읽어주시면 감사드리겠다.
public class ArrayStack {
//섹션1.
int top = -1;
final Object[] stack;
public ArrayStack(int stackSize) {
this.stack = new Object[stackSize];
}
//섹션2.
boolean isEmpty() {
//스택이 비어있니?
return top == -1;
}
boolean isFull() {
//스택이 꽉 찼니?
return top == this.stack.length-1;
}
//섹션3.
void push(Object data) {
//스택이 꽉 찼는지 먼저 체크
if (this.isFull()) {
throw new RuntimeException("stack is full!");
}
//그 후, 포인터 이동 후 데이터 삽입
this.stack[++top] = data;
}
//섹션4.
Object pop() {
//스택이 비어있는지 먼저 체크
if(this.isEmpty()) {
throw new RuntimeException("stack is empty");
}
// 그 후, 포인터 활용해서 데이터 빼버리고, 해당 위치를 null로 바꾼다. 마지막으로 포인터를 이동시킨다.
Object popData = this.stack[top];
this.stack[top--] = null;
return popData;
}
//섹션5.
Object peek() {
//스택이 비어있는지 먼저 체크
if (this.isEmpty()) {
throw new RuntimeException("stack is empty");
}
// 맨 위에 있는 녀석을 인덱스로 찾아서 출력
return this.stack[top];
}Section.1 기본 변수 선언
우선 데이터를 담을 그릇인 Object 타입 배열을 상수로 선언하고, top이라는 일종의 포인터 변수를 선언한다. 초기값으로 -1을 선언한 이유는, 스택이 비어있는 상태임을 표현하기 위해서이다. 또한 데이터가 삽입, 삭제되면 가장 나중에 들어온 데이터의 인덱스를 가르켜야하기 때문이다.
(로직을 구현할 때, -1로 초기화하는게 가장 편하다)
Section.2 스택의 상태 표현
현재 스택이 비어있는지, 꽉 찾는지 주기적으로 확인해야한다. 배열로 구현 시, 공간이 한정적이기 때문에 삽입할 때 마다 공간이 있는지 체크해야한다. 또한 삭제 시에도 배열이 비어있는지 확인해야한다.
- isEmpty() 포인터 변수에 담긴 숫자를 보고 비어있는지 판단.
- isFull() 포인터 변수에 담긴 숫자와 스택의 길이 - 1 값이 같으면 스택이 꽉 찼다고 간주한다.
Section.3 데이터 삽입
배열을 이용한 데이터 삽입은 의외로 복잡하진 않다.
아래 순서대로 구현을 진행하면 된다.
1. 스택에 데이터를 할당할 공간이 없다면, 예외 처리 진행.
2. 포인터 값 갱신 (ex. 만약 최초 삽입이라면, 포인터 값은 -1에서 0으로 이동됨. 즉 삽입할 위치로 이동되는 것임)
3. 갱신된 위치에 데이터 삽입
만약 구현을 잘못해서 잘못된 위치에 데이터를 삽입한 경우 오버헤드가 발생할 수 있다. 따라서 포인터의 도움을 받아서, 포인터가 가르키고 있는 위치에 데이터를 넣으면 된다.
Section.4 데이터 삭제
데이터 삭제는 데이터 삽입의 반대로 진행하면 된다.
- 마찬가지로, 스택이 비어있는 경우, 예외 발생 시키기
- 포인터가 가르키고 있는 위치의 데이터를 popData 변수에 임시저장
- 포인터가 가르키고 있는 위치의 데이터를 null로 바꿔버리고, 포인터 변수 값에서 1을 뺀다. 즉, 삭제 후 마지막 데이터 위치로 이동.
- popData 반환
만약 구현을 잘못해서 잘못된 위치에 있는 데이터를 삭제한 경우 오버헤드가 발생할 수 있다. 따라서 포인터의 도움을 받아서, 포인터가 가르키고 있는 위치에 있는 데이터를 제거해야한다.
Section.5 데이터 조회
만약 중간위치의 데이터를 탐색한다고 하면, 빈 스택을 하나 더 만들어서 pop값을 임시로 담아둬야한다. 탐색에 필요한 시간, 그리고 불필요한 자원도 소모될 수 있다. 따라서 peek()이라는 메소드를 구현해서, 가장 나중에 들어온 데이터만 조회할 수 있도록 제한해야한다.
- 스택이 비어있으면, 데이터 탐색이 불가능하므로 예외 발생
- 포인터가 가르키고 있는 위치의 데이터를 return;
2. 연결리스트로 스택 구현
class Node {
//섹션1.
Node next;
Object data;
}
public class ListStack {
//섹션2.
Node head;
//섹션3.
boolean isEmpty() {
return head == null;
}
//섹션4.
void push(Object data) {
//1, 새삥 노드 생성
Node newNode = new Node();
newNode.data = data;
//2. 스택이 비어있지 않으면, 원래 노드와 새로운 노드를 연결
if (this.head != null) {
newNode.next = head;
}
//3. 헤더에 새로운 노드의 참조값 저장 [텅텅 비어있을 때는 2번 과정은 쌩까고 3으로 넘어옴]
head = newNode;
}
//섹션5.
Object pop() {
//1. 스택 비어있으면? 예외 발생시키자.
if (this.head == null) {
throw new RuntimeException("stack is empty");
}
//2. 뽑아낸 데이터를 임시저장하고, 헤더 값을 다음 노드와 연결.
Node popNode = head;
Object returnData = popNode.data;
head = popNode.next;
//3. 삭제할 노드의 데어터와 next 초기화
popNode.data = null;
popNode.next = null;
//4. 데이터 값 반환
return returnData;
}
//섹션6.
Object peek() {
//1. 스택이 비어있으면 null 반환
if (this.head == null) {
throw new RuntimeException("스택은 비어있단다.");
}
//2. 그거 아니면 헤더의 데이터 반환
return this.head.data;
}Section.1 노드 클래스 생성
연결리스트의 기본 자료구조인 노드를 먼저 생성한다.
노드 클래스는 다음 노드의 참조값을 지니고 있는 next 변수와 데이터를 담을 data 변수로 구성된다.
Section.2 기본 변수 선언
인스턴스 변수로 head를 생성한다. head는 연결리스트 구현 때와 마찬가지로 첫 노드의 참조값을 지니고 있다.
Section.3 스택 상태 체크
스택이 비어있는지 확인하는 메소드. head가 null이면 스택이 비어있는 것으로 간주된다.
Section.4 노드 삽입
삽입은 연결리스트 때 구현한 삽입로직과 매우 유사하다.
로직은 순서는 아래와 같다.
- 새 노드 생성 후, 새 노드의 데이터 영역에 매개변수로 받은 값을 채워넣는다.
- head가 비어있지 않다면 즉, 이미 노드가 있는 경우, 새로운 노드의 next 영역은 head가 참조하고 있는 영역으로 채워넣는다. 새 노드의 다음 노드와 연결하는 작업이다.
- head 값을 새롭게 생성된 노드의 참조값으로 수정한다.
[만약 2에 걸리지 않는다면, 2는 생략되고, 3만 실행됨.]
Section.5 노드 삭제
노드 삽입과 마찬가지로, 연결리스트에서 노드를 삭제하는 로직과 매우 유사하다. 로직 순서는 아래와 같다.
- 스택이 비어있다면, 예외 발생시키기
- head가 가르키고 있는 위치가 가장 나중에 들어온 데이터이다. head를 popNode 변수에 임시저장하자.
- 반환된 데이터를 임시변수에 저장한다.
- head를 삭제될 노드의 다음 노드 참조값으로 변경한다.
- popNode의 데이터 영역과 next 영역을 null로 바꿔버린다. 가비지 컬렉터가 수거해 갈 것이다.
- 임시 변수를 반환
Section.6 노드 조회
peek() 구현은 마지막으로 들어온 데이터를 조회하면 되기 때문에, head에 담긴 data영역 값을 반환하면 된다.
삽입, 삭제 때와 마찬가지로 스택이 비어있는 경우 예외처리를 진행한다.
