Java의 스택(Stack) 클래스
자바에서는 Stack 클래스를 따로 지원해주지만 우리는 직접 구현해보는 것을 목표로 할 것이다. 일단은 자바의 Stack 클래스의 함수 부터 살펴 보자.
기본적으로 Stack은
Stack<Element> stack = new Stack<>();
과 같이 생성 할 수 있다.
Stack 클래스는 기본적으로
public Element push(Element item); // 데이터 추가
public Element pop(); // 최근에 추가된(Top) 데이터 삭제
public Element peek(); // 최근에 추가된(Top) 데이터 조회
public boolean empty(); // stack의 값이 비었는지 확인, 비었으면 true, 아니면 false
public int search(Object o); // 인자값으로 받은 데이터의 위치 반환, 그림으로 설명하겠음이 5가지의 함수를 지원해준다. 지금 부터 예제를 통해 하나 하나 살펴 보겠다.
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < 5; i++) {
stack.push(i + 1);
System.out.println(stack.peek());
} // 1, 2, 3, 4, 5 가 현재 들어가 있음
stack.pop(); // 1, 2, 3, 4
System.out.println(stack.peek()); // 4
System.out.println(stack.search(1)); // 4
System.out.println(stack.empty()); // false위의 함수 들 중 search의 동작 방식이 궁금할 것이다. search는 인덱스를 반환 하는 것이 아니라 순번을 반환 하는 것이다. 즉 search의 인자 값으로 받은 값이 스택구조에서 몇번째에 있는지를 반환하는 것이다. 다음 그림을 보면 search의 동작이 이해가 갈 것이다.
사용자 정의 stack 구현
우리가 구현해야하는 것은 Top과 push, pop, peek 이다. search와 empty는 자바에서 지원해주는 것이고(다른 언어는 안해봐서 모르겠습니다.ㅠㅠ) 기본적으로는 저 3가지 요소는 필수이기에 search와 empty는 구현하지 않아도 되지만 그래도 직접 구현해 보겠습니다. 그리고 Stack을 구현할 때 배열로 만드는 방법과 LinkedList로 만드는 방법이 있습니다. 이 두가지의 장단점은 각각 분명하니 만드면서 생각해 보시길 바랍니다. (궁금하신분은 제일 아래로 ㅎㅎ)
배열로 Stack 구현
public class UserArrayStack {
int top;
int [] stack;
int size;
public UserArrayStack(int size) {
this.size = size; //
stack = new int[size];
top = -1; // top 의 값 초기화
}
private void push(int item) {
stack[++top] = item;
System.out.println(stack[top] + " push!");
}
private void peek() {
System.out.println(stack[top] + " peek!");
}
private void pop() {
System.out.println(stack[top] + " pop!");
stack[top--] = 0;
}
private int search(int item) {
for (int i = 0; i <= top; i++) { // for 문은 top 만큼
if (stack[i] == item)
return (top - i) + 1; // top - 탐색한 배열의 인덱스, 배열 이므로 +1 추가
}
return -1;
}
private boolean empty() {
return size == 0;
}
}아마 배열로 구현하는 것은 쉽게 따라 할 수 있고 또 여러분도 굳이 제 코드나 다른 분들의 코드를 보지 않더라도 따라 할 수 있을 것입니다. 저는 결과 값을 쉽게 보기 위해 pop과 peek을 void로 만들었습니다.
LinkedList로 Stack 구현
링크드리스트로 Stack을 구현하는 것은 배열 보다 복잡하나 링크드리스트의 특성과 Stack의 특성을 잘 결합한다면 쉽게 할 수 있을 것입니다. 링크드리스트로 스택을 구현하기 위해서는 우선 Node를 먼저 만들어줘야합니다. LinkedList(연결 리스트)를 간략하게 설명하자면 연결 리스트는 Node(노드)로 구성되어 있으며 노드는 데이터와 다음 노드를 가르키는 주소로 구성되어 있습니다.
public class Node {
private int data;
private Node nextNode;
public Node(int data) {
this.data = data;
this.nextNode = null;
}
protected void linkNode(Node node) {
this.nextNode = node;
}
protected int getData() {
return this.data;
}
protected Node getNextNode() {
return this.nextNode;
}
}
public class UserLinkedListStack {
Node top;
public UserLinkedListStack() {
this.top = null;
}
private void push(int data) {
Node node = new Node(data);
node.linkNode(top);
top = node;
}
public int peek() {
return top.getData();
}
private void pop() {
if (empty())
throw new ArrayIndexOutOfBoundsException();
else {
top = top.getNextNode();
}
}
private int search(int item) {
Node searchNode = top;
int index = 1;
while(true) {
if (searchNode.getData() == item) {
return index;
} else {
searchNode = searchNode.getNextNode();
index ++;
if (searchNode == null)
break;
}
}
return -1;
}
private boolean empty() {
return top == null;
}
}직접 하면서 느낀거지만 이 둘의 구현의 난이도는 별차이가 없다. 구현 요소?가 배열이냐 연결리스트냐의 차이지 세부적인 내용들은 비슷하기 때문이다. 아무튼 설명을 하자면 제일 처음 push를 할 때 새 노드를 만들어 주고 그 후 이전에 있던 노드(top)과 연결을 한다. 그후 새로운 노드가 가장 앞에 있어야 하니 새로운 노드를 Top으로 명시를 한다. pop의 'ArrayIndexOutOfBoundsException()'은 노드가 아무 것도 없을 때의 에러를 막아주는 아이라고 생각하면 된다. pop은 top은 push를 했을 때 새 노드로 재선언 했지만 pop은 지우는 것이므로 top 과 연결된 노드 즉 top 아래의 있는 노드로 top을 재선언 하는 것이다.
배열 구현의 장단점
배열의 장점은 우선 구현이 쉽고 데이터의 접근 속도 즉 조회가 빠르다는 점입니다. 하지만 단점은 항상 최대 개수를 정해놔야지 사용이 가능하다는 점입니다.
즉 구현과 접근은 좋지만 다른 프로젝트에서 활용할 때는 여러모로 불편합니다.
링크드 리스트 구현의 장단점
반대로 연결리스트로 구현했을 때의 장점은 데이터의 최대 개수가 한정되어 있지 않고 삽입 삭제가 용이 하다는 것입니다. 하지만 반대로 배열과 달리 데이터의 조회가 힘든다는 점입니다. 배열과 달리 노드를 따라따라 가서 조회를 해야지 데이터를 찾을 수 있기 때문입니다.
