생각을 개발하자, 박진형

[자료구조, 알고리즘] 스택 - Array, Linked 기반 구현(설명, 구현 수정함) 본문

Data structure & Algorithm/data structure_algorithm

[자료구조, 알고리즘] 스택 - Array, Linked 기반 구현(설명, 구현 수정함)

imjinbro imjinbro 2017.09.22 14:04
[Stack]
1) 구현 기반만 다를 뿐 같은 스택을 구현하는 것이기 때문에 Stack 인터페이스 생성해두고 상속
- ArrayStack
- LinkedListStack

2) 인터페이스
public interface Stack {

public boolean isEmpty();
public void push(Object data);
public Object pop();
public Object peek() throws Exception;
}


[도구가 되는 자료구조]
(1) 배열
(2) 연결리스트

- 배열과 연결리스트는 자체만으로도 좋은 자료구조이지만 다른 자료구조를 구성하는데에 있어서 도구가 되는 자료구조


[Array Stack]
(1) 스택 생성 : N의 크기로 생성, 현재는 비어있음 N개가 그럼 그걸 체크하는 필드가 있어야할듯
- 비교하기위해서 맥스 크기가 따로 있는게 코드상 깔끔

(3) 내부적으로 Object기 때문에 리턴받을 때는 푸쉬 데이터 타입에 맞게 캐스트 해야함

(3) 자바로 동적배열을 생성하고싶다면...
- 자바의 배열은 동적할당되지않으므로 동적할당이 필요할 때 : 연결리스트 사용
- 링크드리스드 기반 스택 구현은 다음 챕터

(4) 구현
public class ArrayStack implements Stack {

/* main thread */
public static void main(String[] args) {
try{
ArrayStack s1 = new ArrayStack(10);
s1.isEmpty();
s1.push("1번째");
s1.push("2번째");
s1.push("3번째");
s1.push("4번째");

String msg = (String)s1.pop();
System.out.println((String)s1.pop()); //4번쨰
System.out.println((String)s1.pop()); //3번째

System.out.println((String)s1.peek()); //2번째
System.out.println((String)s1.peek()); //2번째

}catch(Exception e){
System.out.println(e.getMessage()); // Null을 포함한 익셉션처리
}

}


/* field */
private Object[] arr;
private final int MAX_SIZE; //선언, 생성자에서 초기화해주면됨
private int current;


public ArrayStack(int size) throws Exception {
if(size < 1){
throw new Exception("크기는 10보다 커야합니다");
}

arr = new Object[size];
MAX_SIZE = size;
current = -1;
}


/* method */
@Override
public boolean isEmpty(){
return (current == -1);
}

@Override
public void push(Object data){
if(data == null){
System.out.println("푸쉬 데이터를 넣어주세요");
return ;
}

current += 1;
arr[current] = data;
}

@Override
public Object pop(){
if(isEmpty()){
throw new ArrayIndexOutOfBoundsException("스택이 비었습니다");
}
//다른 변수가 참조하도록 넘겨주고 배열은 참조를 삭제하고
Object result = arr[current];
arr[current] = null;
current -= 1;

return result;
}

@Override
public Object peek(){
if(isEmpty()){
throw new ArrayIndexOutOfBoundsException("스택이 비었습니다");
}

return arr[current];
}
}



[LinkedListStack] : 수정함
(1) "Linked" : 데이터가 담긴 노드끼리 메모리 주소를 저장해서 1열로 연결
- Linked Stack : Linked 노드를 활용해서 스택을 구현
- Linked Node 활용한 리스트 ADT 구현 : 가장 앞의 노드가 head, 보통 head 활용해서 탐색을 하는 것이 리스트


(2) "LinkedStack"
- 마지막에 추가된 노드를 topNode 지정함
- Linked Node 이전에 추가된(next) 연결하고있음
- 가장 처음에 추가된 노드는 이전에 추가된 노드가 없음


(3) 구현

public class LinkedStack implements Stack {

public static void main(String[] args) {
try{
LinkedStack stack = new LinkedStack();
stack.push(1);
stack.push(2);
stack.push(3); // topNode

System.out.println(stack.peek()); // 3
System.out.println(stack.pop()); // 3
System.out.println(stack.pop()); // 2
System.out.println(stack.pop()); // 1
stack.pop(); // catch문으로

}catch(Exception e){
/* 세부적으로 Exception 처리하고싶으면 Exception 종류별로 catch문을 */
System.out.println("msg : " + e.getMessage());
}
}

//LinkedList는 사용관계이지 직접적으로 맺고 있는 관계(상속)는 없음
private static Node topNode;


public LinkedStack() {
LinkedStack.topNode = null;
}

@Override
public boolean isEmpty() {
return (LinkedStack.topNode == null);
}

@Override
public void push(Object data) {
if(data == null){
throw new NullPointerException("추가할 수 있는 데이터 형식이 아닙니다");
}

Node newNode = new Node(data);

if(!isEmpty()){
newNode.setNext(LinkedStack.topNode);
}
LinkedStack.topNode = newNode;
}

@Override
public Object pop() {
if(isEmpty()){
throw new NullPointerException("저장된 데이터가 없습니다");
}

Object data = LinkedStack.topNode.getData();

if(LinkedStack.topNode.getNext() == null){
LinkedStack.topNode = null;
} else {
LinkedStack.topNode = LinkedStack.topNode.getNext();
}

return data;
}

@Override
public Object peek() {
if(isEmpty()){
throw new NullPointerException("저장된 데이터가 없습니다");
}

return LinkedStack.topNode.getData();
}
}