티스토리 뷰

Stack은 LIFO(Last In First Out)의 특징을 가진 자료구조이다. 가장 상단에서만 삽입, 접근, 삭제가 가능한 제한적인 나열구조이다.


이를 가장 대표적인 구현 방법인 배열과 링크드리스트를 사용하여 구현해 보겠다. 




1. 구현에 앞서 인터페이스 생성


public interface OdolStack {

public Object pop();

public Object peek() ;

public boolean isEmpty();

public void push(Object data);

}



pop() : 스택 가장 상단의 데이터를 가져오고 삭제하는 메소드


peek() : 현재 가장 상단의 데이터를 가져오는 메소드


isEmpty() : 스택이 비었는지 확인하는 메소드


push() : 데이터를 스택에 삽입하는 메소드


2. 배열을 활용한 스택 


public class ArrayStack implements OdolStack {

private Object[] stackArray;

private int index; // 현재 인덱스 확인


public static void main(String args[]) {

ArrayStack as = new ArrayStack(10);

as.push("hihi");

as.push(1);

as.push('A');


System.out.println(as.pop());

System.out.println(as.pop());

System.out.println(as.pop());

as.push('A');

System.out.println(as.pop());

}


public ArrayStack(int size) {

this.stackArray = new Object[size];

this.index = 0;

}


@Override

public void push(Object data) {

// TODO Auto-generated method stub

if (index >= stackArray.length) {

throw new IndexOutOfBoundsException("full");

} else {

stackArray[index++] = data;

}


}


@Override

public Object peek() {

// TODO Auto-generated method stub

if (isEmpty()) {

throw new IndexOutOfBoundsException();

} else {

return stackArray[index - 1];

}

}


@Override

public Object pop() {

// TODO Auto-generated method stub

if (isEmpty()) {

throw new IndexOutOfBoundsException();

} else {

Object obj = peek();

stackArray[index] = null;

return obj;

}

}


@Override

public boolean isEmpty() {

// TODO Auto-generated method stub

return (index <= 0);

}


}



3. 링크드 리스트 개념을 활용한 스택 


public class LinkedStack implements OdolStack {

private OdolNode topNode;


public static void main(String args[]) {

LinkedStack ls = new LinkedStack();

ls.push("1");

ls.push(1);

ls.push("hiih");


System.out.println(ls.pop());

System.out.println(ls.pop());

System.out.println(ls.pop());


}


public LinkedStack() {

this.topNode = null;

}


@Override

public void push(Object data) {

// 새로운 노드 생성 

OdolNode newNode = new OdolNode(data);

// 새로운 노드의 다음노드를 삽입 이전의 top을 참조하도록 

newNode.setNextNode(topNode);

// 삽입 이후의 탑은 새로운 노드 

topNode = newNode;

}



@Override

public Object pop() {

if (isEmpty()) {

throw new IndexOutOfBoundsException("empty");

} else {

// 탑노드의 데이터 

Object data = peek();

// 새로운 탑노드는 현재 탑노드의 nextNode 

topNode = topNode.getNextNode();

// 데이터 반환 

return data;

}

}


@Override

public Object peek() {

if (isEmpty()) {

throw new IndexOutOfBoundsException();

} else {

return topNode.getData(); // 데이터만 반환 

}

}


@Override

public boolean isEmpty() {

return (topNode == null);

}


}


class OdolNode { // 스택에 활용할 노드 클래스 

private Object data; // 데이터를 저장 

private OdolNode nextNode; // 이전의 노드를 저장하기 위한 노드 

public OdolNode(Object data) {

this.data = data;

this.nextNode = null;

}

public Object getData() {

return data;

}

public void setNextNode(OdolNode node) {

nextNode = node;

}

public OdolNode getNextNode() {

return nextNode;

}

}



4. 정리

배열을 활용한 개념은 매우 간단했다. 인덱스만 가지고 돌면되니까.


링크드리스트의 경우 


 - 삽입 시 새로운 노드를 생성 후 그 노드의 넥스트노드가 삽입 이전의 탑노드를 참조시키고 현재 탑                                            노드는 새로운 노드를 참조하는 것

 - 추출 시 현재 탑노드의 데이터를 가져온 후 탑노드의 넥스트노드(이전의 탑노드)를 다시 현재 탑노드로 설정한다는 것 


두 가지가 핵심으로 이 부분을 완벽히 이해하고 있어야 할 것 같다.


다음 포스팅은 큐를 위의 방법으로 구현하고 두개의 스택을 활용한 큐와 같은 응용법도 진행해 보겠다.




댓글
댓글쓰기 폼