[Data Structure] 스택 (Stack)개념 및 구현

스택 (Stack)

stack은 사전적 의미로 쌓다 포개지다라고 정의되어 있다.

즉, 정의 그대로 데이터를 쌓으면서 관리하는 자료구조라고 할 수 있다.

 

그림에서 볼 수 있듯이 입력과 출력이 한 방향으로 자료를 쌓으면서 관리하기 때문에 가장 늦게 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 형태의 자료구조이다. 

---

스택의 특징

1. 하나의 입출력 방향

데이터의 입출력이 방향이 같다.

2. LIFO (Last In First Out)

스택은 입출력이 한쪽 방향으로만 발생하기 때문에 마지막에 들어온 데이터가 제일 먼저 나가는 자료구조이다.

---

스택 주요 메서드 및 구현

push() - 스택에 데이터 추가
pop()   - 스택에 가장 마지막으로 추가된 데이터를 스택에서 삭제하고 데이터를 반환
peek() - 스택에 가장 마지막으로 추가된 데이터를 반환 (삭제 X)
size()  -  스택에 저장되어 있는 데이터의 개수 반환
clear() - 스택의 모든 데이터 삭제
isEmpty() - 스택이 비었는지 boolean으로 반환

제네릭 클래스로 스택의 주요 메서드를 구현하면 다음과 같이 구현할 수 있다.

class MyStack<T> {
    private T[] elements; //데이터를 담을 배열
    private int top; //최상단 데이터의 인덱스
    private int capacity; //스택 배열의 길이
    private int size; //데이터의 개수

    public MyStack() {
        capacity = 10; //초기 배열의 크기 10
        top = -1;
        elements = (T[]) new Object[capacity];
        size = 0;
    }

    public T peek() {
        if (top == -1) {
            return null;
        }
        return elements[top];
    }

    public void push(T data) {
        if (size == capacity) {
            this.capacity *= 2;
            this.elements = Arrays.copyOfRange(elements, 0, capacity);
        }
        this.elements[++top] = data;
        size++;
    }

    public T pop() {
        if (top == -1) {
            return null;
        }
        T data = elements[top];
        elements[top--] = null;
        size--;
        return data;
    }

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

    public boolean isEmpty() {
        return top == -1;
    }

    public void clear() {
        for (int i = 0; i < this.size; i++) {
            elements[i] = null;
        }
        top = -1;
        size = 0;
    }

    public String toString() {
        return Arrays.toString(Arrays.copyOfRange(elements, 0, this.size));
    }
}

 

MyStack()

public MyStack() {
    capacity = 10; //초기 배열의 크기 10
    top = -1;
    elements = (T[]) new Object[capacity];
    size = 0;
}

스택의 생성자 부분이다 배열의 크기를 10으로 설정하고 최상단 인덱스는 -1 size는 0으로 초기화한다. 

peek()

public T peek() {
    if (top == -1) {
        return null;
    }
    return elements[top];
}

최상단 인덱스가 -1이면 null을 반환하고 데이터가 있다면 배열의 최상단 인덱스에 있는 데이터를 반환한다. 

push()

public void push(T data) {
    if (size == capacity) {
        this.capacity *= 2;
        this.elements = Arrays.copyOfRange(elements, 0, capacity);
    }
    this.elements[++top] = data;
    size++;
}

스택 배열의 capacity와 스택의 size가 같으면 배열의 크기를 키워야 하기 때문에 capacity를 두배로 늘리고 배열을 복사한다.

데이터가 추가되기 때문에 최상단 인덱스 top과 size를 증가시킨다.

pop()

public T pop() {
    if (top == -1) {
        return null;
    }
    T data = elements[top];
    elements[top--] = null;
    size--;
    return data;
}

스택에 데이터가 없을 경우  top은 -1이기 때문에 null을 반환하고 있을 경우엔 최상단 인덱스의 데이터를 null로 바꾸고 데이터를 반환한다. 

size() & isEmpty()

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

public boolean isEmpty() {
    return top == -1;
}

데이터의 개수를 반환하는 size()와 top으로 배열이 비어있는지 확인하고 boolean 타입을 반환한다.

clear()

public void clear() {
    for (int i = 0; i < this.size; i++) {
        elements[i] = null;
    }
    top = -1;
    size = 0;
}

size의 크기만큼 배열의 데이터를 null로 변경하고 top과 size를 다시 초기화한다.

public class StackTest {
    public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
        for(int i = 0; i < 3; i++){
            stack.push(i);
        }

        System.out.println("stack.size = " + stack.size() + " stack.peek() = " + stack.peek());
        System.out.println("stack = " + stack);
        stack.pop();


        System.out.println("\n--------------stack.pop()--------------");
        System.out.println("stack.size = " + stack.size() + " stack.peek() = " + stack.peek());
        System.out.println("stack = " + stack);


        System.out.println("--------------stack.push()-------------");
        for(int i = 3; i <12; i++){
            stack.push(i);
        }
        System.out.println("stack = " + stack);
        System.out.println("stack.size = " + stack.size() + " stack.peek() = " + stack.peek());

        System.out.println("\n--------------stack.clear()------------");
        stack.clear();
        System.out.println("stack.clear(), stack = " + stack);
    }
}