[자료구조] 스택(연결리스트 이용) - push, pop

안녕하세요. PEACE-입니다.

자료구조 스터디 [네 번째] 글입니다.

이번 포스팅은 연결리스트를 이용한 스택 구현입니다. 연결리스트의 개념을 반드시 알고있어야하며 모르신다면 아래 링크를 통해 학습하시길 권장합니다.

선형 연결리스트 - 삽입, 삭제(Last) : http://mailmail.tistory.com/24

1. 스택

스택이란 자료구조 중 하나입니다. 가장 최근에 들어간 데이터가 가장 먼저 나오며 흔히 후입선출(Last In First Out)이라고 말합니다. 이와 같은 호출이 일어나면 스택에 함수에 대한 정보가 push되고 함수의 끝이나 return을 만나면 함수가 종료되면서 pop을 통해 나중에 호출된 함수가 스택에서 빠져나옵니다.

2. 스택구현

연결리스트를 이용한 스택 구현은 스택의 크기가 정해져있지 않고 동적으로 늘어날 수 있습니다. 연결리스트를 통해 얻얼 수 있는 장점입니다. 우선 첫 노드를 head, 마지막 노드를 top으로 가리키며 push와 pop을 유연하게 구현할 수 있습니다. push 메서드는 스택(연결리스트)에 새 노드를 이어붙이는 작업을 구현하고, pop 메서드는 스택(연결리스트)에 들어있는 마지막 노드를 제거하는 작업을 구현합니다. 연결리스트를 이용한 스택은 배열을 이용한 스택 구조와 다르게 데이터를 뺀다는 의미에 완벽하게 들어맞는 작업을 구현할 수 있습니다. 또한 사이즈가 정해져있지 않기 때문에 isFull과 같은 메서드를 구현할 필요가 없으며, 데이터가 비어있는지만 확인하면 되므로 isEmpty 메서드 정도만 구현하면 됩니다다. 추가로 배열과는 다르게 index의 범위가 벗어나는 문제가 생길 수가 없으므로 IndexOutOfBoundsException과 같은 예외 상황이 발생하는 것에 대해 염려할 필요가 없습니다.

*필요 멤버

 - 멤버 변수 : 

head : 첫 노드

top : 마지막 노드

 - 메서드 :

isEmpty() : boolean

push(data) : void

pop() : data type of stack array

3. Push

연결리스트를 이용한 스택의 PUSH는 선형 연결리스트의 insertLast와 흡사하며 두 가지의 상황이 있다.

CASE 1 : 스택이 비어있을 때

CASE 2 : 스택이 비어있지 않을 때 

'CASE 1'은 HEAD와 TOP이 NULL인 상태이다. 둘 다 새 노드를 가리킨다. 그러나 'CASE 2'일 때는 TOP의 위치만 변경해주면 되므로 TOP만 새 노드를 가리키면 된다.

HEAD와 TOP이 아무것도 가리키지 않는 상태로 초기 상태이다.

새 데이터(새 노드)가 PUSH되었고, 'CASE 1'에 속하므로 HEAD과 TOP 모두 새 노드를 가리킨다.

새 데이터(새 노드)가 PUSH되었고, 'CASE 2'에 속하므로 TOP만 새 노드를 가리킨다.

새 데이터(새 노드)가 PUSH되었고, 또 'CASE 2'에 속하므로 TOP만 새 노드를 가리킨다.

4.Pop

연결리스트를 이용한 스택에서 POP은 마지막 노드를 제거하는 작업이므로 deleteLast와 흡사하며, 두가지 상황을 고려해야한다.

CASE 1 : 스택이 비어있을 때

CASE 2 : 스택이 비어있지 않을 때 

'CASE 1'은 HEAD와 TOP이 NULL인 상태이다. 빠져나갈 데이터가 없다는 뜻이므로 상황에 맞게 처리해주면 된다. 'CASE 2'일 때는 TOP이 가리키는 노드를 삭제하고 TOP은 이전 노드를 가리키도록 한다.

스택에 3개의 데이터(노드가)있다.

스택은 후입선출이므로 마지막에 들어온 노드의 연결을 해제하고 TOP이 가리키는 위치를 이전 노드로 옮긴다.

POP 후 정리된 상태

스택은 후입선출이므로 마지막에 들어온 노드의 연결을 해제하고 TOP이 가리키는 위치를 이전 노드로 옮긴다.

데이터가 한 개만 남았다.

마지막 데이터를 삭제했으므로 HEAD와 TOP 모두 연결을 해제한다.(NULL로 만들어준다.)

5.소스코드

Node.class

public class Node {

    public int data;
    public Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Stack.class

/* Array를 이용한 스택 구현
 * 0. 준비 : 노드(연결리스트를 사용하기 위해)
 * 1. 변수 : head, top
 * 2. createNode : Node
 * 3. isEmpty : boolean
 * 4. input -> push : void 
 * 5. output -> pop : data type
 * */

public class Stack {
    private Node head;
    private Node top;

    public Stack() {
        head = top = null;
    }

    private Node createNode(int data) {
        return new Node(data);
    }

    private boolean isEmpty() {
        return top == null ? true : false;
    }

    public void push(int data) {
        if (isEmpty()) { // 스택이 비어있다면
            head = createNode(data);
            top = head;
        }
        else { //스택이 비어있지 않다면 마지막 위치를 찾아 새 노드를 연결시킨다.
            Node pointer = head;

            while (pointer.next != null)
                pointer = pointer.next;

            pointer.next = createNode(data);
            top = pointer.next;
        }
    }

    public int pop() {
        int popData;
        if (!isEmpty()) { // 스택이 비어있지 않다면!! => 데이터가 있다면!!
            popData = top.data; // pop될 데이터를 미리 받아놓는다.
            Node pointer = head; // 현재 위치를 확인할 임시 노드 포인터

            if (head == top) // 데이터가 하나라면
                head = top = null;
            else { // 데이터가 2개 이상이라면
                while (pointer.next != top) // top을 가리키는 노드를 찾는다.
                    pointer = pointer.next;

                pointer.next = null; // 마지막 노드의 연결을 끊는다.
                top = pointer; // top을 이동시킨다.
            }
            return popData;
        }
        return -1; // -1은 데이터가 없다는 의미로 지정해둠.

    }

    public void display() {
        Node pointer = head;
        System.out.print("STACK : ");
        while (pointer.next != null) {
            System.out.print(pointer.data + " ");
            pointer = pointer.next;
        }
        System.out.println(pointer.data);
    }
}