[자료구조] 연결리스트로 Stack(스택) 구현해보기

Stack은 추상자료형(Abstract Data Type , ADT)이기 때문에 구현 방법을 따로 명시하지 않아 어떤 방법으로든 구현이 가능하다. 보통 Array, LinkedList, Deque 중에서 사용하는데, 이 글은 LinkedList를 통해 Stack을 구현하는 방법을 소개한다.

Stack 자료구조란?

Stack 자료구조를 tail이 없는 LinkedList라고 생각하면 쉽다.  LinkedList에서는 head를 제외하면 포인터를 이용해 노드에 접근하기 때문에 중간 노드로의 바로 접근이 불가하다. Stack도 이와 마찬가지로 중간으로의 접근이 불가하고 항상 LinkedList의 head에 해당하는 top에서만 접근이 가능하다. 

 

그림으로 표현하면 아래와 같다.

Stack은 LinkedList가 수직으로 되어있다고 생각하면 쉽다.

Stack은 그림과 같이 접시처럼 쌓여 있기 때문에 중간이나 가장 마지막 레벨에서의 바로 접근은 불가하다. 따라서 Stack 자료구조는 LIFO(Last In First Out)이라고도 불리우는데 , 가장 마지막에 입력된 것이 가장 처음으로 제거된다는 의미이다.

 

Stack의 클래스는 top을 가리키는 노드와 Stack의 길이를 나타내는 height로 필드로 구성한다.

public class Stack{
    private Node top;
    private int height;
}

 

LinkedList도 내부 클래스 필드에 head와 length로 구성되있는데 이와 같이 head가 top이 되고, length가 height가 되었다.

public class LinkedList{
    private Node head;
    private Node length;
}

 

Stack : Constructor 

Stack 초기화시 첫 노드에 저장될 값을 받아, 해당값을 가지고 있는 노드를  top으로 설정한다.

public Stack(int value){
    Node newNode = new Node(value);
    top = newNode;
    height = 1;
}

 

Stack : Push

Stack에 노드 추가하는 것을 Push라고 하며 이는 노드를 추가하고 Top이 해당 노드를 가리키도록 설정하면 된다. 

Push할 때는 두 가지의 상황이 있다. 

1) 노드가 없는 Stack인 경우 

위의 그림과 같이 Stack의 길이가 0인 경우, top은 NULL을 가리키게 된다. 이때는 top이 새로 추가된 노드를 가리키도록 설정하면 된다. 

if(height == 0){
   top = newNode;
}

 

2) 노드 이미 존재하는 Stack인 경우 

새로운 노드 추가시, 새로운 노드의 포인터(newNode.next)가 Top을 가리키도록 설정하여 새로운 노드와 Top을 연결시킨다. 그 후 Top이 새로운 노드를 가리키도록 설정한다,. 

 else{
    newNode.next = top;
    top = newNode;
 }

 

이를 종합해보면 Push 메소드는 아래와 같은 구조로 되어있는 것을 알 수 있다.

public void push(int value){
     Node newNode = new Node(value);
     if(height == 0){
         top = newNode;
     }else{
         newNode.next = Top;
         top = newNode;
     }
     
     height++;
}

Stack : Pop

Stack에서 제일 상단의 노드를 제거하는 작업을 Pop이라고 하며, 삭제할 노드의 포인터를 Null로 처리하고 Top을 한 레벨 내리면 노드가 제거된다.

Pop을 하는 경우에도 두 가지 상황을 고려한다.

 

1) Stack에 노드가 없는 경우 

Stack에 노드가 없으면 Stack의 길이는 0이며, 노드가 없으니 당연히 삭제할 노드도 없다.

public Node pop(){
     if(height == 0) return null;
}

 

2) Stack에 노드가 있는 경우 

Stack에 노드가 이미 존재하는 경우, Top이 한 단계 아래 노드를 가리키도록 하고, 기존 Top이였던 가장 위의 노드를 삭제시켜야한다. 

그림의 과정은 다음과 같다 . 

1) temp 변수가 가장 위의 노드(Top)를 가리키도록 한다.  

2) Top이 한 단계 아래를 가리키도록 한다. 

3) temp의 포인터(temp.next)를 null로 처리하여 , temp와 기존 Stack의 연결을 끊는다. 

Node temp = top;
top = top.next;
temp.next = null;

 

이를 종합하면 Pop 메소드는 다음과 같다. 

public Node pop(){
    if(height == 0) return null;
    
    Node temp = top;
    top = top.next;
    temp.next = null;
    
    height--;
    return temp; //삭제한 노드 
}

 

 

여기까지가 LinkedList로의 Stack 구현이며, 추상자료형이기 때문에 개발자의 선택에따라 메소드를 더 추가하거나, Array나 Deque같은 자료구조를 사용하여 다른 방식으로도 구현할 수 있다.

 

LinkedList로 구현된 최종 Stack 클래스는 다음과 같다. 

public class Stack {

    private Node top;
    private int height;

    class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    public Stack(int value) {
        Node newNode = new Node(value);
        top = newNode;
        height = 1;
    }

    public Node getTop() {
        return top;
    }

    public int getHeight() {
        return height;
    }

    public void push(int value) {
        Node newNode = new Node(value);
        if(height == 0) {
            top = newNode;
        } else {
            newNode.next = top;
            top = newNode;
        }
        height++;
    }

    public Node pop(){
        if(height == 0) return null;
        
        Node temp = top;
        top = top.next;
        temp.next = null;
        
        height--;
        return temp;
    }
}