[백엔드 과정][자바 기초] - 스택 구현하기 (2.LinkedList를 이용한 구현)

---

Stack

• 스택은 선입후출 구조로 먼저 들어온 값이 맨 아래로 깔려서 맨 나중에 들어온 값부터 차례대로 삭제해야 맨 마지막에 맨 처음에 들어온 값을 빼내는 구조이다.
• 스택을 구현하는 자료구조로는 ArrayList와 LinkedList가 있다.

Linked List

📌출처 : https://www.geeksforgeeks.org/data-structures/linked-list/

---

[Stack Interface]

package arrays;

public interface Stack{
    public boolean isEmpty();
    public void push(Integer element);
    public Integer pop();
    public Integer peek();
    public int size();
}

[LinkedList로 구현한 Stack]

package arrays;

import java.util.EmptyStackException;

public class LinkedListStack implements Stack{
    static class LinkedNode{
        Integer data;
        LinkedNode next;

        public LinkedNode(Integer data, LinkedNode next) {
            this.data = data;
            this.next = next;
        }

        public Integer getData() {
            return data;
        }

        public LinkedNode getNext() {
            return next;
        }
    }


    LinkedNode head; //data와 다음 Node를 가르키는 link가 있다.
    int cnt;

    public LinkedListStack() {
        this.head = null;
        this.cnt = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.cnt == 0;
    }

    @Override
    public void push(Integer element) {
        this.head = new LinkedNode(element, this.head);
        this.cnt++;
    }

    @Override
    public Integer pop() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }

        Integer value;
        value = this.head.getData();
        this.head = this.head.getNext();
        this.cnt--;


        return value;
    }

    @Override
    public Integer peek() {

        if(isEmpty()){
            throw new EmptyStackException();
        }
        return this.head.getData();
    }

    @Override
    public int size() {
        return this.cnt;
    }

    @Override
    public String toString() {

        StringBuilder line = new StringBuilder();

        LinkedNode node = this.head;
        while (node != null){
            line.reverse().append(((line.length()!=0)?" ":"")+node.getData());
            node = node.getNext();
        }

        return line.toString();
    }
}

• LinkedNode는 data와 다음 Node의 레퍼런스를 가지고 있는 next가 있다.
• head는 현재 노드를 의미하고 cnt는 LinkedNode의 크기를 의미한다.
• 앞서 포스팅한 ArrayStack과 유사하게 메소드들이 구성되어 있다.