자료구조 스택 (Stack) 자바로 구현

1. 개요

스택은 대표적인 자료구조중 하나로, 가장 마지막에 들어간 데이터가 가장 먼저 나오는 

후입선출, LIFO (Last In First Out) 형식의 자료구조다.

 

활용방법으로는

• 웹 브라우저 뒤로가기 : 가장 마지막에 열린 페이지부터 나온다.
• 실행 취소 (undo) : 가장 마지막에 실행된 것부터 실행을 취소한다. (ctrl + z)
• 함수 호출 : 프로그램에서 함수를 호출할 때, 함수가 끝나면 원래 코드로 돌아가야 한다. 이런 함수의
  정보를 저장하는 메모리를 콜 스택이라고 한다.

기능으로는

• push() : 데이터를 넣는 메소드
• pop() : 데이터를 빼는 메소드
• top(), peek() : 데이터를 빼지 않고, 가장 위에 있는 데이터를 확인하는 메소드

자세히 설명하면, push는 데이터를 하나씩 담는다.

 

pop은 최근에 들어온 데이터를 가져오고, 그 데이터를 지우고, 다시 pop을 하면, 2번째로 나중에

들어온 데이터가 나오고 삭제된다.

 

top과 peek은 만드는 사람에따라 같은 기능에 다른 이름을 붙인 거다. 기능은 pop과 다르게, 데이터를

삭제하지 않고, 최근에 들어온 데이터를 확인하는 것이다.

 

 

2. 구현

package stack;

public interface IStack<T> {
    void push(T data);
    T pop();
    T peek();
    int size();
}

package stack;

public class MyStack<T> implements IStack<T> {

    private int size;
    private Node head;

    public MyStack() {
        this.size = 0;
        this.head = new Node(null); // 더미
    }

    @Override
    public void push(T data) {
        Node node = new Node(data, this.head.next);
        this.head.next = node;
        this.size++;
    }

    @Override
    public T pop() {
        if (this.isEmpty()) {
            return null;
        }
        Node curr = this.head.next; // 가장 최신의 노드
        this.head.next = curr.next;
        curr.next = null;
        this.size--;
        return curr.data;
    }

    @Override
    public T peek() {
        if (this.isEmpty()) {
            return null;
        }
        return this.head.next.data; // 데이터를 빼지 않고 데이터 가져오기
    }

    private boolean isEmpty() {
        return this.head.next == null;
    }

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

    private class Node {
        T data;
        Node next;

        Node(T data) { this.data = data; }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

    }
}

3. 설명

3-1. 노드 구성

노드는 데이터와 넥스트 포인터를 가진다.

 

노드를 생성할 때, 인수로 데이터를 넣으면 그 데이터를 노드에 집어넣는다.

 

생성 시, 데이터와 노드를 집어넣으면, 노드에 데이터를 집어넣고, 넥스트 포인터는 들어온 노드를 가르킨다.

 

 

3-2. 멤버 변수(member variable), 생성자(constructor)

멤버 변수는 스택의 크기를 나타내는 size, 더미 노드로 쓸 head가 있다.

 

생성자는 사이즈를 0으로 (아직 데이터가 없으니), head에 빈 노드를 집어넣는다.

 

 

3-3. push(T data)

데이터를 삽입하는 메소드다.

데이터를 집어넣을 노드를 생성하는데, next를 원래 있던 최신의 노드로 설정한다.

 

그리고 head의 next를 새로운 노드로 설정한다.

 

자세히 살펴보면, head의 next가 없으니 null이 될 것이다.

그리고 head의 next는 새로운 노드가 되니 처음 데이터가 들어왔다면,

head(데이터 X, next newNode1), newNode1(데이터 O, next null) 의 상태가 되어있다.

 

이 상태에서 데이터를 하나 더 넣으면,

head(데이터 X, next newNode2), newNode1(데이터 O, next null),

newNode2(데이터 O, next newNode1)

 

하나 더 들어오면,

head(데이터 X, next newNode3), newNode1(데이터 O, next null),

newNode2(데이터 O, next newNode1), newNode3(데이터 O, next newNode2)

의 형태가 된다.

 

head에서 최근에 들어온 데이터를 next로 바로 확인할 수 있고, 최신 노드의 next로 바로 이전

노드의 위치를 알 수 있기 때문에, 그 데이터를 삭제해도, 최신의 데이터를 계속 찾을 수 있다.

 

 

3-4. isEmpty()

스택이 비어있는지 확인하는 메소드다.

head의 next가 null이면, 데이터가 들어오지 않았으니 비어있고, true가 반환된다. null이 아니면 비어있지

않으니 false가 반환된다.

 

 

3-5. pop

만약 스택이 비어있으면, null을 반환한다.

비어있지 않으면 데이터를 꺼내기 위해, curr 노드를 생성하고, 최신 데이터가 들어있는, head의 next를 집어넣는다.

 

curr에 들어간 최신 데이터의 next는, 바로 이전에 들어온 노드이고, head의 next를 curr의 next로 바꿔준다.

 

head의 next가 curr이 아니고, curr의 next를 null로 지워주면, curr의 데이터는 curr변수 이외는 아무도
참조하지 않는 노드가 되고, 함수가 종료되면, curr변수가 없어짐과 동시에 자바의 GC (Garbage Corrector 
쓰레기 수집기)에 의해 삭제된다.

 

데이터가 하나 빠지니, 사이즈를 하나 줄이고, curr의 데이터를 반환하고 끝난다.

 

 

3-6. peek()

pop과 공통점은 최신의 데이터를 반환하는 것이지만, 차별점은 최신의 데이터를 삭제하지 않는다는 점이다.

스택이 비었으면 null을 반환하고, 그렇지 않다면 head의 next, 최신의 데이터가 들어간 노드의 데이터를 반환한다.

 

 

3-7. size()

스택에 데이터가 얼마나 들어갔는지, 그 사이즈를 반환한다.