Data Structure, Stack

Stack과 Queue, Hash Table 등 대표적인 Data Structure를 정리해보려 합니다.

 

42 Seoul에서 PushSwap Project를 구현할 때가 새록새록 나더군요,,

 

일단 Stack에 대해 알아봅시다

1. 스택이란?

나서스 스택,,

우리가 흔히 일반적으로 Stack이라 하는 것은 영단어 의미 그대로 쌓다라는 뜻을 갖고 있는데요

 

프로그래밍에서의 Stack은 단순히 쌓는 것만이 아닌 쌓고 꺼내는 데이터 구조를 의미합니다. 

 

쉽게 이해하기 위해 모든 교수님들이 사용하시는 예제를 한 번 사용하겠습니다

 

급식판

식당 아주머니가 급식판을 추가할 때는 위에부터 추가해주시죠

 

그리고 우리가 급식판을 가져갈 때는 위에 것부터 순서대로 사용합니다 (그림과 달리 일반적인 경우에)

 

이러한 구조를 LIFO(Last In First Out)라 하죠

 

마지막에 들어온 데이터가 가장 먼저 나가는 구조를 Stack이라 합니다.

 

2. Operations

Data Structure를 형성하기 위해 필요한 공통적인 Operation들이 있는데요

 

(1) Insert, 데이터 추가

(2) Remove, 데이터 추출

(3) Test if empty, Check Empty

 

이 Common Operation들은 Stack 뿐만이 아니라 다른 Data Structure에서 공통적으로 사용됩니다 (이름만 달라질뿐)

 

Stack에서 Insert Method(Function)는 Push

Stack에서 Remove Method(Function)는 Pop

Stack에서 Test if empty는 IsEmpty

일반적으로 정의하고 사용합니다.

 

이때 일반적인 프로그래밍 언어에서 Stack을 Implementation하기 위해 2가지 방법을 사용할 수 있습니다.

 

(1) Linked List

(2) Array

 

두 가지 데이터 구조로 구현할 때 장단점이 있습니다 뒤에서 확인해봅시다.

3. Code

다음 예제는 String Data를 Linked List를 통해 Stack 구조를 Implementation한 코드입니다.

import java.util.NoSuchElementException;

public class Stack {
    private Node first = null;
    private static class Node {
        Node next;
        String item;
    }

    public boolean IsEmpty() {
        return first == null;
    }

    public void Push(String item) {
        Node second = first;
        first = new Node();
        first.next = second;
        first.item = item;
    }

    public String Pop() {
        if (IsEmpty())
            throw new NoSuchElementException("스택이 비어있습니다.");
        String item = first.item;
        first = first.next;
        return item;
    }
}

import java.util.NoSuchElementException;
public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack();
        try {
            stack.Push("First Item");
            String item1 = stack.Pop();
            System.out.println("Pop된 아이템: " + item1);
            stack.Push("First Item");
            stack.Push("Second Item");
            String item2 = stack.Pop();
            System.out.println("Pop된 아이템: " + item2);
            String item3 = stack.Pop();
            System.out.println("Pop된 아이템: " + item3);
            String item4 = stack.Pop();
            System.out.println("Pop된 아이템: " + item4);
        } catch (NoSuchElementException e) {
            System.out.println("스택이 비어있습니다. 에러 메시지: " + e.getMessage());
        }
    }
}

위에서 언급한 Push, Pop, IsEmpty를 구현하고  Main 문에서 간단히 실행한 결과 입니다.

실행 결과

Push를 통해 문자열 데이터를 추가하고 Pop을 통해 문자열 데이터를 추출하여 확인하는 간단한 예제입니다.

 

Node라는 Inner static class를 선언하여 Linked List를 구현하고 각 Operation들을 Method로 구현했습니다

private static class Node {
    Node next;
    String item;
}

 

 

Stack구조에서는 First Node가 가장 중요합니다.

 

First Node 변수를 통해 Stack에 가장 앞부분이 어디에 있는지 알려주기 때문에

 

Push, Pop Method가 실행될 경우 First 변수가 가르키는 Node가 바뀌는 것을 확인할 수 있습니다.

public void Push(String item) {
    Node second = first; // 기존 Node를 Second Node로 옮기고
    first = new Node(); // First Node에 새로운 Node를 생성
    first.next = second; // First -> Second Link
    first.item = item; // First에 새로이 Push한 Data 입력
}

public String Pop() {
    if (IsEmpty())
        throw new NoSuchElementException("스택이 비어있습니다.");
    String item = first.item; // Data 추출
    first = first.next; // First Node를 Second Node로 변경
    return item; // Pop Value Return
}

 

Linked List는 어렵지 않게 데이터를 추가하고 삭제할 수 있는 장점이 있습니다 (새로운 노드 만들고 삭제하면 장땡)

 

 

다음은 Array로 구현한 Stack을 살펴봅시다.

 

import java.util.NoSuchElementException;

public class Stack {
    int N = 0; // index
    String [] arr = new String[4];

    public void Push(String item) {
        if (N > arr.length - 1) {
            DupArr(arr.length * 2);
        }
        arr[N++] = item;
    }
    public String Pop() {
        if (IsEmpty())
            throw new NoSuchElementException("스택이 비어있습니다.");
        String item = arr[N-1];
        arr[N-1] = null;
        N -= 1;
        if (N < arr.length / 4)
            DupArr(arr.length / 2);
        return item;
    }

    public boolean IsEmpty() {
        return N == 0;
    }
    public void DupArr(int size) {
        String [] temp = new String[size];
        for (int i = 0; i < N; i++) {
            temp[i] = arr[i];
        }
        arr = temp;
    }

}

Array의 경우 Linked List와 달리 배열의 크기를 미리 정해놓기 때문에

 

Resize의 과정이 필요하다

 

만약 한 칸씩만 증가하게된다면 굉장히 비효율적일 것이다.

 

N이 커질 수록 복사해야하는 비용이 커지기 때문이다.

 

따라서 매번 한 칸씩 size를 늘리는 것이 아닌 2배씩 size를 늘리게 된다면 (컴퓨터는 2를 좋아해)

 

굉장히 경제적일 것이다.

 

이것은 Push할 때 뿐만 아니라 Pop을 할 때도 동일하다

 

배열의 크기보다 들어있는 요소들이 적을 경우 메모리를 낭비하기 때문이다.

 

이 때 만약 요소가 배열의크기에 1/2일 때 축소를 하게된다면

 

배열이 가득차 있는 상황이 다시 되어 Push를 할 경우 다시 늘어나는 비효율이

 

다시 발생할 수 있다. 따라서 1/2이 아닌 1/4 일때 1/2로 Resize해준다.

 

이렇게 코드를 작성했을 경우 최소 25%~100% 배열을 사용하게 됩니다.

4. Array, Linked List의 장단점

(1) Element 수, Index 조회

 

Arr >>> Linked List

 

Linked List와 비교하여 K번째 인덱스의 데이터를 조회하기 쉽다.

Arr[K-1] 끝! 하지만 Linked List는 함수를 이용하여 Node를 조회해야하는 번거로움이 있다.

 

Arr에서는 N만큼 데이터가 들어있기에 바로 Return하면 된다.

Linked List는 한 바퀴 순회해서 Count를 해야하는 번거로움이 있다.

 

(2) Add, Remove

 

Arr <<< Linked List

 

Arr는 위에서 설명했듯이 Resizing 과정이 필요합니다.

 

5. 결론

Arr가 더 좋은거 아니냐!?

 

상황에 따라 다릅니다.

 

Linked List는 원하는 다른 타입의 데이터들을 추가적으로 넣을 수도 있는 장점들도 있고

 

Arr는 index Error 핸들링을 계속해줘야하는 번거로움이 있죠

 

프로그램 아키텍쳐에 따라 다음 두 데이터 구조의 장단을 알고 적합한 방법을 선택하는 것이 좋겠습니다.

 

긴 글 읽어주셔서 감사합니다아,,

 

다음글은 Queue로 만나뵙겠습니다!