[java] Stack 구현해보기(ft. LinkedList)

LIFO 구조의 Stack..

LinkedList를 활용해 Java로 구현해보겠습니다!!!

 

LinkedList(Doubly)구현을 위한 Node 구현

class StackOfLinkedList{
    private Node top;
        int size;

        class Node{
                String value;
                Node prev;
                Node next;
        }
}

Node 클래스를 생성후,

(Doubly Linked List로 구현할 것 이기에, prev, next 두 개의 변수를 설정해줬어요.)

 

가장 최근 Node를 참조할 수 있도록 Pointer 개념으로 top노드를 선언해주었습니다.

또 Stack에 담긴 값의 개수를 나타내는 변수 size도 함께 선언해주었습니다.

 

---

isEmpty( ) 구현

boolean isEmpty(){
        return size == 0;
}

간단하죠? 단순히 Stack의 값의 개수를 나타내는 size가 0인지 여부만 반환해주면 됩니다.

 

---

push( )구현

 

void push(String value){
        Node newNode = new Node();
        newNode.value = value;

        if(isEmpty()){
            top = newNode;
            size += 1;
            return;
        }
        top.next = newNode;
        newNode.prev = top;
        top = newNode;
                size += 1;
    }

 

newNode 생성

새로운 value를 Stack에 입력할 경우, 이를 차곡차곡 쌓아줄 수 있는 메서드를 작성했습니다.

 

새로운 value값을 갖는 새 노드를 newNode로 구현해주고, newNode의 value값을 입력받은 value값으로 설정해주었습니다.

 

 

newNode를 LinkedList에 연결

이 newNode를 LInkedList에 연결시키려고 할 때, 케이스를 두 가지로 나눌 수 있습니다!

특수 케이스인 stack이 비어있을 경우와 그 밖의 경우로 말이죠!

 

1) 비어있는 Stack에 push한 경우

 

if 문을 통해 stack이 비어있을 경우 newNode가 top노드가 되면 됩니다.

stack에 push후, stack에 있는 value는 방금 push했던 newNode 하나밖에 없기 때문이죠.

 

값을 push해준 만큼 size도 1만큼 키워주겠습니다.

 

쉽죠?

 

2) 비어있지 않은 Stack에 push한 경우

 

이 경우, 기존의 LinkedList로 연결되어있던 node들에 새로운 newNode를 연결시켜주기만 하면 됩니다.

여기서 주의할 점은

 

top = newNode;

이렇게 바로 newNode를 top으로 지정하면, 기존의 top을 참조하여 newNode의 prev로 선언해줄 수 없기에,

 

다음처럼 기존 top의 next와 newNode의 prev를 각각 연결해준 후, top을 newNode로 재지정하였습니다.

마찬가지로 size도 1만큼 늘려주었습니다.

 

top.next = newNode;
newNode.prev = top;
top = newNode;

 

---

pop( ) 구현

String pop() {
        if (isEmpty()) {
            return null;
        }

        String topValue = top.value;
        top = top.prev;
        if (size > 1) top.next = null;
        size -= 1;

        return topValue;
    }

 

newNode 연결 해제

 

앞선 push()와 마찬가지로, Stack이 비어있을 경우에는 null만 리턴해주도록 구현했습니다.

 

또한, 연결을 해제하기 전, pop된 값을 리턴해주려면, 참조할 수 있는 값이 필요하기 때문에,
(연결 끊어버리면 더 이상 그 값을 사용하지 못하니까요..)

topValue라는 변수에 기존의 top 값을 초기화해주었습니다.

 

Stack에 값의 개수가 1개일 경우(top 혼자만 있을 경우) top의 prev는 null값일 것이기에,

 

top = top.prev

 

다음 코드를 통해 null값으로 처리해줄 수 있습니다.

하지만 Stack에 값의 개수가 2개 이상일 경우, 이전의 노드와 연결을 해제해야 합니다. 다음처럼요!

 

top = top.prev
top.next = null

 

그 후, size를 1만큼 지워준 후, 기존에 topValue값에 저장된 기존 top의 값을 반환해주었습니다.

 

---

toString() 오버라이딩

Stack에 직접적으로 필요한 기능 구현은 아니지만,,

Stack에 있는 값을 출력했을 때

1 / 2 / 3 / 4 / 5 /

 

이런 식으로 출력될 수 있도록 하고 싶어서 toString 메서드를 오버라이딩해봤습니다!!

 

@Override
    public String toString() {
        Node current = top;
        String answer = "";
        while(current != null) { //runner
            answer += current.value;
            answer += "/";
            current = current.prev;
        }
        return answer;
    }

 

간단한 오버라이딩이니 설명은 패스..!

 

---

최종 코드

public class StackPractice {
    public static void main(String[] args) {

    }
}

class StackOfLinkedList{

    private Node top = null;
    int size;

    class Node{
        String value;
        Node prev;
        Node next;
    }

    boolean isEmpty(){
        return top == null;
    }

    void push(String value){
        Node newNode = new Node();
        newNode.value = value;

        if(isEmpty()){
            top = newNode;
            size += 1;
            return;
        }
        top.next = newNode;
        newNode.prev = top;
        top = newNode;
        size += 1;
    }

    String pop() {
        if (isEmpty()) {
            return null;
        }
        String topValue = top.value;
        top = top.prev;
        if (size > 1) top.next = null;
        size -= 1;

        return topValue;
    }

    @Override
    public String toString() {
        Node current = top;
        String answer = "";
        while(current != null) { //runner
            answer += current.value;
            answer += "/";
            current = current.prev;
        }
        return answer;
    }
}

 

---

 

Test

이제 main함수에 각각 메서드가 잘 작동되는지 출력해보았습니다.

 

이를 실행해보면

 

의도한대로 잘 출력되네요!!