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

[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();
    }
}