스택(Stack)

GilLog·2020년 10월 12일

자료구조

목록 보기

1/7

1. 스택(Stack)

1.1 스택 이란?

스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조로 후입선출(LIFO - Last In First Out)로 되어 있다.
자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.
- WikiPedia

스택은 간단히 한줄로 말하면, 나중에 넣은 자료를 제일 먼저 꺼내는 자료구조다.

위 사진처럼 마치 뷔페에서 식판을 꺼내듯 가장 위에 쌓여있는 자료를 제일 먼저 꺼내는 방식이다.

1.2 스택 메소드

Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다.

Stack을 생성할 때는 java.util.Stack 클래스를 임포트 받은 후,

import java.util.Stack;

아래와 같이 생성하며

// E는 강제 형변환 문제를 해결해주는 제너릭 <E> 이다.
Stack<E> stack = new Stack<E>();

기본적으로 사용되는 메소드는 다음과 같다.

메소드	반환 타입	용도
push(E data)	E	스택에 data를 넣는다.
pop()	E	스택 가장 위에 있는 data를 제거하고 return 한다.
peek()	E	스택 가장 위에있는 data를 제거없이 return 한다.
empty()	boolean	스택이 비어있으면 true를 return 한다.
search(Object o)	int	스택에서 해당 Object의 존재하는 위치의 인덱스를 반환한다. 이때, 인덱스는 제일 마지막에 저장된 요소의 위치부터 0이 아닌 1부터 시작한다.

2. 스택 관련 Java 코드

스택을 Java로 직접 구현해보면 아래와 같은 메소드를 정의 해주어야 한다.

push() : 데이터 입력
pop() : 최상위 데이터 출력
empty() : 스택이 비어있는지 확인
isFull() : 스택이 꽉차있는지 확인

여기에 스택은 push와 pop을 할 위치를 저장하고 있어야해서 스택 포인터(SP)가 필요하다.

스택 포인터는 스택에서 다음 데이터가 들어갈 위치를 저장하고 있는다.

2.1 스택 포인터(SP)

// 기본 값 -1
private int sp = -1;

2.2 push()


// 스택 포인터가 최대 크기와 같다면 return
// 아닌 경우 최상위 위치에 데이터를 입력
public void push(Object o) {
    if(isFull(o)) {
        return;
    }
    
    stack[++sp] = o;
}

2.3 pop()


// 스택 포인터가 0인 경우 null return
// 아닌 경우 최상위 위치 데이터를 출력
public Object pop() {
    
    if(isEmpty(sp)) {
        return null;
    }
    
    Object o = stack[sp--];
    return o;
    
}

2.4 isEmpty()


// 
private boolean isEmpty(int cnt) {
    return sp == -1 ? true : false;
}

2.5 isFull()

// 스택 포인터+1이 MAX_SIZE가 되면 꽉찬것
// true return
private boolean isFull(int cnt) {
    return sp + 1 == MAX_SIZE ? true : false;
}

2.6 최대 크기가 없는 스택

스택에는 보통 MAX_SIZE(최대 크기)를 사용해서 구현한다.

isFull 메소드에서 스택 포인터 + 1과 MAX_SIZE를 비교하기 때문이다.

아래에는 두 가지 방법으로 최대 크기가 없는 스택을 구현하는 코드이다.

arraycopy 활용 동적 배열 스택


// MAX_SIZE 2배에 해당하는 새로운 배열(arr)을 생성하고
// arraycopy를 사용해서 기존 stack 인덱스 0 ~ MAX_SIZE까지의 데이터를 새로운 배열 (arr)의 인덱스 0부터 복사한다.
// stack에 arr의 참조값을 저장한다.
// MAX_SIZE를 2배 늘려준다.
// 원래라면 꽉찼을 스택포인터(sp)에 저장이 가능해진다.
public void push(Object o) {
    
    if(isFull(sp)) {
        
        Object[] arr = new Object[MAX_SIZE * 2];
        System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
        stack = arr;
        MAX_SIZE *= 2; // 2배로 증가
    }
    
    stack[sp++] = o;
}

Linked List 활용 구현


public class Node {

    public int data;
    public Node next;

    public Node() {
    }

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


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은 데이터가 없다는 의미로 지정해둠.

    }

}